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

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

Пронумеруем клетки доски числами 0, 1, 2 так, чтобы по диагонали «слева-направо и снизу-вверх» стояли одинаковые числа.

У1. Если существует искомая конструкция тримино, то существует конструкция, в которой все кривые тримино расположены одинаково и их центральные клетки имеют различные номера.

Действительно, учитывая, что $% mn $% делится на 3, на доске будет одинаковое число клеток, которые пронумерованы каждым из чисел. При этом все прямые тримино содержат одинаковое число клеток с разными номерами, поэтому число клеток с одинаковыми номерами в трех кривых тримино также одинаково. Это возможно в двух следующих случаях нумерации кривых тримино: 1) (0,1,2), (0,1,2), (0,1,2); 2) (0,1,1), (1,2,2), (2,0,0). Если затем сменить ориентацию принятой нумерации на противоположную, т. е. одинаковые числа теперь будут стоять по диагонали «слева-направо и сверху-вниз», то это условие также должно выполняться. Из этого нетрудно усмотреть также, что все кривые тримино должны быть расположены одинаково. Можно повернуть доску так, что они будут иметь, например, L-образное положение и центральные клетки будут занумерованы разными числами. Кроме того, не нарушая общности, будем считать, что ширина доски кратна 3. Кривые тримино в L-образном положении будем называть особыми.

Введем некоторые понятия. Пусть некоторым образом замощена $%i$%-я строка. Под конфигурацией $%i$%-й строки (нумерация снизу, начиная с 1) понимается совокупность клеток $% (i+1) $%-й и $% (i+2) $%-й строк, входящих в состав тримино, клетки которых имеются в $%i$%-й строке. Будем считать, что конфигурация исходной строки (т. е. строки с номером 0) пуста. Конфигурацию будем задавать последовательностью чисел $% H^i =(h_1^i, h_2^i,…, h_m^i ) $%, где $% h_j^i $% – число клеток $% j $%-го вертикального тримино, находящихся в $% (i+1)$%-й и $% (i+2)$%-й строках; для позиций, клетки которых входят в горизонтальные тримино, принимается $% h_j^i =0$%.

Процесс замощения (может быть, есть более удачный термин?) и формирования, таким образом, допустимых конфигураций осуществляется последовательно, начиная с 1-й строки. Замощение прямыми тримино каждой $% i$%-й строки и переход, таким образом, к одной из ее допустимых конфигураций осуществляется следующим образом. В произвольные пустые места строки укладывается произвольное число (которое может быть размещено) горизонтальных тримино, а в оставшихся выставляются вертикальные. При этом при замощении прямыми тримино допустимыми для $% i=1 $% являются конфигурации $%H^1 $%, у которых $% h_j^1 =0$% либо $% h_j^1 =2$%, причем для всех $% j=1,2,…,n$% выполняются условия: $$ a) h_j^i \ne 0 \land h_{ j +1}^i = 0 \Rightarrow h_{ j +2}^i= h_{ j +3}^i =0 .$$ $$ b) h_j^i = 0 \land h_{ j +1}^i \ne 0 \Rightarrow j+1-J(j) \equiv 0 (mod 3), $$ где $%J(j) $% - обозначает наибольший номер позиции, не больший $%j$%, в которой $%h_{J(j)}^1 \ne 0.$% Допустимые конфигурации $% H^{i} $% для любой $% i$%-й строки на основе заданной конфигурации $% (i-1)$%-й строки формируются при заполнении строки прямыми тримино следующим образом:

1) формируется заполнение свободных клеток $% i$%-й строки, описываемое последовательностью $% d_{ j }$%, для которой должны быть выполнены условия: $$ a) h_j^{i-1}\ne 0 \Rightarrow d_{ j }=0;$$ $$ b) h_j^{i-1}= 0 \Rightarrow d_{ j }=1 \lor d_{ j }=3 ; $$ $$ c) d_j \ne 0 \land d_{ j +1} = 0 \Rightarrow d_{ j +2} = d_{ j +3} =0; $$ $$ d) d_j = 0 \land d_{ j +1} \ne 0 \Rightarrow j+1-J(j) \equiv 0 (mod 3).$$

3) формируется конфигурация $% H^{i} $% в виде: $% h_{ j }^i= h_j ^{i-1}+ d_j -1$%.

У2. При $% i \ge 4 $% любая допустимая конфигурация $% i$%-й строки может быть получена в результате добавления некоторых горизонтальных тримино к допустимой конфигурации $% (i-3)$%-й строки.

Это утверждение может быть доказано на основе условий a)-d), однако в его справедливости можно убедиться путем рассмотрения примеров построений конфигураций.

Конфигурация строки называется s-допустимой ($% s \in \lbrace 0,1,2,3 \rbrace $%), если она может быть получена из исходной при заполнении строк с номерами от 1 до $% i $% прямыми и особыми тримино, причем число особых тримино равно $% s $%. При использовании в строке особых тримино указанные операции отличаются тем, что предварительно (до п. c) в строку осуществляется вставка их заданного числа.

У4. При $% i \ge 4 $% любая $%s$%-допустимая конфигурация $% i$%-й строки может быть получена в результате добавления некоторых горизонтальных тримино к $%s$%-допустимой конфигурации $% (i-3)$%-й строки.

У5 (следствие У4). Если существует конструкция с тремя особыми объектами, то существует такая конструкция с размерами доски не более $% 14 \times 15 $%.

У6. Для существования конструкции необходимо и достаточно, чтобы при некотором $% i$% конфигурация $% i$%-й строки $% h^{i}=(0,0,…0) $% была $%s$%-допустимой.

У7. Конструкции с заданными особыми объектами не существует.

Примечание (добавил для упрощения понимания идеи). Некоторые приведенные утверждения не являются необходимыми для доказательства и выглядят излишними. Фактически доказательство опирается на прозрачные утверждения У1, У4 и простое установление того факта, что при $% s \ge 1 $% $% s$%-допустимая конфигурация $% H^i$% обязательно содержит подпоследовательность длины 3, все элементы которой различны.