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