المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

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

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


ابزار صفحه