Задано несколько красных и несколько синих точек. Некоторые из них соединены отрезками. Назовём точку «особой», если более половины из соединённых с ней точек имеют цвет, отличный от её цвета. Если есть хотя бы одна особая точка, то выбираем любую особую точку и перекрашиваем в другой цвет. Докажите, что через конечное число шагов не останется ни одной особой точки.

   Решение

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

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

Прислать комментарий

Условие

Шахматный король обошёл всю доску 8×8, побывав на каждой клетке по одному разу, вернувшись последним ходом в исходную клетку.
Докажите, что он сделал чётное число диагональных ходов.

Решение

При каждом недиагональном ходе меняется цвет поля, на котором стоит король; при диагональном – не меняется. Поскольку король обошёл всю доску и вернулся обратно, то цвет поля менялся с белого на чёрный столько же раз, сколько с чёрного на белый, значит, недиагональных ходов король сделал чётное число. Число диагональных ходов равно 64 минус число недиагональных ходов – тоже чётное число.

Замечания

3 балла

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