المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

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

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

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

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

  • اگر ‎$b-a>1$‎ مهره‌اش را یا یک یا دو واحد به چپ ببرد.
  • ‎اگر ‎$b-a=1$‎ مهره‌ی افروز را بزند و برنده شود.
  • ‎اگر ‎$b\leq a$‎ مهره‌ی خود را دقیقا یک واحد به چپ ببرد‎.‎

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


ابزار صفحه