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)$ Тоже абсурдно т.к. полоска будет хорошей для квадратика в который он входит