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

[Lia]

atlakatl
Замечание за оффтоп. Оффтоп удален.

[B@R5uk]

arseniiv в сообщении #1290426 писал(а):

Кому интересно, моя гипотеза неверна

А в чём она заключалась?

[arseniiv]

Вот она:

arseniiv в сообщении #1290313 писал(а):

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

Добавил там «прямоугольные», а то можно неправильно понять.

[DeBill]

arseniiv
ЭТА гипотеза неверна. Но: если замощение есть, то есть и замощение, для которого она верна....

[arseniiv]

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

[atlakatl]

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

10 на 10 не режется на 1 на 4.

Вот ключ к разгадке. 1 минимальная длина. В целочисленном $ab$ этой стороной можно замостить его и по вертикали, и по горизонтали. А так как $ab \bmod cd=0$, то вторая, большая сторона должна делить оставшуюся сторону нацело.
Если в процессе деления возникнет прямоугольник с нецелой второй стороной, то тут уже ничего не поделаешь: меньше чем 1 натуральное число не бывает.
Т.е. дело просто в масштабе.
Допустим, $ab=210 \times 13$, а $cd = 3 \times 7$. п.1 выполнен.
Но теперь всё разделим на 3. $ab=70 \times 13/3$, $cd = 1 \times 7/3$ - замостить нельзя!
А вот $ab=210 \times 15$ уже можно.
Т.о. остаётся одно условие: одно из чисел $a, b$ должно делиться на меньшее из $c, d$, а второе - на оставшееся.

[Null]

$5 \times 6$ можно замостить $2\times 3$

[ET]

Вроде как в частном случае задачи с $c=1$ необходимо и достаточно чтобы в упомянутой DeBill диагональной раскраской в $d$ цветов каждого цвета было поровну
Это как-нибудь можно переформулировать? В смысле эквивалентно ли это тому, что одно из чисел $a$ или $b$ делится на $d$?

[atlakatl]

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

$5 \times 6$ можно замостить $2\times 3$

Да, но там простая аддитивность $3\times6$ и $2\times6$. Каждый из них условию делимости удовлетворяет.

ET в сообщении #1290492 писал(а):

эквивалентно ли это тому, что одно из чисел $a$ или $b$ делится на $d$?

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

[DeBill]

Ааа, все можно - проще, без всяких раскрасок (но - можно и с раскрасками): я уже писал, как доказать, что одно из чисел $a,b$ делится на $c$. Но - чем $d$ хуже? - получаем, что одно из них делится на $d$. Все, необходимые условия получены.

-- 06.02.2018, 13:44 --

atlakatl в сообщении #1290482 писал(а):

одно из чисел $a, b$ должно делиться на меньшее из $c, d$, а второе - на оставшееся.

Не так: "..., и одно из них - на оставшееся"

[B@R5uk]

Тогда стоит обобщить. Возможны два варианта, когда существует замощение:
1) одно из чисел a или b делится на с, а другое — на d
2) одно из чисел a или b делится и на c, и на d, а другое представимо в виде $n\,c+m\,d$ с положительными n и m.
Это как раз моя гипотеза со множествами.

Интересно, автору топика ещё интересная эта задача? Откуда она возникла?

[DeBill]

arseniiv
6 на 6, замощенный доминошками, всегда разбиваем на два прямоугольника (от противного: пусть - нет. Тогда каждый разрез (гориз. или верт.) пересекает доминошку (и даже две - из четности). Разрезов всего $5+5=10$, а доминошек $18<20$ - противоречие). Это рассуждение ломается при бОльших размерах. Так что, может, есть пример и для 6 на 8?

[B@R5uk]

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

6 на 6, замощенный доминошками, всегда разбиваем на два прямоугольника

Я сходу придумал замощение, которое не разбиваемо на два:
+---+---+---+
|...|...|...|
+-+-+-+-+-+-+
|.|...|...|.|
|.+-+-+-+-+.|
|.|.|.|.|.|.|
+-+.|.|.|.+-+
|.|.|.|.|.|.|
|.+-+-+-+-+.|
|.|...|...|.|
+-+-+-+-+-+-+
|...|...|...|
+---+---+---+

-- 06.02.2018, 13:44 --

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

[DeBill]

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

замощение, которое не разбиваемо на два:

Разве? Отрежем сверху полоску ширины 1... Или - снизу.

[B@R5uk]

И правда...