|
|
 |
Условие
На шахматную доску произвольным образом уложили 32 доминошки
(прямоугольника 1×2), так что доминошки не перекрываются. Затем к доске добавили
одну клетку, как показано на рисунке. Разрешается вынимать любую доминошку, а
затем класть её на две соседние пустые клетки.
Докажите, что можно расположить все доминошки
горизонтально.
Решение
Все доминошки занимают 64 клетки, поэтому одна клетка всегда свободна. Будем называть ее дыркой. Заметим сначала, что если в (горизонтальном) ряду с дыркой есть хотя бы одна вертикальная доминошка, то одну из таких доминошек можно сделать горизонтальной. Действительно, для этого достаточно сдвинуть все горизонтальные доминошки, находящиеся между дыркой и вертикальной доминошкой, после чего повернуть вертикальную доминошку. Будем повторять такую операцию, пока дырка не окажется в ряду без вертикальных доминошек (это обязательно случится, так как после каждой операции число вертикальных доминошек уменьшается).Когда указанный процесс остановится, дырка будет находиться в верхнем ряду: действительно, дырка окажется в ряду, в котором все доминошки горизонтальны, а, значит, в этом ряду нечетное число клеток. Но во всех рядах,
а)
б)
в)
кроме верхнего, число клеток четно.
Начнем строить "змею": передвинем дырку в верхний левый угол и сделаем вертикальной доминошку, оказавшуюся под дыркой ("змея" занимает весь верхний ряд, см. рис., а).
Теперь рассмотрим оставшуюся часть доски. Применим процесс, описанный в первом абзаце, к этой части. После этого дырка окажется во втором сверху ряду, причем в этом ряду будет только одна вертикальная доминошка (рис., б). Передвинем теперь дырку в правый конец второго ряда и сделаем оказавшуюся под ней доминошку вертикальной. "Змея" теперь занимает уже два верхних ряда (рис. , в).
Повторяя эти операции, в итоге получим "змею", составленную из всех доминошек (рис., а). Теперь, если "змея переползет" на одну клетку вперед, то все доминошки станут горизонтальными (рис., б).
а)
б)
Комментарий. Заметим, что упоминавшееся в решении переползание "змеи" на одну клетку вперед есть применение процедуры, описанной в первом абзаце решения.
