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

[sa233091]

Существуют ли какие-нибудь критерии, позволяющие по числам $a, b, c , d$ узнать можно ли замостить клетчатый прямоугольник $a \times b$ клетчатыми прямоугольниками $c \times d$?

[atlakatl]

1. $\mod(a \cdot b; c \cdot d) = 0$
2. Должны существовать целые числа k, l, m, n, что $kc+md=a, lc+nd=b$

[kotenok gav]

(Оффтоп)

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

1. $\mod(a \cdot b; c \cdot d) = 0$

Кто так пишет? $ab\mod cd=0$

[Dmitriy40]

(Оффтоп)

kotenok gav в сообщении #1290172 писал(а):

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

1. $\mod(a \cdot b; c \cdot d) = 0$

Кто так пишет? $ab\mod cd=0$

Или так: $ab \bmod cd = 0$.

[sa233091]

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

1. $\mod(a \cdot b; c \cdot d) = 0$
2. Должны существовать целые числа k, l, m, n, что $kc+md=a, lc+nd=b$

А этого достаточно?

[atlakatl]

arseniiv
Достаточны ли названные мной два критерия для возможности замощения? Пробовал в Excel, всегда получалось.

-- 05.02.2018, 20:48 --

sa233091
Вот и я сомневаюсь. Контрпример бы решил вопрос.

[arseniiv]

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

Достаточны ли названные мной два критерия для возможности замощения? Пробовал в Excel, всегда получалось.

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

<Удалено насчёт удалённого.>

-- Пн фев 05, 2018 19:02:28 --

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

-- Пн фев 05, 2018 19:04:28 --

(Разумеется, это тривиальность, но потому и говорю, что не думал над этим.)

[atlakatl]

Пусть $c, d$ простые числа. Тогда для выполнения п.1 прямоугольник $a\times b$ должен иметь стороны, кратные этим простым. Тогда $a\times b$ действительно разбивается на отдельные прямоугольники, состоящими из горизонтально либо вертикально расположенных $c\times d$
Пусть "доминошки" имеют размер $17 \times 31$. Прямоугольник $a\times b$ имеет либо однонаправленный паркет - его стороны соответственно кратны 17 и 31, либо два прямоугольника, причём одна из его сторон кратна и 17, и 31 - для разнонаправленных доминошек.

[Xaositect]

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

1. $\mod(a \cdot b; c \cdot d) = 0$
2. Должны существовать целые числа k, l, m, n, что $kc+md=a, lc+nd=b$

Этого очевидно недостаточно, ибо при взаимно простых $c, d$ этим условиям удовлетворяет прямоугольник $a \times b = 1 \times cd$.
Вот если заменить во втором пункте целые числа на натуральные, то надо подумать.

-- Пн фев 05, 2018 15:57:34 --

А, тут тоже банально, надо наоборот - $c \times d = 1 \times ab$. Оба условия выполнятся.

[B@R5uk]

На мой взгляд нужно идти таким путём. Сначала рассмотреть множество прямоугольников, которые получаются взяв плитку $c\times d$ по горизонтали $n$ раз, а по вертикали $m$ раз, где эти два целых числа произвольные, большие нуля. Обозначим это множество $X$. Потом аналогичным образом построим множество прямоугольников $Y$ из плиток $d\times c$. Эти два множества всегда будут иметь общие элементы, а в особых частных случаях вообще полностью совпадать ($c=d$). Но для нас самое главное, что можно найти такие пары прямоугольников, что первый из них принадлежит $X$, второй — $Y$, а так же они имеют равную сторону. Не важно, вертикальная эта сторона или горизонтальная. Главное, что можно эти два прямоугольника сложить (без поворота) и получить новый, который может уже не принадлежать не $X$, не $Y$.

Так вот моя гипотеза: множество прямоугольников $Z$, включающее в себя оба множества $X$ и $Y$, а так же все прямоугольники, получаемые из двух, способом, описанным выше, исчерпывает все возможные прямоугольники, которые можно замостить плиткой $c\times d$.

В случае, если эта гипотеза верна, одно из чисел $a$ или $b$ обязано делиться на одно из чисел $c$ или $d$. А другое тогда — представимо в виде $k\,c+l\,d$.

[DeBill]

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

[arseniiv]

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

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

Точнее, или совместимо, или являет собой сам этот прямоугольник, его-то уж никак не поделишь.

[DeBill]

(известная задача. Решается диагональной раскраской в 4 цвета).

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

одно из чисел $a$ или $b$ обязано делиться на одно из чисел $c$ или $d$.

А есть еще такая известная: прямоугольник порезали на прямоугольники, у которых одна из сторон - целая. Доказать: у прямоугольника одна из сторон - целая (это доказывает Ваше "необходимое условие"). Одно из решений: порежем большой прямоугольник по линиям сетки на единичные квадратики, и - в нецелом случае - малые кусочки, и сложим в стопку (то бишь, профакторизуем плоскость по $\mathbb{Z}^2$). Разрезаемость дает: для любых $a,b,c,d$, точки $(a,b)$ и $(c,d)$ суммарно накрываются столько же раз, сколько и точки $(a,c)$ и $(b,d)$. Это приведет к противоречию, когда есть кусочек с двумями маленькими сторонами

[DeBill]

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

который может уже не принадлежать

Это автоматически приводит к делимости одной стороны большого (пусть $a$) и на $c$, и на $d$. Остается обеспечить представимость $b$ в виде $b=mc+nd$ с неотрицательными к-тами, что проверяется явно по разложению НОД ($c,d$ - взаимно просты, моно считать) $1=cx+dy$.
Осталось доказать Вашу гипотезу.
Имеем:
$(\ast)$ $a=kc$, но $k $ не делится на $d$,
$ab$ делится на $cd$ : $ab=Ncd$.
Будем действовать как в примере: покрасим прямоугольник в $d$ цветов: каждый цвет - по диагонали - так, что в любой (вертикальной или горизонтальной) полоске $1\times d$ каждого цвета - по одной клетке каждого цвета. Тогда в прямоугольничке $c\times d$ клеток каждого цвета - ровно $c$ штук. Прямоугольничков - ровно $N$ штук. Осталось заметить (это, вроде, правда), что при неделимости
$k$ на $d$, клеток одного цвета - не поровну....Противоречие.

-- 06.02.2018, 00:38 --

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

[arseniiv]

Кому интересно, моя гипотеза неверна — вот замощение, не делящееся на два прямоугольника:



В первый раз не вышло, решил увеличить размер. Если бы и 8×8 не собрался, подумал бы, что, видимо, контрпримеров нет. Повезло!