20-я Международная Жаутыковская олимпиада по математике, 2024 год

Дана таблица ${m\times n}$, где $mn$ делится на $6$. В этой таблице полоской назовём любой прямоугольник ${1\times 3}$ или ${3\times 1}$, а доминошкой -- любой прямоугольник ${1\times 2}$ или ${2\times 1}$. Таблицу замостили полосками. Докажите, что поверх этого замощения таблицу можно замостить доминошками так, что в каждой полоске две клетки будут накрыты одной доминошкой и ещё одна -- другой. (При замощении прямоугольники покрывают всю таблицу и не перекрываются между собой.) ( М. Карпук )

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

Переформулировка условий:

Изначально полностью белую доску $m$ на $n$ каким то образом покрасим в один цвет при этом делая это фигурами $1 \times 3$ или $3 \times 1$. $($ Границы фигур остаются белыми $)$

Докажите что можно перекрасить доску в другой цвет фигурами $1 \times 2$ и $2 \times 1$ также имеющие белые грани так что: не будет $3$ подряд стоящие клетки $1 \times 1$

Решение:

Б.О.О. $m$ - четное. Теперь мы разобьем задачу на два случая. (i) $n \mid 2$, (ii) $n \nmid 2$

(i) Заполним доску фигурками $2 \times 2.$ $($ назовем их квадратами $)$ Теперь назовем полоску хорошой при случае когда две его клетки находятся в квадрате. Заметим что каждая линия входит ровно в 2 квадрата и является хорошей для одного из них.

В таком случае мы можем ставить доминошки в сторону куда смотрит хорошие полоски в каждом квадратике. Не сложно убедиться что данное очевидно работает.

(ii) В данном случае поступим аналогично, но последнюю полосу поделим на доминошки

Допустим мы не смогли сделать как нам хотелось.$($ Используем ту же тактику $)$

По $(i)$ выходит что мы сможем сделать это в прямоугольнике m x n-1 значит $a)$ Данное не получилось в последнем ряду, $b)$ Данное не получилось сделать на стыке с последним рядом

$a)$ Абсурдно. У нас выйдет так как мы поделили данный ряд на доминошки

$b)$ Тоже абсурдно т.к. полоска будет хорошей для квадратика в который он входит