Принцип Дирихле

Подсказка 1

Расположение коней нам неизвестно. Но хотелось бы выделить область, в которой коней было бы достаточно много. Для этого удобно было бы разделить квадрат на 4 одинаковые области. Как это сделать?

Подсказка 2

Верно! Можно разделить квадрат на 4 квадрата 4 × 4. По принципу Дирихле в одном из них будет не менее 9 коней. Попробуем теперь доказать, что в этом квадрате два коня бьют друг друга. Можно ли и эту область разбить на несколько других так, чтобы два коня в одной из областей наверняка били друг друга?

Подсказка 3

Разобьем квадрат на 4 группы клеток по следующему признаку: каждая группа состоит из четырех клеток, являющимися последовательными ходами коня. Легко проверить, что квадрат разбивается таким образом полностью. Тогда в одной из этих четырех групп не менее трех коней. Найдутся ли 2, которые бьют друг друга?