المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۱:سوال یک

جدول بازی (۲۴ نمره)

امید و دخترش فرناز بازی زیر را در یک جدول $𝑛×𝑛$ انجام میدهند:

امید بازی را شروع میکند. هر کس در هر نوبت خود در طول بازی، یکی از خطوط جدول (یکی از $𝑛+1$ خط عمودی یا یکی از $𝑛+1$ خط افقی) ‫را به طور کامل پاک میکند. در ابتدای بازی، همه ی ${𝑛^2}$ خانه ی ۱×۱ جدول سالم هستند، اما پس از هر نوبت ممکن است تعدادی از خانه های سالم به دلیل پاک شدن یکی از ضلع هایشان خراب شوند(واضح است خانه ای که خراب شده است تا انتها خراب باقی می ماند).وضعیت جدول را ویران می نامیم ،اگر تمام ${𝑛^2}$ خانه ی ۱×۱ از جدول اولیه خراب شده باشند. به محض این که جدول ویران شود، بازی به پایان می رسد. میگوییم یک بازیکن استراتژی برد دارد اگر بتواند به نحوی بازی کند که مستقل از حرکات نفر مقابل همیشه برنده ی بازی باشد.

الف) در این بخش، کسی که آخرین حرکت بازی را انجام دهد بازنده ی بازی میشود. چه کسی استراتژی برد دارد؟ (۱۰نمره)

ب) در این بخش، کسی که آخرین حرکت بازی را انجام دهد برنده ی بازی میشود. چه کسی استراتژی برد دارد؟ (۱۴نمره)


ابزار صفحه