مسابقه‌ی تصادفی

 
 
 بازی با مهره
بازی با مهرهمسابقه كامپيوتر
مسابقه شماره ۲۴۵

 سوال


یک نوار داریم که به n خانه تقسیم شده است. خانه‌ها را به ترتیب از ۱ تا n شماره گذاری کرده‌ایم. دو عدد مهره در خانه‌های n و 
n - 1 قرار گرفته‌اند. دو بازیکن بازی زیر را انجام می‌دهند :

هر بازیکن در نوبت خود می‌تواند یکی از مهره‌ها ( هر کدام ) را برداشته و در یک خانه‌ی خالی با شماره‌ی کمتر قرار دهد. بازیکنی که آخرین حرکت را انجام دهد برنده است. در صورتی که n = 9 باشد آیا نفر اول می‌‌تواند طوری بازی کند که همیشه برنده باشد‌؟



پاسخ

لم : اولین بازیکنی که یک مهره در یکی از خانه‎های i ( که i کوچیکتر مساوی ۴ ) قرار دهد بازنده است.

اثبات : حالات زیر را در نظر می‌گیریم :

۱. بازیکن X یک مهره در خانه ۱ قرار می‌دهد در این صورت بازیکن y مهره دیگر را در خانه ۲ قرار داده و برنده می‌شود.

۲. بازیکن x یک مهره در خانه ۲ قرار می‌دهد در این صورت بازیکن y مهره دیگر را در خانه ۱ قرار داده و برنده می‌شود.

۳. بازیکن x مهره A را در خانه ۳ قرار می‌دهد. در این صورت بازیکن y مهره B را در خانه ۴ قرار می‌دهد ٫ حال اگر x یگی از مهره‌ها را در خانه ۱ ( یا ۲ ) قرار دهد ٫ آنگاه y مهره دیگر را در خانه ۲ ( یا ۱ ) قرار داده و برنده می‌شود.

۴. بازیکن x مهره A را در خانه ۴ قرار می‌دهد. در این صورت بازیکن y مهره B را در خانه ۳ قرار می‌دهد و همانند بند ۳ واضح است که y برنده می‌شود.

طریقه بازی :
 
 بازیکن اول مهره موجود در خانه شماره ۹ را در خانه ۷ قرار می‌دهد. بازیکن دوم به دو طریق زیر می‌تواند بازی کند ( با توجه به لم واضح است که اگر یکی از مهره‌ها را در یکی از خانه‌های ۱ تا ۴ قرار دهد بازنده می‌شود ) :

الف ) یکی از مهره‌ها را در خانه ۶ قرار می‌دهد. در این صورت بازیکن اول مهره دیگر را در خانه شماره ۵ قرار می‌دهد اینجاست که بازیکن دوم به ناچار یکی از مهره‌ها رو در یکی از خانه‌های ۱ تا ۴ قرار می‌دهد و با توجه به لم ٫ بازنده می‌شود.

ب ) یکی از مهره‌ها را در خانه ۵ قرار می‌دهد. در این صورت بازیکن اول مهره دیگر را در خانه شماره ۶ قرار می‌دهد. سپس بازیکن دوم به ناچار یکی از مهره‌ها را دریکی از خانه‌های ۱ تا۴ قرار داده و با توجه به لم ٫ بازنده می‌شود.
 
1392/9/29لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  4166
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  4166