سوال ۳
می‌خواهیم ۷ رقم ۰ و ۱ را دور دایره بچینیم. می‌گوییم رشته‌ی $S$ در این چینش آمده است، اگر چند رقم متوالی در دایره وجود داشته باشند که با کنار هم قرار دادن‌شان به ترتیب ساعت‌گرد، رشته‌ی $S$ تشکیل شود. تعداد دفعات وجود $S$ در چینش را $f(S)$ می‌نامیم. برای مثال، در چینش روبرو، $f(110)=1$ و $f(11) = 3$ و $f(01110) = 0$ است.
یک چینش اعداد دور دایره را در نظر بگیرید. به ازای هر رشته‌ی دودویی $S$ که حداکثر ۳ رقم دارد، $2^{f(S)}$ را محاسبه می‌کنیم و این مقادیر را با هم جمع می‌کنیم (به عنوان مثال در شکل مقابل این عدد برابر 70 می‌شود). عدد نهایی حداقل چند است؟ (برای رشته‌هایی که در چینش وجود ندارند $f(S) = 0$ است.)
- ۶۳
- ۵۶
- ۵۳
- ۵۵
- ۵۱
پاسخ
گزینه (۳) درست است.
به ازای رشته‌های یک رقمی بهترین حالت این است 4 تا از اعداد یکسان باشند.
به ازای رشته‌های دو رقمی بهترین حالت این است که از سه حالت 2 بار و از یک حالت 1 بار وجود داشته باشد.
و در نهایت به ازای رشته‌های سه رقمی بهترین حالت این است که از هر حالت حداکثر یک بار آمده باشد و از یک رشته اصلا نیاید.
اگر دنباله دور دایره به صورت 1110010 باشد به چنین حالتی می‌رسیم و در نتیجه این جواب بهینه است. با محاسبه‌ی مجموع اعداد فوق عدد 53 بدست می‌آید که پاسخ مسئله است.