Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:تئوری نهایی سوم:سوال ۱

سوال ۱

در حالیکه هنوز پس از گذشت بیش از نیم قرن از کنار گذاشته شدن آب‌بازی می‌گذرد هنوز عده‌ای در مکان‌های دور دست باشگاه این کار ناپسندیده را ترک نمی‌کنند. حال افروز و علیرضا که بسیار عاقلند این بازی را انجام می‌دهند:

در یک جدول 2×n ( دو سطر و ‎n‎‎ ستون) افروز سربازی در خانه‌ی ‎(1,1)‎ و علیرضا سربازی در خانه‌ی ‎(2,n)‎ دارد. با شروع از افروز به نوبت هر کس یک حرکت می‌کند. اگر مهره ی افروز در خانه‌ی ‎(1,a)‎ و مهره‌ی علیرضا در خانه‌ی ‎(2,b)‎ باشد، افروز در نوبت خود می‌تواند این کارها را بکند:

  • ‎اگر ‎ba>1‎ مهره‌اش را یا یک یا دو واحد به راست ببرد‎.‎
  • ا‎گر ‎ba=1‎ مهره‌ی علیرضا را بزند و برنده شود.
  • ‎اگر ‎ba‎ مهره‌ی خود را دقیقا یک واحد به راست ببرد.‎

علیرضا نیز در نوبت خود می تواند این کار ها را بکند:‎

  • اگر ‎ba>1‎ مهره‌اش را یا یک یا دو واحد به چپ ببرد.
  • ‎اگر ‎ba=1‎ مهره‌ی افروز را بزند و برنده شود.
  • ‎اگر ‎ba‎ مهره‌ی خود را دقیقا یک واحد به چپ ببرد‎.‎

اگر هم مهره‌ای زده نشد هرکس زودتر به ستون آخر برسد برنده است‎ (ستون آخر برای افروز ستون ‎n‎ام و برای علیرضا ستون ‎۱‎ است). چه کسی می تواند برنده‌ی بازی و رییس انجمن گراف شود؟


ابزار صفحه