سوال ۲۲
یک نوار داریم که به $n$ خانه تقسیم شده است. خانه‌ها را به ترتیب از ۱ تا $n$ شماره‌گذاری کرده‌ایم. دو عد مهره در خانه‌های $n$ و $n-1$ قرار گرفته‌اند. دو بازیکن بازی زیر را انجام می‌دهند:
هر بازیکن در نوبت خود می‌تواند یکی از مهره‌ها(هرکدام) را برداشته و در یک خانه‌ی خالی با شماره‌ي کم‌تر قرار دهد. بازیکنی که آخرین حرکت را انجام دهد برنده است. در صورتی که $n=9$ باشد آیا نفر اول می‌تواند طوری بازی کند که همیشه برنده باشد؟
پاسخ
لم: اولین بازیکنی که یک مهره در یکی از خانه‌های $(i \leq 4)i$ قرار دهد بازنده است.
اثبات: حالات زیر را در نظر می‌گیریم:
- بازیکن $x$ یک مهره در خانه‌ی ۱ قرار می‌هد در این صورت بازیکن $y$ مهره‌ی دیگر را در خانه‌ی ۲ قرار داده و برنده می‌شود.
- بازیکن $x$ یک مهره در خانه‌ی ۲ قرار می‌دهد. در این صورت بازیکن $y$ مهره‌ی دیگر را در خانه‌ی ۱ قرار داده و برنده می‌شود.
- بازیکن $x$ مهره‌ی $A$ را در خانه‌ی ۳ قرار می‌دهد. در این صورت بازیکن $y$ مهره‌ی $B$ را در خانه‌ی ۴ قرار می‌دهد٬ حال اگر $x$ یکی از مهره‌ها را در خانه‌ی ۱(یا ۲) قرار دهد٬ آن‌گاه $y$ مهره‌ی دیگر را در خانه‌ی ۲(یا ۱) قرار داده و برنده می‌شود.
- بازیکن $x$ مهره‌ی $A$ را در خانه‌ی ۴ قرار می‌دهد. در این صورت بازیکن $y$ مهره‌ی $B$ را در خانه‌ی ۳ قرار می‌دهد و همانند بند ۳ واضح است که $y$ برنده می‌شود.
طریقه‌ی بازی: بازیکن اول مهره‌ی موجود در خانه‌ی شماره ۹ را در خانه‌ی ۷ قرار می‌دهد. بازیکن دوم به دو طریق زیر می‌تواند بازی کند( با توجه به لم واضح است که اگر یکی از مهره‌ها را در یکی از خانه‌های ۱ تا ۴ قرار دهد بازنده می‌شود):
- یکی از مهره‌ها را در خانه‌ی ۶ قرار می‌دهد. در این صورت بازیکن اول مهره‌ی دیگر را در خانه‌ی شماره ۵ قرار می‌دهد اینجاست که بازیکن دوم به ناچار یکی از مهره‌ها را در یکی از خانه‌های ۱ تا ۴ قرار می‌دهد و با توجه به لم٬ بازنده می‌شود.
- یکی از مهره‌ها را در خانه‌ی ۵ قرار می‌دهد. در این صورت بازیکن اول مهره‌ی دیگر را در خانه‌ی شماره ۶ قرار می‌دهد. سپس بازیکن دوم به ناچار یکی از مهره‌ها را در یکی از خانه‌های ۱ تا ۴ قرار داده و با توجه به لم٬ بازنده می‌شود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
