مسابقهي شمارهي 116
هوش و خلاقيت
يك بيماري واگيردار در يك صفحهي شطرنجي nدرn در حال انتشار است. اين بيماري بهگونهي زير منتشر ميشود: اگر خانهاي داراي دو يا بيشتر همسايهي بيمار باشد، آنگاه اين خانه نيز بيمار ميشود. (دو خانه تنها در صورتي با هم همسايه هستند كه در يك ضلع مشترك باشند.)
مثلاً اگر در ابتدا فقط قطر صفحهي شطرنجي بيمار باشد، خانههاي مجاور قطر نيز بيمار ميشوند و سپس بيماري به همهي خانهها سرايت ميكند:
ثابت كنيد براي سرايت اين بيماري به همهي خانهها، در ابتدا بايستي حداقل n خانه بيمار باشند.