سوال ۳۲

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

اگر تعداد رشته‌هایی به طول $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$$