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