سوال ۶

برای اینکه نشان دهیم جواب برابر با $k$ است، باید دو چیز را نشان دهیم:

• راهی وجود دارد که با $k$ مرحله تمام نقاط را سفید کنیم.
• هیچ راهی وجود ندارد که با کمتر از $k$ مرحله بتوانیم تمام نقاط را سفید کنیم.

سعی کنید یک کران بالا و یک کران پایین برای جواب پیدا کنید و کران‌های بالا و پایین را به هم نزدیک کنید.

برای اثبات کران پایین، دقت کنید که هیچ امینکی وجود ندارد که شامل یکی از خانه‌های گوشه‌ای شبکه شود.

برای ارائه کران پایین بهتر، به نقاط قرمز شکل زیر توجه کنید: هیچ امینکی وجود ندارد که شامل بیشتر از یکی از این نقاط باشد.
به این ترتیب توانستیم ثابت کنیم که برای سفید کردن همه‌ی نقاط به حداقل $8$ مرحله نیاز داریم. اگر همین روش را ادامه دهیم، کران پایین را چقدر می‌توانیم افزایش دهیم؟