المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوالات ۲۷ و ۲۸

سوالات ۲۷ و ۲۸

نازخیکول یک کیسه شامل ۲۲ تیله سفید و ۳۳ تیله سیاه دارد. تا زمانی که بیش از ۱ تیله در کیسه وجود داشته باشد، در هر مرحله نازخیکول بدون نگاه کردن به تیله‌ها دو تیله را به صورت تصادفی از کیسه خارج می‌کند و با توجه به رنگ آن ها، یکی از اعمال زیر را انجام می‌دهد:

  • اگر هر دو تیله سفید بودند، هر دو تیله را دور می اندازد.
  • اگر هر دو تیله سیاه بودند، یک تیله را دور می‌اندازد و دیگری را به کیسه باز می‌گرداند.
  • اگر یک تیله سفید و یک تیله سیاه بود، تیله سفید را به کیسه بر می‌گرداند و تیله سیاه را دور می‌اندازد.

با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید:

سوال ۲۷

حداقل و حداکثر چند مرحله طول می کشد تا نازخیکول متوقف شود( زمانی که حداکثر ۱ تیله در کیسه وجود داشته باشد)؟

  1. ۴۵٬۴۳
  2. ۴۴٬۴۴
  3. ۴۵٬۴۴
  4. ۴۴٬۴۳
  5. ۴۳٬۴۳

راهنمایی

دقت کنید برای حذف یک مهره‌ی سیاه حداقل یک گام اخصاصا نیاز است.

راهنمایی

سه حالت نهایی ممکن را در نظر گیرید. هیچ مهره‌ای باقی نماند، یک مهره‌ی سفید باقی بماند و یک مهره‌ی سیاه باقی بماند.

پاسخ

گزینه‌ی ۴ درست است.

تنها در صورتی که دو تیله‌ی سفید بیرون آورده شود، دو تیله از کیسه حذف می‌شود. در نتیجه حداکثر ۱۱ بار این اتفاق خواهد افتاد. در بقیه حالات نیز یک تیله حذف می‌شود. در ابتدا ۵۵ تیله و در انتها حداکثر ۱ تیله خواهد ماند. در نتیجه حداقل ۴۳ مرحله نیاز است. اگر در ۱۱ مرحله‌ی اول تیله‌ی سفید از کیسه بیرون آید این حالت اتفاق می‌افتد.

از طرفی در انتها هیچ تیله‌ی سفیدی در کیسه نیست (چون تعداد تیله‌های سفید همواره زوج هستند). در نتیجه دقیقا ۱۱ بار دو تیله حذف شده است. در ابتدا ۵۵ تیله و در انتها می‌تواند تیله‌ای در کیسه نماند، پس حداکثر ۴۴ مرحله نیاز است. اگر تا زمانی که تیله‌ی سیاه در کیسه است تیله‌ی سفید و سیاه از کیسه بیرون آید این حالت اتفاق خواهد افتاد.

سوال ۲۸

کدام گزاره در مورد حالت نهایی درست است؟

  1. در حالت پایانی حتما یک تیله سیاه در کیسه وجود دارد
  2. کیسه حتما خالی می شود
  3. در صورت خالی نشدن کیسه٬ رنگ تیله پایانی حتما سیاه است
  4. در حالت پایانی حتما یک تیله سفید در کیسه وجود دارد
  5. هیچکدام

راهنمایی

در چه صورتی تیله‌ی سفیدی از کیسه حذف می‌شود؟

راهنمایی

ایا ممکن است در یک لحظه، فرد تیله‌ی سفید داشته باشیم؟

راهنمایی

گزینه‌های اول، دوم و چهارم را می‌توانید بنا بر سوال‌های پیشین حذف کنید.

پاسخ

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

با توجه به روش ذکرشده در مرحله‌ی قبل دو حالت برای انتهای بازی وجود دارد:

  • یک تیله‌ی سیاه در کیسه بماند.
  • هیچ تیله‌ای در کیسه نماند.

در نتیجه در بین گزینه‌های سوال، تنها گزینه‌ی ۳ صحیح است.


ابزار صفحه