سؤال ۲۹
در یک جدول، دو خانه را همسایه می‌گوییم اگر در یک نقطه یا در یک ضلع اشتراک داشته باشند (بنابراین، هر خانه حداکثر ۸ همسایه دارد). می‌خواهیم در یک جدول $۱۰×۱۰$، $k$ خانه را علامت بزنیم به‌طوری که هر خانه‌ی علامت نخورده حداقل یک همسایه علامت خورده داشته باشد. $k$ حداقل چه قدر است؟
- ۱۳
- ۱۴
- ۱۵
- ۱۶
- ۱۷
پاسخ
گزینه (۴) درست است.
اگر جدول را مطابق شکل٬ به ۱۶ ناحیه افراز کنیم آن‌گاه معلوم می‌شود که وجود حداقل یک خانه علامت‌دار در هر ناحیه الزامی است. بنابراین وجود حداقل ۱۶ خانه علامت‌دار حتمی است. در شکل با ۱۶ خانه علامت‌دار به منظور مسئله رسیده‌ایم:
