Олимпиадная задача про шахматных коней на доске 5×5 – докажите уникальность
Задача
На клетчатой доске 5×5 расставили максимальное число шахматных коней так, чтобы они не били друг друга.
Докажите, что такая расстановка единственна.
Решение
Пример. Рассмотрим шахматную раскраску доски, при которой центральное поле чёрное. Ясно, что 13 коней на чёрных полях друг друга не бьют.
Оценка. Рассмотрим обход доски конем (на рисунке клетки занумерованы в порядке обхода). Ослабим условие: будем требовать только, чтобы кони не стояли на клетках с соседними номерами. Тогда между каждой парой занятых конями номеров должен быть промежуток из одного или нескольких свободных номеров.

Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет