الگوریتم زیر که $Zip$ نام دارد، رشتە‌ای دودویی (از ارقام $۰$ و $۱$) را به عنوان ورودی می‌گیرد و به صورت زیر اجرا می‌شود:

1. $S$ را مجموعە‌ای تهی در نظر بگیر و ورودی را در $z$ بریز.
2. اگر $z$ یک رقمی است یا $z ∈ S$ ،آن را برگردان و به پایان برس.
3. $z$ را به $S$ اضافه کن.
4. دو رقم سمت راست $z$ را در نظر بگیر؛ اگر این دو رقم برابر باشند، رقم سمت راست $z$ را حذف کن؛ در غیر این صورت، رقم سمت راست $z$ را حذف کن و آن را به سمت چپ $z$ اضافه کن.
5. به مرحلە‌ی ۲ بازگرد.

برای مثال، اگر رشتە‌ی $۱۱۱۰$ را به عنوان ورودی به این الگوریتم بدهیم، مقدار $z$ به این صورت تغییر می‌کند: $$ ۱۱۱۰ → ۰۱۱۱ → ۰۱۱ → ۰۱ → ۱۰ → ۰۱ $$ و در نتیجه، مقدار $Zip(1110)$ برابر با $۰۱$ می‌شود. دقت کنید که رقم سمت چپ رشتە‌ی $z$ می‌تواند صفر باشد.

به ازای همە‌ی رشتە‌های دودویی یازده رقمی ممکن، این الگوریتم چند خروجی متفاوت را برمی‌گرداند؟

1. ۱۰
2. ۱۲
3. ۲۲
4. ۵
5. ۲

بزرگ‌ترین مجموعه از رشتە‌های دودویی یازده رقمی متمایز که خروجی الگوریتم برای همە‌ی اعضایش یکسان باشد، چه اندازە‌ای دارد؟

1. ۳۳۰
2. ۲۵۲
3. ۵۰۴
4. ۹۲۴
5. ۴۶۲

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