|
|
 |
Условие
В прямоугольную коробку с основанием m×n, где m и n – нечётные числа, уложены домино размера 2×1 так, что остался не покрыт только квадрат 1×1 (дырка) в углу коробки. Если доминошка прилегает к дырке короткой стороной, её разрешается сдвинуть вдоль себя на одну клетку, закрыв дырку (при этом открывается новая дырка). Докажите, что с помощью таких передвижений можно перегнать дырку в любой другой угол.
Решение
Занумеруем горизонтали и вертикали по порядку, начиная от края, и назовём полями клетки, стоящие на пересечении рядов с нечётными номерами. В частности, все клетки в углах – поля. Заметим, что дырка будет перемещаться только по полям.
Если поле A покрыто доминошкой, то одна из узких сторон доминошки
граничит с другим полем B; проведём стрелку из центра A в центр B. Заметим, что если B – дырка, то, сдвинув доминошку по стрелке, мы переместим дырку на A.
Проведём так стрелки из каждого поля (кроме дырки). Если есть путь по стрелкам из поля A на дырку, можно перегнать дырку на A, сдвинув сперва доминошку вдоль последней стрелки пути, затем – вдоль
предпоследней, и т.д.
Путь по стрелкам либо приходит на дырку, либо зацикливается. Докажем, что доминошки, соответствующие циклу, охватывают многоугольник с нечётным числом клеток внутри.
Действительно, рассмотрим цикл как линию из стрелок. Если построить новую квадратную сетку с узлами в центрах полей, то цикл пройдёт по линиям этой сетки и будет охватывать многоугольник, который сетка разбивает на квадраты со стороной 2. Докажем наше утверждение индукцией по числу квадратов. Для одного квадрата оно верно – если выложить домино по границе, внутри будет только одна клетка.
Многоугольник из k квадратов получается добавлением квадрата на границе многоугольника из k – 1 квадрата, и нетрудно
проверить, что при выкладывании границы доминошками внутри добавляется 2 или 4 клетки.
Итак, цикл должен охватывать многоугольник с нечётным числом клеток внутри. Но это невозможно, поскольку этот многоугольник должен быть заполнен целым числом доминошек, то есть содержать чётное число клеток, так как дырка исходно расположена на краю.
Значит, циклов нет, и существует путь по стрелкам, приходящий на дырку.
