Задача 30771

Тема:    [ Инварианты ]

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

Условие

Фишка ходит по квадратной доске, каждым своим ходом сдвигаясь либо на клетку вверх, либо на клетку вправо, либо по диагонали вниз-влево. Может ли она обойти всю доску, побывав на всех полях ровно по одному разу, и закончить на поле, соседнем справа от исходного?

Решение

Сумма номеров строки и столбца при каждом ходе либо уменьшается на 2, либо увеличивается на 1. Значит, ее остаток по модулю 3 каждый раз увеличивается на 1. Так как всего ходов n² - 1, а в конце сумма должна быть на 1 больше исходной, то мы получаем, что n² - 2 должно делиться на 3, что невозможно. Следовательно, такого обхода нет.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	12
Название	Инвариант
Тема	Инварианты
задача
Номер	022