سوال ۸
۱۰ دانش‌آموز یک مدرسه در صفی ایستادەاند و روی سر هر کدام از آن‌ها کلاه قرمز یا آبی قرار دارد. ناظم در هر مرحله، یکی از دانش‌آموزان صف را از صف خارج کرده و به کلاس می‌فرستد. نحوەی انتخاب دانش‌آموز توسط ناظم در هر مرحله به شکل زیر است:
- اگر تنها یک نفر در صف باشد، همان فرد انتخاب می‌شود؛ در غیر این صورت (در صورت وجود حداقل دو نفر در صف)، اگر نفر اول صف کلاه آبی و نفر دوم کلاه قرمز داشته باشند، نفر دوم صف، و در غیر این صورت، نفر اول صف انتخاب می‌شود.
پس از ۱۰ مرحله، تمام دانش‌آموزان صف به کلاس می‌روند. یک دنباله از رنگ‌های قرمز و آبی را به این صورت می‌سازیم که از یک دنباله‌ی خالی شروع می‌کنیم و به ازای هر دانش‌آموزی که از صف خارج شد، رنگ کلاه او را در انتهای دنباله اضافه می‌کنیم. به دنباله‌ی ۱۰ عنصری حاصل دنباله‌ی سلطانی صف می‌گوییم. تمام $2^{10}$ حالت اولیه برای رنگ کلاەهای دانش‌آموزان صف، روی هم چند دنباله‌ی سلطانی متمایز تولید می‌کنند؟
- ۱۰۲۴
- ۵۱۳
- ۱۴۴
- ۵۱۲
- ۱۲۸
راهنمایی
نحوه انتخاب دانش‌آموزان معادل روش زیر است:
- اگر رنگ کلاه نفر اول صف آبی بود، نفر دوم انتخاب می‌شود.
راهنمایی
اگر در مرحله iام، برای اولین بار، کلاه نفر اول آبی باشد، از مرحله iام به بعد دنباله به چه صورت است؟
راهنمایی
نشان دهید که اگر حداقل یک نفر کلاه آبی داشته باشد، حتما رنگ آخر دنباله آبی خواهد بود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
