Задача из журнала «Квант» (2000 год, 4 выпуск)
Условие
Какое наибольшее число коней можно расставить на доске $5\times5$ так, чтобы каждый из них бил ровно двух других?
Решение
На рисунке $1$ приведено расположение $16$ коней, удовлетворяющее условию задачи. Покажем, что большее число коней расставить нельзя. Заметим, что количество коней, расположенных на черных клетках, равно количеству коней, расположенных на белых клетках. Значит, если число пустых белых клеток равно $n$, то число пустых черных клеток равно $n+1$.
Заметим, что для оптимального расположения коней центральная клетка пуста, так как в противном случае из восьми клеток, которые бьет конь, стоящий на центральном поле, ровно шесть пустых белых. Отсюда $n\geqslant6$, и число коней не превосходит $25-n-(n+1)\leqslant12$.
Разобьем белые клетки на четыре группы так, как показано на рисунке $2$ (клетки одной группы отмечены одинаковыми цифрами). Покажем, что для оптимального расположения по крайней мере одна клетка каждой группы пуста, отсюда будет следовать, что $n\geqslant4$ . Предположим противное: например, что на всех клетках группы $3$ стоят кони. Обозначим их буквами $a$, $b$ и $с$ (рис.3). Конь, стоящий на клетке $а$, бьет клетки $f$, $d$ и центральную. Но, как было показано выше, центральная клетка пуста, значит, на клетках $f$ и $d$ стоят кони.
Аналогично можно показать, что на клетках $e$ и $g$ тоже стоят кони. Но тогда конь, стоящий на клетке $c$, бьет четырех коней, расположенных на $d$, $e$, $f$ и $g$, что противоречит условию.
Итак, число пустых белых клеток $n\geqslant4$. Значит, число коней не больше
$25-n-(n+1)\leqslant12$.
Ответ: $16$.
М. Горелов
