![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
bgmtЯ не помню, помещал ли я уже когда-нибудь эту задачу. Если да, то в первый период моего ЖЖительства, когда читало меня очень мало народу. Так что неважно.
Некоторые знания для решения надо иметь, предупреждаю.
Имеется набор прямоугольников. В некоторой системе мер по крайней мере одна сторона каждого прямоугольника - целочисленна. Про другую ничего не сказано.
Дано: их удалось сложить без дырок и без наложений так, что получился прямоугольник.
Доказать, что по крайней мере одна его сторона - целочисленна.
Ответы скринятся.
UPDATE Расскринено всё.
Некоторые знания для решения надо иметь, предупреждаю.
Имеется набор прямоугольников. В некоторой системе мер по крайней мере одна сторона каждого прямоугольника - целочисленна. Про другую ничего не сказано.
Дано: их удалось сложить без дырок и без наложений так, что получился прямоугольник.
Доказать, что по крайней мере одна его сторона - целочисленна.
Ответы скринятся.
UPDATE Расскринено всё.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2007-12-11 08:26 pm (UTC)Я ее в свое время решил, поэтому в конкурсе не участвую.
no subject
Date: 2007-12-11 10:42 pm (UTC)no subject
Date: 2007-12-11 10:58 pm (UTC)Я сообразил, что по прямоугольнику можно проинтегрировать e2π i(x+y) и получится 0. А отсюда все следует.
(ответ на заскриненный ответ)
Date: 2007-12-11 11:11 pm (UTC)Re: (ответ на заскриненный ответ)
Date: 2007-12-11 11:28 pm (UTC)no subject
Date: 2007-12-11 08:56 pm (UTC)Стало быть площадь большого прямоугольника - кратна p. Поскольку p - простое - одна из сторон кратна p (с учетом сказанного выше - сколь угодно близка к p). Чтд.
У нее есть решение по индукции, которое и считали нормальным мои знакомые.
no subject
Date: 2007-12-20 06:31 pm (UTC)за интегралы принялся!
(Я задачку не заметила, совсем забегалась. Только
сейчас увидела объявление, что комментарии расскринены)
no subject
Date: 2007-12-20 09:07 pm (UTC)no subject
Date: 2007-12-21 05:11 pm (UTC)именно так
Date: 2007-12-21 05:48 pm (UTC)Re: именно так
Date: 2007-12-23 01:05 am (UTC)no subject
Date: 2007-12-20 08:13 pm (UTC)no subject
Date: 2007-12-20 09:05 pm (UTC)no subject
Date: 2007-12-21 06:21 am (UTC)no subject
Date: 2007-12-11 09:38 pm (UTC)no subject
Date: 2007-12-11 09:49 pm (UTC)no subject
Date: 2007-12-20 04:17 pm (UTC)no subject
Date: 2007-12-11 10:22 pm (UTC)no subject
Date: 2007-12-11 10:27 pm (UTC)no subject
Date: 2007-12-11 10:40 pm (UTC)no subject
Date: 2007-12-12 08:58 pm (UTC)Большой прямоугольник то конечный или как? :)
no subject
Date: 2007-12-12 11:04 pm (UTC)no subject
Date: 2007-12-12 07:40 am (UTC)Но фсе, фсе забыл... покрылся инеем и мхом.
no subject
Date: 2007-12-12 11:05 pm (UTC)no subject
Date: 2007-12-14 06:47 pm (UTC)no subject
Date: 2007-12-12 09:07 am (UTC)no subject
Date: 2007-12-12 11:07 pm (UTC)no subject
Date: 2007-12-13 07:45 am (UTC)возьмем какую-то точку на торе, и проведем через нее меридиан и параллель. Они разделят окрестность точки на четыре квадранта. Обойдем их по часовой стрелке и возьмем альтернированную сумму числа листов накрытия в каждом квадранте. Если эта сумма не ноль, назовем точку "углом".
При добавлении фигурок в накрытие вышеописанная сумма ведет себя аддитивно. Поскольку для каждого из малых прямоугольников она везде ноль, то и у всего накрытия не будет "углов". А если бы большой прямоугольник имел обе стороны нецелые, то получилось бы четыре угла.
no subject
Date: 2007-12-13 07:54 am (UTC)no subject
Date: 2007-12-13 02:26 pm (UTC)no subject
Date: 2007-12-13 06:04 am (UTC)no subject
Date: 2007-12-13 02:24 pm (UTC)no subject
Date: 2007-12-13 10:46 am (UTC)Терминология.
Прямоугольник - один из прямоугольников выбранного набора.
Поле - "большой прямоугольник", сложенный из меньших. Нам надо доказать, что одна из сторон поля целочисленна. Направление одной из сторон считаем "вертиакльным", другой - "горизонтальным".
Вертикальный прямоугольник - прямоугольник (из набора), у которого вертикальная сторона целочисленна.
Горизонтальный прямоугольник - прямоугольник, не являющийся вертикальным. По условию, у всех горизонтальных прямоугольников горизонтальная сторона целочисленна.
Высота - расстояние от нижней стороны поля (мы не будем рассматривать точки, находящиеся ниже её, так что о знаках можно не беспокоиться).
Уровень - максимальный (в смысле включения) отрезок, составленный из горизонтальных сторон прямоугольников. В частности, верхняя и нижняя стороны поля являются уровнями; верхняя и нижняя стороны каждого прямоугольника лежат на каком-то уровне. Два уровня могут иметь одну и ту же высоту. Для каждого уровня, кроме верхней и нижней сторон поля, сумма длин горизонтальных сторон прямоугольников, прилегающих к этому уровню сверху, равна такой же сумме снизу (и равна длине самого уровня).
Определим понятие достижимого уровня по индукции:
1) Нижняя сторона поля - достижимый уровень.
2) Если к уровню прилегает - неважно, с какой стороны - вертикальный прямоугольник, другая горизонтальная сторона которого лежит на достижимом уровне, то данный уровень тоже достижим.
По определению вертикального прямоугольника, видно, что все достижимые уровни имеют целочисленную высоту. В частности, если верхняя сторона поля достижима, то вертикальная сторона поля целочисленна.
Предположим теперь, что верхняя сторона поля недостижима. Тогда для всех достижимых уровней, кроме одного (а именно, нижней стороны поля), сумма горизонтальных сторон прямоугольников, прилегающих к ним сверху, равна сумме горизонтальных сторон прямоугольников, прилегающих к ним снизу; для нижней же стороны поля она равна горизонтальной стороне поля. Следовательно, горизонтальная сторона поля равна (сумма длин горизонтальных сторон прямоугольников, прилегающих к достижимым уровням сверху) - (сумма длин горизонтальных сторон прямоугольников, прилегающих к достижимым уровням снизу).
Далее, каждый вертикальный прямоугольник либо не прилегает ни к одному достижимому уровню, либо прилегает к двум достижимым уровням - к одному сверху, к другому снизу. Следовательно, он либо вообще не попадает в эту разность, либо попадает как в первую сумму, так и во вторую. Значит, мы можем сократить все вертикальный прямоугольники. Таким образом, горизонтальная сторона поля равна (сумма длин горизонтальных сторон ГОРИЗОНТАЛЬНЫХ прямоугольников, прилегающих к достижимым уровням сверху) - (сумма длин горизонтальных сторон ГОРИЗОНТАЛЬНЫХ прямоугольников, прилегающих к достижимым уровням снизу). Поскольку горизонтальные прямоугольники имеют целочисленные горизонтальные стороны, обе суммы целочисленны и их разность тоже целочисленна. Ч.Т.Д.
no subject
Date: 2007-12-13 02:22 pm (UTC)Это так безумно сложно (ну, для моего способа мышления)... Есть настолько более простое решение... И даже менее (для меня) простое решение, предложенное ПК, тоже менее сложно, на мой вкус...
no subject
Date: 2007-12-13 02:24 pm (UTC)Рассмотрим функцию двух переменных f(x,y)=(sin 2\pi x)(sin 2\pi y). Её интеграл по прямоугольнику равен нулю если и только если одна из сторон прямоугольника - целое число. Интеграл по большому прямоугольнику - сумма интегралов по всем маленьким, т.е. ноль.
no subject
Date: 2007-12-13 02:43 pm (UTC)no subject
Date: 2007-12-13 10:47 am (UTC)P.P.S. А что нужно знать?
no subject
Date: 2007-12-21 10:23 pm (UTC)Закрасим чёрным все прямоугольники с целочисленной горизонталью. Получаем чёрный большой прямоугольник с белыми прямоугольниками внутри. Теперь смотрим, существует ли горизонтальная чёрная непрерывная линия от края до края. Если да, то горизонталь целочисленна как сумма целочисленных сторон.
Теперь рассмотрим случай, когда такой линии не существует. Это значит, что имеется разрыв - вертикальная белая линия от края до края. Поскольку белыми мы оставили прямоугольники с целочисленной вертикалью, то вертикаль большого прямоугольника целочисленна как сумма целых.
ЧТД.
no subject
Date: 2007-12-21 11:59 pm (UTC)no subject
Date: 2007-12-22 03:04 pm (UTC)> вертикальная белая линия от края до края.
Естественно, не значит. Прямоугольники с целочисленной горизонталью могли бы тянуться от левого края до правого, нигде не накрывая большую горизонталь полностью.
Тут надо "ухватить тотальность" - что у Мигмита сделано.
no subject
Date: 2007-12-22 11:57 pm (UTC)Воистину так - я сознательно не рассматривал случай "вертикальной лесенки", потому что тут надо бы нарисовать. Если нарисовать, то станет ясно, что мы можем разбить нашу "полную горизонталь" на куски согласно "ступеням лесенки" и получить её не целиком, а в сумме - и не сможем этого сделать только в случае наличия вертикальной белой полосы ненулевой ширины. Несомненно, у Мигмита это всё сделано более строго.
no subject
Date: 2007-12-23 05:57 pm (UTC)Если учитывать конструкции типа такой (прямоугольники с целочисленной горизонталью выделены красным):
- думаю, что рассуждение получится не проще, чем у Мигмита. Т.е., наверное, просто эквивалентное мигмитовскому.