Задача 98370

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

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

Условие

Автор: Канель-Белов А.Я.

На клетчатой доске 5×5 расставили максимальное число шахматных коней так, чтобы они не били друг друга.
Докажите, что такая расстановка единственна.

 

Решение

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

  Максимальное число коней получится в единственном случае: 1-я и 25-я клетки заняты конями, а каждый промежуток состоит из одной клетки, то есть кони стоят на всех "нечётных" (то есть чёрных) клетках.

Замечания

4 балла

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

олимпиада
Название	Турнир городов
Турнир
Дата	1997/1998
Номер	19
вариант
Вариант	осенний тур, тренировочный вариант, 10-11 класс
Задача
Номер	4