====== سوال ۸ ======

۱۰ دانش‌آموز یک مدرسه در صفی ایستادەاند و روی سر هر کدام از آن‌ها کلاه قرمز یا آبی قرار دارد. ناظم در هر مرحله، یکی از دانش‌آموزان صف را از صف خارج کرده و به کلاس می‌فرستد. نحوەی انتخاب دانش‌آموز توسط ناظم در هر مرحله به شکل زیر است:
  * اگر تنها یک نفر در صف باشد، همان فرد انتخاب می‌شود؛ در غیر این صورت (در صورت وجود حداقل دو نفر در صف)، اگر نفر اول صف کلاه آبی و نفر دوم کلاه قرمز داشته باشند، نفر دوم صف، و در غیر این صورت، نفر اول صف انتخاب می‌شود.

پس از ۱۰ مرحله، تمام دانش‌آموزان صف به کلاس می‌روند. یک دنباله از رنگ‌های قرمز و آبی را به این صورت می‌سازیم که از یک دنباله‌ی خالی شروع می‌کنیم و به ازای هر دانش‌آموزی که از صف خارج شد، رنگ کلاه او را در انتهای دنباله اضافه می‌کنیم. به دنباله‌ی ۱۰ عنصری حاصل **دنباله‌ی سلطانی** صف می‌گوییم. تمام $2^{10}$ حالت اولیه برای رنگ کلاەهای دانش‌آموزان صف، روی هم چند دنباله‌ی سلطانی __متمایز__ تولید می‌کنند؟


  - ۱۰۲۴
  - ۵۱۳
  - ۱۴۴
  - ۵۱۲
  - ۱۲۸


<راهنمایی>
نحوه انتخاب دانش‌آموزان معادل روش زیر است:
  * اگر رنگ کلاه نفر اول صف آبی بود، نفر دوم انتخاب می‌شود.
</راهنمایی>

<راهنمایی>
اگر در مرحله iام، برای اولین بار، کلاه نفر اول آبی باشد، از مرحله iام به بعد دنباله به چه صورت است؟
</راهنمایی>

<راهنمایی>
نشان دهید که اگر حداقل یک نفر کلاه آبی داشته باشد، حتما رنگ آخر دنباله آبی خواهد بود.
</راهنمایی>


  * [[سوال ۷|سوال قبل]]
  * [[سوال ۹|سوال بعد]]