المپدیا

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

ابزار کاربر

ابزار سایت


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

رنگین مسیر

بازی «رنگین‌مسیر» یک بازی ۲ نفره است که روی یک صفحه‌ی $۴ \times n$ (۴ سطر و $n$ ستون) که در ابتدا سفید رنگ است انجام می‌شود. بهروز و حمید مشغول انجام این بازی هستند و به نوبت طبق قوانین بازی حرکت می‌کنند. بهروز از رنگ آبی و حمید از رنگ قرمز استفاده می‌کند. بازی به این صورت انجام می‌شود که بهروز در هر مرحله دو خانه‌ی سفید رنگی که در یک ضلع با هم مشترک هستند و تشکیل یک مستطیل $۱ \times ۲$ (۱ سطر و ۲ ستون) می‌دهند را انتخاب می‌کند و آن‌ها را به رنگ خود (آبی) در می‌آورد. حمید نیز در نوبت خود دو خانه‌ی سفید رنگی که در در یک ضلع با هم مشترک باشند و تشکیل یک مستطیل $۲ \times ۱$ (۲ سطر و ۱ ستون) بدهند را انتخاب می‌کند و آن‌ها را به رنگ خود (قرمز) در می‌آورد. اگر کسی نتواند در نوبت خود حرکت کند (یعنی نتواند دو خانه‌ی مجاور با شرایط گفته شده پیدا کند) نوبت بازی به نفر مقابل می‌رسد و اگر هیچ یک از دو نفر قادر به انجام حرکت نباشند بازی تمام می‌شود.

در پایان اگر دنباله‌ای از خانه‌های آبی وجود داشته باشد که هر کدام در یک ضلع با خانه‌ی بعدی مشترک باشد و اولین خانه در ستون اول جدول و آخرین خانه در ستون آخر قرار داشته باشد٬ در این صورت بهروز برنده‌ی بازی است.

اگر دنباله‌ای از خانه‌های قرمز وجود داشته باشد که هر کدام در یک ضلع با خانه‌ی بعدی مشترک باشد و اولین خانه در ستون اول جدول و آخرین خانه در ستون آخر قرار داشته باشد٬ در این صورت حمید برنده‌ی بازی است.

اگر هیچ‌یک از دو حالت فوق اتفاق نیفتد٬ بازی مساوی می‌شود. با فرض این که هر دو نفر به بهترین نحو ممکن بازی می‌کنند٬ به ازای هر $۷ \le n$ :

الف) اگر حمید شروع‌کننده‌ی بازی باشد٬ چه کسی بازی را می‌برد؟

ب) اگر بهروز شروع‌کننده‌ی بازی باشد٬ چه کسی بازی را می‌برد؟


ابزار صفحه