Задача 105077

Темы:    [ Шахматные доски и шахматные фигуры ] [ Шахматная раскраска ] [ Степень вершины ] [ Примеры и контрпримеры. Конструкции ] [ Перебор случаев ]

Сложность: 4+ Классы: 7,8,9,10

Условие

Автор: Горелов М.В.

Какое наибольшее число коней можно расставить на доске 5×5 клеток так, чтобы каждый из них бил ровно двух других?

Решение

  Пример. На рис. приведено расположение 16 коней, удовлетворяющее условию задачи.

  Оценка. Предположим, что нам удалось расставить более 16 коней. Раскрасим доску в шахматном порядке (см. рис.), а коней – в цвет клеток, на которых они стоят. Так как каждый белый конь бьёт двух чёрных, а каждый чёрный – двух белых, то количество чёрных и белых коней одинаково (каждых не меньше девяти). Таким образом, свободно не более трёх белых и не более четырёх чёрных клеток. Поэтому на центральной клетке конь стоять не может (иначе из восьми битых им белых клеток шесть будут свободны).
  Так как свободно не более трёх белых клеток, то по крайней мере один белый конь стоит на клетке, соседней с центральной. Но оттуда он бьёт шесть чёрных клеток. Значит, четыре из них пусты. Вместе с центральной мы получаем пять пустых чёрных клеток. Противоречие.

Ответ

16 коней.

Замечания

7 баллов

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	2000
выпуск
Номер	1
Задача
Номер	М1716
олимпиада
Название	Московская математическая олимпиада
год
Номер	63
Год	2000
вариант
Класс	8
задача
Номер	6
олимпиада
Название	Турнир городов
Турнир
Дата	1999/2000
Номер	21
вариант
Вариант	весенний тур, основной вариант, 8-9 класс
Задача
Номер	5