مسابقه شماره ۲۳۶
سوال
بازی یک نفره «کوئیدیچ» به شکل زیر انجام می‌شود :
یک صفحه 4 × 4 که همه 16 خانه آن سفید هستند در اختیار داریم.
در هر حرکت , یک خانه را انتخاب می‌کنیم.
با انتخاب هر خانه , رنگ آن خانه و همه خانه‌هایی که در بالا و سمت راست آن هستند عوض می‌شود ( از سفید به سیاه یا از سیاه به سفید تغییر می‌یابد ).
مثلا در شکل بالا با انتخاب خانه دوم از ردیف سوم , رنگ بعضی از خانه‌ها سیاه شده است.
می‌خواهیم با k بار انجام این حرکت , صفحه را به صورت شطرنجی درآوریم ( یعنی رنگ هیچ دو خانه‌ای که در یک ضلع مشترکند , یکی نباشد). کمترین مقدار k چقدر است ؟
پاسخ
اگر خانه‌هایی با مختصات (2 , 1) , (3 , 1) , (4 , 1) , (1 , 2) , (1 , 3) , (1 , 4) را به ترتیب انتخاب کنید صفحه شطرنجی خواهد شد.
لازم به ذکر است که انتخاب هر یک از آن خانه‌ها الزامی است , زیرا خانه‌ای مانند (2 , 1) را فقط انتخاب خودش می‌تواند تغییر رنگ دهد.