Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:ترکیبیات:سوال ۱

سوال ۱

تعدادی سنگریزه وجود دارد که دو نفر مشغول بازی با آن‌ها هستند. ما از قوانین بازی آن‌ها اطلاع دقیقی نداریم، ولی می‌دانیم مجموعه‌ی ‎S={1,a1,...,at}‎ وجود دارد که همه اعضای آن از عدد طبیعی ‎k (از این عدد آگاه هستیم) کمتر هستند و هر بازیکن در نوبت خود یکی از اعضای ‎S‎ را انتخاب می‌کند و به تعداد آن سنگریزه برمی‌دارد. همچنین هر کسی که نتواند حرکتی انجام دهد بازنده است‎.

ما می‌توانیم عددی مثل ‎n‎ را انتخاب کنیم و از آن‌ها بپرسیم که استراتژی برد به ازای ‎n‎ سنگریزه با چه کسی است. ثابت کنید با متناهی پرسش می‌توان استراتژی برد به ازای همه اعداد را یافت.


ابزار صفحه