Разделы 
Дополнительно
Задача по математике - 3317
2019-06-02 
Какое наибольшее число коней можно расставить на доске $5 \times 5$ клеток так, чтобы каждый из них бил ровно двух других? (Приведите пример и объясните, почему больше коней расставить нельзя.)
Решение:
На рис. приведено расположение 16 коней, удовлетворяющее условию задачи. Покажем, что большее число коней расставить нельзя. Раскрасим клетки доски в черный и белый цвета, как показано на рис. Заметим, что количество коней, расположенных на черных клетках, равно количеству коней, расположенных на белых клетках. Действительно, если соединить отрезками бьющих друг друга коней, то каждый отрезок будет соединять белую клетку с черной. С другой стороны, из каждой клетки выходит два отрезка. Значит, число отрезков равно удвоенному числу коней, стоящих на белых клетках, и удвоенному числу коней, стоящих на черных клетках. Поэтому число коней, стоящих на белых клетках, равно числу коней, стоящих на черных клетках.
Белых клеток всего 12, а черных - 13. Значит, если число пустых белых клеток равно $n$, то число пустых черных клеток равно $n + 1$, и нам достаточно доказать, что $n \geq 4$ (тогда по крайней мере $4 + (4 + 1) = 9$ клеток пусты).
При любом оптимальном расположении коней центральная клетка пуста. В противном случае из восьми клеток, которые бьет конь, стоящий на центральном поле, ровно шесть пустых белых. Отсюда $n \geq 6$, и число коней не превосходит $25 - 6 - (6 + 1) = 12$.
Рассмотрим клетку, обозначенную на рисунке 117 цифрой 1. Если на этой клетке стоит конь, то 4 из 6 черных клеток, которые она бьет, пусты. По доказанному центральная клетка тоже пуста. Значит, по крайней мере 5 черных клеток пусты, и все доказано. Поэтому можно считать, что эта клетка пуста. Аналогично, можно считать, что клетки 2, 3 и 4 пусты. Но тогда $n \geq 4$, что и требовалось.
Ответ: 16 коней.
Какое наибольшее число коней можно расставить на доске $5 \times 5$ клеток так, чтобы каждый из них бил ровно двух других? (Приведите пример и объясните, почему больше коней расставить нельзя.)
Решение:
На рис. приведено расположение 16 коней, удовлетворяющее условию задачи. Покажем, что большее число коней расставить нельзя. Раскрасим клетки доски в черный и белый цвета, как показано на рис. Заметим, что количество коней, расположенных на черных клетках, равно количеству коней, расположенных на белых клетках. Действительно, если соединить отрезками бьющих друг друга коней, то каждый отрезок будет соединять белую клетку с черной. С другой стороны, из каждой клетки выходит два отрезка. Значит, число отрезков равно удвоенному числу коней, стоящих на белых клетках, и удвоенному числу коней, стоящих на черных клетках. Поэтому число коней, стоящих на белых клетках, равно числу коней, стоящих на черных клетках.
Белых клеток всего 12, а черных - 13. Значит, если число пустых белых клеток равно $n$, то число пустых черных клеток равно $n + 1$, и нам достаточно доказать, что $n \geq 4$ (тогда по крайней мере $4 + (4 + 1) = 9$ клеток пусты).
При любом оптимальном расположении коней центральная клетка пуста. В противном случае из восьми клеток, которые бьет конь, стоящий на центральном поле, ровно шесть пустых белых. Отсюда $n \geq 6$, и число коней не превосходит $25 - 6 - (6 + 1) = 12$.
Рассмотрим клетку, обозначенную на рисунке 117 цифрой 1. Если на этой клетке стоит конь, то 4 из 6 черных клеток, которые она бьет, пусты. По доказанному центральная клетка тоже пуста. Значит, по крайней мере 5 черных клеток пусты, и все доказано. Поэтому можно считать, что эта клетка пуста. Аналогично, можно считать, что клетки 2, 3 и 4 пусты. Но тогда $n \geq 4$, что и требовалось.
Ответ: 16 коней.
