Олимпиадная задача: можно ли расположить все доминошки горизонтально на доске с добавленной клеткой?

Все доминошки занимают 64 клетки, поэтому одна клетка всегда свободна. Будем называть ее дыркой. Заметим сначала, что если в (горизонтальном) ряду с дыркой есть хотя бы одна вертикальная доминошка, то одну из таких доминошек можно сделать горизонтальной. Действительно, для этого достаточно сдвинуть все горизонтальные доминошки, находящиеся между дыркой и вертикальной доминошкой, после чего повернуть вертикальную доминошку. Будем повторять такую операцию, пока дырка не окажется в ряду без вертикальных доминошек (это обязательно случится, так как после каждой операции число вертикальных доминошек уменьшается). Когда указанный процесс остановится, дырка будет находиться в верхнем ряду: действительно, дырка окажется в ряду, в котором все доминошки горизонтальны, а, значит, в этом ряду нечетное число клеток. Но во всех рядах,

а)

б)

в)

кроме верхнего, число клеток четно.

Начнем строить "змею": передвинем дырку в верхний левый угол и сделаем вертикальной доминошку, оказавшуюся под дыркой ("змея" занимает весь верхний ряд, см. рис., а).

Теперь рассмотрим оставшуюся часть доски. Применим процесс, описанный в первом абзаце, к этой части. После этого дырка окажется во втором сверху ряду, причем в этом ряду будет только одна вертикальная доминошка (рис., б). Передвинем теперь дырку в правый конец второго ряда и сделаем оказавшуюся под ней доминошку вертикальной. "Змея" теперь занимает уже два верхних ряда (рис. , в).

Повторяя эти операции, в итоге получим "змею", составленную из всех доминошек (рис., а). Теперь, если "змея переползет" на одну клетку вперед, то все доминошки станут горизонтальными (рис., б).

а)

б)

Комментарий. Заметим, что упоминавшееся в решении переползание "змеи" на одну клетку вперед есть применение процедуры, описанной в первом абзаце решения.

Ответ задачи отсутствует