Архив задач олимпиады по математике и криптографии
Обход
Докажите, что нельзя обойти все клетки изображенной на рисунке фигуры, побывав в каждой ровно один раз. Начинать движение можно из любой клетки. Разрешается двигаться на одну клетку только вправо, влево, вверх или вниз. Движение по диагонали запрещено.
Раскрасим клетки как на рисунке. Делая один шаг, мы из черной клетки попадаем в белую и наоборот. Значит, если бы искомый обход был возможен, то клеток одного цвета было бы от силы на единицу больше, чем клеток другого цвета. Но черных клеток на две больше, чем белых. Поэтому обход невозможен.
