Областная олимпиада по математике, 2003 год, 9 класс

Клетчатая доска размера $2m\times 2n$ ($m$ и $n$ — натуральные числа) полностью покрыта доминошками размера $1 \times 2$ без наложений. Докажите, что эту доску можно полностью покрыть вторым слоем доминошек так, что никакие две доминошки первого и второго слоя не будут совпадать.

Комментарий/решение

Так как доска 2m$\times$2n, ее можно покрыть квадратиками размером 2$\times$2.

Для удобства будем называть домино "хорошим" если он не выходит за рамки какого то конкретного квадрата, то есть когда он полностью лежит на данном квадрате 2$\times$2.Рассмотрим 3 разных случая.

1)Когда в квадрате 2 параллельных доминошек.

2)Когда в квадрате есть только одна хорошая доминошка которая не выходит за рамки квадрата

3)Когда в квадрате нету ни одного хорошего домино.

.При первом случае просто на второй слой кладем 2 параллельных домино перпендикулярные к предыдущим параллельным доминошкам которые были расположены в первом слое всей доски. Во втором случае соединяем при помощи доминошек во втором слое каждый квадратик хорошего домино с квадратиками "нехорошего" домино.В третьем случае просто кладем 2 параллельных домино на второй слой.По такому алгоритму можно покрыть всю доску вторым слоем чтобы никакая новая доминошка не совпадала со старым.