Замощение прямоугольника

[arseniiv]

B@R5uk в сообщении #1290561 писал(а):

arseniiv, если честно, я так и не понял, в чём ваша гипотеза заключалась. Можете ещё раз чуть подробнее?

Вот любое замощение (но не тривиальное). Тогда если провести вертикальную или горизонтальную линию в прямоугольнике так, чтобы она никакой прямоугольник из замощения не разрезала. Но вот увы (или ура — если всё такое регулярное, как-то скучно).

Под совместимостью тут я имел в виду, что одно из разбиений можно получить измельчением другого. (О, кстати, если не указывать, какое какого, тривиальное замощение можно уже не отделять от остальных.)

(ASCII-графика)

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

1 1 2 2 1 1
5 3 3 4 4 5
5 1 2 1 2 5
6 1 2 1 2 6
6 3 3 4 4 6
1 1 2 2 1 1

Разрезы сразу видно.

[Null]

Вот вопрос можно ли замостить прямоугольник $147\times 100$ прямоугольниками $14\times 15$?

[DeBill]

Null
Из доказанного выше следует: нет.

[Null]

DeBill
В теме нет ни одного доказательства.

[DeBill]

Null в сообщении #1290744 писал(а):

В теме нет ни одного доказательства.

Это странно: я был уверен, что сформулированная (последней) гипотеза доказана (даже как "необходимое и достаточное условие разрезаемости"). И даже двумя способами: раскраской, и факторизацией....

[DeBill]

А, нет: в "необходимости", не показана разрешимость линейного уравнения в натуральных
Добавлено: Дык это ж очевидно: к стороне примыкают нужные отрезки, что и есть выполнение условия...

[Null]

Метод раскраски выглядит странно, ничего не сказано о повернутом прямоугольнике.

[DeBill]

Null в сообщении #1290957 писал(а):

ничего не сказано о повернутом прямоугольнике.

При "диагональной" раскраске в $d$ цветов, каждая полоска ширины 1 (как вертикальная, так и горизонтальная) содержит ровно одну клетку каждого из цветов. Поэтому прямоугольник $c$ на $d$ (хоть и повернутый) содержит ровно $c$ клеток каждого из цветов. Осталось проверить, что если ни $a$, ни $b$ не делится на $d$, то в большом пр-ке, не всех цветов поровну (что не есть совсем тривиально. Но - правда...)

[Null]

DeBill в сообщении #1291007 писал(а):

что не есть совсем тривиально. Но - правда..

Понятно. Это правда.
Пусть $a=kd+r, b=md+l$, где $|l|,|r|\le \frac{d}{2}$. Тогда задача сводиться к равности цветов в прямоугольнике $r\times l$. А 1 из цветов туда не попадает.