المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۴:سوال ۳۸

سوال ۳۸

دو سینی داریم که در یکی از آن‌ها ۱۰ بشقاب روی هم چیده شده و سینی دیگر خالی است. هر بشقاب٬ یکی از ۵ رنگ را دارد و هر رنگ دقیقاً دو بار آمده است. در یک حرکت٬ می‌توان هر کدام از بشقاب‌های سینی اول را برداشت و روی بشقاب‌های موجود در سینی دوم گذاشت. توجه شود که این بشقاب را فقط روی بشقاب‌های سینی دوم می‌توان قرار داد٬ و نمی‌توانیم زیر بشقاب دیگری قرار دهیم.

هدف این است که بعد از ۵ حرکت٬ رنگ بشقاب‌های دو سینی به ترتیب از پایین به بالا دقیقاً یکسان شود. به چند طریق می‌توان این کار را انجام داد؟

  1. ۳۲
  2. ۶۴
  3. ۱۲۰
  4. ۲۵۲
  5. بستگی به وضعیت ابتدایی دارد.

پاسخ

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

فرض کنید بعد از مراحلی در مورد رنگ خاصی که در بشقاب $a$ و $b$ مربوط به آن رنگ است٬ بشقاب $a$ پایین‌تر از بشقاب $b$ باشد٬ به‌طور مستقل از سایر عملکردها دو کار می‌توان انجام داد٬ یکی آن که بشقاب $b$ را به سینی دوم برد و یا تکلیف تمام بشقاب‌های بین $a$ و $b$ را مشخص کرد و سپس بشقاب $a$ را (که احتمالا در زیر چند بشقاب جا مانده است)به سینی دوم منتقل کنیم. بنابراین طبق اصل ضرب جواب مورد نظر $2^5$ یعنی ۳۲ خواهد شد.


ابزار صفحه