Задача 98512

Темы:    [ Шахматные доски и шахматные фигуры ] [ Четность и нечетность ] [ Инварианты ]

Сложность: 4- Классы: 10,11

Условие

На доске размером 15×15 клеток расставили 15 ладей, не бьющих друг друга. Затем каждую ладью передвинули ходом коня.
Докажите, что теперь какие-то две ладьи будут бить друг друга.

Решение

Введём на доске "систему координат": занумеруем горизонтали и вертикали числами от 1 до 15. Если ладьи не бьют друг друга, то в каждой горизонтали и в каждой вертикали находится ровно одна ладья, поэтому сумма координат всех ладей равна  2(1 + 2 + ... + 15),  то есть чётна. Когда ладья передвинута ходом коня, сумма её координат изменяется на 1 или на 3, то есть меняет чётность. Так как количество ладей нечётно, после перестановки сумма координат всех ладей нечётна. Следовательно, некоторые ладьи бьют друг друга.

Замечания

5 баллов

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

олимпиада
Название	Турнир городов
Турнир
Дата	2000/2001
Номер	22
вариант
Вариант	весенний тур, тренировочный вариант, 8-9 класс
Задача
Номер	5