سوال ۳

می‌خواهیم ۷ رقم ۰ و ۱ را دور دایره بچینیم. می‌گوییم رشته‌ی $S$ در این چینش آمده است، اگر چند رقم متوالی در دایره وجود داشته باشند که با کنار هم قرار دادن‌شان به ترتیب ساعت‌گرد، رشته‌ی $S$ تشکیل شود. تعداد دفعات وجود $S$ در چینش را $f(S)$ می‌نامیم. برای مثال، در چینش روبرو، $f(110)=1$ و $f(11) = 3$ و $f(01110) = 0$ است.

یک چینش اعداد دور دایره را در نظر بگیرید. به ازای هر رشته‌ی دودویی $S$ که حداکثر ۳ رقم دارد، $2^{f(S)}$ را محاسبه می‌کنیم و این مقادیر را با هم جمع می‌کنیم (به عنوان مثال در شکل مقابل این عدد برابر 70 می‌شود). عدد نهایی حداقل چند است؟ (برای رشته‌هایی که در چینش وجود ندارند $f(S) = 0$ است.)

  1. ۶۳
  2. ۵۶
  3. ۵۳
  4. ۵۵
  5. ۵۱

پاسخ

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

به ازای رشته‌های یک رقمی بهترین حالت این است 4 تا از اعداد یکسان باشند.

به ازای رشته‌های دو رقمی بهترین حالت این است که از سه حالت 2 بار و از یک حالت 1 بار وجود داشته باشد.

و در نهایت به ازای رشته‌های سه رقمی بهترین حالت این است که از هر حالت حداکثر یک بار آمده باشد و از یک رشته اصلا نیاید.

اگر دنباله دور دایره به صورت 1110010 باشد به چنین حالتی می‌رسیم و در نتیجه این جواب بهینه است. با محاسبه‌ی مجموع اعداد فوق عدد 53 بدست می‌آید که پاسخ مسئله است.