Форум на Исходниках.RU

покрытие прямоугольника

Hyboid — Fri, 20 Aug 2004 01:53:18 +0000

Hyboid: Предлагаю так...

Дано:
A - прямоугольник;
Введем P(A) = "У A длина хотя бы одной стороны - целое число";

{Xi, i=1..n}
Xi & Xj = 0, при i <> j;
X1 | X2 | ... | Xn = A;

Доказать: P(X1) & P(X2) & ... & P(Xn) -> P(A);

Доказательство.

Выбрать прямоугольник Xi, находящийся в нижнем углу A, обозначим его KLMN.
Пусть M лежит внутри A и сторона KL - целая, расположена вертикально.
Разрежем исходный прямоугольник по прямой (LM).
Возьмем верхнюю часть и обозначим ее A'. Очевидно, что P(A) <-> P(A').
т.к. прямая (LM) может пересекать Xj тремя способами, то выполнение P(X'j) не нарушается
a) вдоль стороны - тривиально;
б) У Xj вертикальная сторона целая - из целого вычесть KL - целое = целое;
в) У Xj горизональная сторона целая - пересечение с (LM) не существенно.

Так будем резать пока не останется один цельный прямоугольник
(т.к. Xj-ых конечное число), покрытый единственным X'' у которого длина хотя
бы одной стороны целая.
:whistle:

покрытие прямоугольника

Vesper — Thu, 05 Aug 2004 06:44:18 +0000

Vesper: хммммм. Пусть есть прям-к А со сторонами m+f, n+g (N Э m,n; 0
Черт :( какая-то ахинея, смысл в том, что в прям-ке останется дыра размером f*g, в которую прям-к с целой стороной не впишешь.

Пусть есть прям-к А (m+f, n+g) m,n целые, 0Вообще-то задача сводится к невозможности собрать (X*a*b+1)/(a*b) из дробей 1/a и 1/b, a,b,X E N.

опять черт :( есть ли у кого есть еще идеи?

покрытие прямоугольника

Adil — Sat, 31 Jul 2004 07:04:18 +0000

Adil:

Цитата

Гость ALF, 31.07.04, 01:26
Доказали лишь что на 2 поделить нельзя, а вдруг на 3 можно, или на 4,...

Ну может неполной мат.индукцией? :)

покрытие прямоугольника

Гость ALF — Fri, 30 Jul 2004 21:26:23 +0000

Гость ALF:

Цитата

Sazabis, 29.07.04, 14:21
Предположим что мы имеем А, с не целыми сторонами, попробуем поделить его на две части так, чтобы получилось 2 прямоугольника у которых хотябы 1 стороная целая. Мы не сможем сего сделать потому как нельзя сложить 2 целых чтобы получить нецелое. Получили противоречие, чтд

Доказали лишь что на 2 поделить нельзя, а вдруг на 3 можно, или на 4,...

покрытие прямоугольника

Sazabis — Thu, 29 Jul 2004 11:21:43 +0000

Sazabis: Предположим что мы имеем А, с не целыми сторонами, попробуем поделить его на две части так, чтобы получилось 2 прямоугольника у которых хотябы 1 стороная целая. Мы не сможем сего сделать потому как нельзя сложить 2 целых чтобы получить нецелое. Получили противоречие, чтд :P

покрытие прямоугольника

esperanto — Wed, 28 Jul 2004 16:42:23 +0000

esperanto: :yes: :yes: :yes:
:yes: :yes:
:yes:
:wall: >:(

покрытие прямоугольника

CD_Eater — Wed, 28 Jul 2004 15:13:18 +0000

CD_Eater: esperanto
Всё-таки есть существенная разница между математиками и программистами... :D

покрытие прямоугольника

Adil — Mon, 19 Jul 2004 06:49:16 +0000

Adil: Не знаю, как насчет очевидности ответа, но мне сама фраза не понятна

Цитата

esperanto, 18.07.04, 13:29
покрыть* прямоугольниками х1,х2,...хп.

. что здесь означают символs '*' и 'x'? :unsure:

покрытие прямоугольника

tserega — Sun, 18 Jul 2004 17:51:50 +0000

tserega: А разве это не очевидно?

покрытие прямоугольника

esperanto — Sun, 18 Jul 2004 09:29:45 +0000

esperanto: Известно, что некоторый прямоугольник А, можно покрыть* прямоугольниками х1,х2,...хп.(прямоугольники не пересекаются друг с другом)
такими что, длина хотя бы одной стороны у каждого из них - целое число.

Докажите, что длина хотя бы одной стороны у А - целое число