Прямоугольник и тримино

[Edward_Tur]

Доказать, что прямоугольник $m \times n$ нельзя замостить тремя уголками-тримино и некоторым количеством прямых тримино.

[grizzly]

Пусть мы замостили этими тримино некий прямоугольник. Пусть горизонтальная сторона этого прямоугольника кратна 3, тогда его можно раскрасить циклически тремя цветами так:
123123...123
231231...231
312312...312
...
или так:
123123...123
312312...312
231231...231
...
Теперь несложно доказать, что все три уголка в нашем замощении одинаково ориентированы (иначе неизбежны кратные трём проблемы для каких-то цветов [в одной из раскрасок -- добавлено позднее]).

Казалось бы дальше всё просто -- достаточно доказать, что нельзя замостить прямоугольник никаким количеством одинаково ориентированных (переводимых друг в друга простым сдвигом) уголков-тримино и прямых тримино. Это же что-то очень простое, правда? Но у меня ни одной продуктивной идеи. Нужно знать какой-то олимпиадный трюк?

[venco]

grizzly в сообщении #936046 писал(а):

Теперь несложно доказать, что все три уголка в нашем замощении одинаково ориентированы (иначе неизбежны кратные трём проблемы для каких-то цветов).

12 12   3 
2   3  31

[grizzly]

venco в сообщении #936048 писал(а):

grizzly в сообщении #936046 писал(а):

Теперь несложно доказать, что все три уголка в нашем замощении одинаково ориентированы (иначе неизбежны кратные трём проблемы для каких-то цветов).

12 12   3 
2   3  31

Ну да, я же и говорю -- несложно убедиться, что в другой приведенной выше раскладке цветов возникают проблемы.

-- 25.11.2014, 20:23 --

Здесь всё дело именно в том, что прямоугольник мы можем красить разными способами при уже фиксированном замощении.

[TOTAL]

grizzly в сообщении #936057 писал(а):

venco в сообщении #936048 писал(а):

grizzly в сообщении #936046 писал(а):

Теперь несложно доказать, что все три уголка в нашем замощении одинаково ориентированы (иначе неизбежны кратные трём проблемы для каких-то цветов).

12 12   3 
2   3  31

Ну да, я же и говорю -- несложно убедиться, что в другой приведенной выше раскладке цветов возникают проблемы.

В примере уголки ориентированы по-разному. Какие проблемы возникли?

[12d3]

TOTAL в сообщении #936314 писал(а):

В примере уголки ориентированы по-разному. Какие проблемы возникли?

Если эти же уголки раскрасить второй раскраской, выйдет плохо.

[grizzly]

Надеюсь, все согласятся, что нельзя замостить прямоугольник некоторым количеством одинаково ориентированных уголков-тримино и прямых тримино (далее у- и п- тримино, соответственно).

Попытаемся ещё дальше обобщить эту часть задачи. Для этого сначала введём формализацию ориентации у-тримино. Сопоставим каждому типу у-тримино одну из упорядоченных пар: $(-1;-1), (-1;1), (1;-1), (1;1)$. Назовём это характеристикой у-тримино. Правило сопоставления опишем в наивном виде: если у-тримино можно преобразовать в п-тримино перемещением одной из клеток на 1 клетку вправо и на 1 клетку вниз, то это тип $(1;-1)$ (здесь знаки намекают на направление движения по декартовым осям). Для остальных типов -- аналогично. Можно, по аналогии для любого п-тримино считать характеристикой пару $(0;0)$.

Я предполагаю, что в этих терминах будет верным следующее обобщение:
Лемма. В произвольном замощении прямоугольника с помощью тримино покоординатная сумма характеристик всех тримино равна $(0;0)$.

Если утверждение Леммы верно, то такой выбор инварианта представляется удачным.

[12d3]

К сожалению, лемма неверна, если я все правильно понял. Прямоугольник 4 на 6 можно замостить 7 уголками и одни прямым. А семь уголков в сумме не дадут $(0;0)$

[grizzly]

Проверил -- действительно можно. Лемма не верна. Спасибо, что столкнули с ложного пути :)

[provincialka]

По моему опыту такие методы (рассмотрение каких-то вариантов расстановки) практически никогда не приводят к успеху. Нужен инвариант, или полуинвариант, раскраска и т.п. Правда, наличие решения с 7 уголками смущает...

[Edward_Tur]

provincialka в сообщении #936549 писал(а):

Правда, наличие решения с 7 уголками смущает...

Есть и решение с 5 уголками.

[provincialka]

То есть 3 - единственное исключение? Вот это номер! А может, того, как-то можно уложить и три?

[Edward_Tur]

provincialka в сообщении #936602 писал(а):

То есть 3 - единственное исключение? Вот это номер! А может, того, как-то можно уложить и три?

Один - тоже исключение. Легко доказывается раскраской в три цвета.

[grizzly]

Edward_Tur в сообщении #936604 писал(а):

provincialka в сообщении #936602 писал(а):

То есть 3 - единственное исключение? Вот это номер! А может, того, как-то можно уложить и три?

Один - тоже исключение. Легко доказывается раскраской в три цвета.

Как раз тоже про 5 хотел сказать -- спасибо, опередили. Да, получается только два исключения -- 1 и 3 уголка. Для одного раскраска решает всё, для трёх -- только доказывает, что все они одинаково ориентированы.

Я уверен в справедливости утверждения, что любое количество одинаково ориентированных "не работает". И искать общий инвариант для такого обобщения представляется более естественным, чем для трёх уголков как исключения из правил.

[provincialka]

Не додумала до конца, но, может, сделать так.
Одна из сторон прямоугольника кратна 3. Пусть, например, вертикальная. Раскрасим его горизонтальными полосками в 3 цвета. Число клеток каждого цвета будет совпадать. В прямоугольнике число клеток разного цвета может быть $(0, 0, 3)$ или $(1, 1, 1)$, то есть совпадает по модулю 3. Значит, и для трех уголков в сумме должно быть то же условие.

По модулю 3 число разноцветных клеток в уголке будет $(1,-1,0)$ с точностью до перестановки (две клетки в одной горизонтали, одна - в другой). Можно показать (можно?), что суммы трех таких векторов сравнимы $\mod 3$ с $(a,a,a)$, только если нули стоят в одном столбце. То есть уголки раскрашены только в 2 цвета. Поэтому лежат в полосах шириной 2.

Ну и что? Надо дальше думать...

-- 26.11.2014, 23:57 --

А нет, можно уложить три уголка еще и так: $(0,1,2)$, $(1,2,0)$, $(2,0,1)$.