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

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

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

Сообщение отредактировано: esperanto - 18.07.04, 09:32

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

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

Цитата

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

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

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

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

Цитата

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

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

Цитата

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

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

хммммм. Пусть есть прям-к А со сторонами m+f, n+g (N Э m,n; 0<f<1,0<g<1) В него могут быть вписаны только прям-ки с хотя бы одной целой стороной. Пусть в одном углу стоит прям-к со сторонами (а, б) Если А - целое, то оставшаяся фигура имеет остаток стороны m+f-A, т.е. (m-A)+f, нецелую. Сторона Б может быть любой, но чтобы не плодить нецелости, ее нужно брать Y+g Y - целое, Y<=n. Далее, всю сторону (m-A)+f мы уже не можем заполнить снизу одним прям-ком, так как если мы это сделаем, на 3-ей стороне останется иррациональный кусок меньшего размера.

Черт :( какая-то ахинея, смысл в том, что в прям-ке останется дыра размером f*g, в которую прям-к с целой стороной не впишешь.

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

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

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

Дано:
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'' у которого длина хотя
бы одной стороны целая.