المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۱:سوال ۳۲

سوال ۳۲

فرض کنید ‎$A$‎ مجموعه‌ی کلیه‌ی رشته‌های به طول ‎۸‎ از ‎۰‎ و ‎۱‎ باشد که در آن‌ها رشته‌ی ‎۰۰‎ نیامده باشد (در رشته‌ی ‎۰۱۰۱۱۰۰۱‎ رشته‌ی ‎۰۰‎ آمده ولی در ‎۰۱۱۰۱۰۱۱‎ رشته‌ی ‎۰۰‎ نیامده است) و ‎$B$‎ مجموعه‌ی کلیه‌ی رشته‌های به طول ‎۸‎ باشد که در آن ‎۱۱‎ نیامده باشد. ‎$A \cup B$‎ چند عضو دارد؟

  1. ۶۶
  2. ۶۸
  3. ۱۰۸
  4. ۲۵۴
  5. ۲۵۶‎

پاسخ

گزینه (۳) درست است.

اگر تعداد رشته‌هایی به طول $n$ که شامل ۰۰ نیستند را با $F(n)$ نمایش دهیم٬ آن‌گاه ان تعداد را به دو دسته تقسیم کنیم٬ رشته‌هایی که رقم آخرشان ۰ است و رشته‌هایی که رقم آخرشان ۱ است. رقم ماقبل آخر تمام رشته‌های موجود در دسته‌ی اول ۱ می‌باشد چون در هیچ یک از آن‌ها دو رقم ۰ پشت سر هم نیامده است٬ بنابراین تعداد آن رشته‌ها را $n-2$ رقم اول تعیین خواهد کرد که با توجه به تعریف این تعداد برابر $F(n-2)$ می‌باشد. تعداد رشته‌های موجود در دسته‌ی دوم نیز برابر $F(n-1)$ می‌باشد.

بنابراین رابطه‌ی $F(n)=F(n-1)+F(n-2)$ برقرار است و با توجه به تساوی‌های $F(2)=3$ و $F(3)=5$ تساوی‌های زیر حاصل خواهند شد:

$$F(4)=8 \quad , \quad F(5)=13 \quad , \quad F(6)=21 \quad , \quad F(7)=34 \quad , \quad F(8)=55$$

از طرف دیگر با توجه به اصل شمول و عدم شمول رابطه‌ی زیر برقرار است:

$$|A \cup B| = |A| +|B| - |A \cap B|$$

حاصل هر یک از عبارات $|A|$ و $|B|$ برابر ۵۵ به‌دست آمد. حاصل $|A \cap B|$ نیز برابر ۲ می‌باشد زیرا تنها دو رشته‌ی ۱۰۱۰۱۰۱۰ و ۰۱۰۱۰۱۰۱ می‌باشد که نه شامل ۰۰ و نه شامل ۱۱ است. بنابراین:

$$|A \cup B|=55+55-2=108$$


ابزار صفحه