المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۲۷ و ۲۸

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

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

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

سوال ۲۷

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

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

پاسخ

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

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

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

سوال ۲۸

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

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

پاسخ

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

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

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

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


ابزار صفحه