Задача
Какое наибольшее число коней можно расставить на шахматной доске так, чтобы каждый бил не более семи из остальных?
Решение
Пример расстановки 60 коней: заняты все клетки, кроме клеток центрального квадрата 2×2.
Покажем, что при удовлетворяющей условию расстановке не менее четырёх клеток останутся свободными (то есть больше 60 коней расставить не удастся). Рассмотрим центральный квадрат 4×4. Если в нём четыре поля свободны, все доказано.
Пусть свободных полей в нем не больше трёх, тогда коней там не меньше 13. Каждый из них атакует 8 клеток доски, хотя бы одна из которых свободна. Легко проверить, что фиксированную клетку кони, стоящие в центральном квадрате, атакуют не более четырёх раз. Следовательно, свободных клеток не меньше 13 : 4 > 3, то есть не меньше 4.
Ответ
60 коней.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь