Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوال ۲۲

سوال ۲۲

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

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

پاسخ

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

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

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

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

  1. یکی از مهره‌ها را در خانه‌ی ۶ قرار می‌دهد. در این صورت بازیکن اول مهره‌ی دیگر را در خانه‌ی شماره ۵ قرار می‌دهد اینجاست که بازیکن دوم به ناچار یکی از مهره‌ها را در یکی از خانه‌های ۱ تا ۴ قرار می‌دهد و با توجه به لم٬ بازنده می‌شود.
  2. یکی از مهره‌ها را در خانه‌ی ۵ قرار می‌دهد. در این صورت بازیکن اول مهره‌ی دیگر را در خانه‌ی شماره ۶ قرار می‌دهد. سپس بازیکن دوم به ناچار یکی از مهره‌ها را در یکی از خانه‌های ۱ تا ۴ قرار داده و با توجه به لم٬ بازنده می‌شود.

ابزار صفحه