====== سوال ۳ ======

{{:سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۵:selection_080.png |}}
می‌خواهیم ۷ رقم ۰ و ۱ را دور دایره بچینیم. می‌گوییم رشته‌ی $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 بدست می‌آید که پاسخ مسئله است.

</پاسخ>
  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]