Условие
Прямоугольник размером
2
n×2
m замостили костями домино
1×2. Докажите, что на этот слой костей можно положить
второй слой так, что ни одна кость второго слоя не совпадает с
костью первого слоя.
Решение
Разрежем прямоугольник со сторонами 2
n и 2
m на квадратики со
стороной 2 и вторым слоем будем мостить каждый квадратик по
отдельности.
Квадратик можно замостить либо двумя
горизонтальными костями домино, либо двумя вертикальными. Ясно,
что нам подойдет одно из этих покрытий, так как в квадратике со
стороной 2 не могут содержаться одновременно горизонтальная и
вертикальная кости.
Источники и прецеденты использования
