ماشین (بازپرور) یک رشته‌ی ارقام در مبنای ۲ را به عنوان ورودی گرفته و یک رشته‌ی جدید برمی‌گرداند. اگر رشته‌ی ورودی $S= s_1s_2...s_n$ باشد، این ماشین با درنظرگرفتن یک رشته‌ی خروجی تهی در ابتدا، از چپ به راست بیت‌های $S$ را می‌خواند، سپس به ازای هر بیت که یک باشد خود $S$ و به ازای هر بیت که صفر باشد نقیض $S$ را به رشته‌ی خروجی می‌چسباند. منظور از نقیض یک رشته، رشته‌ای با همان طول است که هر بیت صفر آن به یک و هر بیت یک آن صفر شده باشد. برای مثال اگر به این ماشین رشته‌‌ِی ۱۰۱۱ را بدهیم، رشته‌ی خروجی ۱۰۱۱۰۱۰۰۱۰۱۱۱۰۱۱ خواهد بود. واضح است که اگر طول رشته‌ی ورودی $n$ باشد، طول رشته خروجی $n^۲$ خواهد بود.

رشته‌ی سه بیتی $A= a_۱a_۲a_۳$ را طلایی گوییم، اگر با شروع از یکی از اعضای مجموعه‌ {۰۰٫۰۱٫۱۰٫۱۱} و استفاده مکرر از دستگاه بازپرور بتوان به رشته‌ای مانند $B= b_۱b_۲...b_m$ رسید که رشته‌ِی $A$ زیررشته‌‌ی آن باشد. رشته‌ی $A$ زیررشته‌ی $B$ است، اگر اندیسی مانند $i$ وجود داشته باشد که $i \le m-2$ و $b_i=a_1$٬ $b_{i+1}=a_2$ و $b_{i+2}=a_3$. برای مثال رشته‌ی ۱۰۰ طلایی است چرا که با شروع از ۱۰ و یک‌بار استفاده از دستگاه به رشته ۱۰۰۱ می‌رسیم که رشته ۱۰۰ زیررشته‌ی آن است. چند تا از رشته‌های مجموعه‌ی {۱۱۱٫۰۰۰٫۰۱۰٫۱۰۱} طلایی هستند؟

1. ۰
2. ۱
3. ۲
4. ۳
5. ۴

• سوال بعد
• سوال قبل