олимпиада мехмата

[peregoudov]

Четвертая, вроде, скучная, а что с пятой? Понятно, что прямоугольниками только с рациональными сторонами квадрат не замостить: не из чего будет набрать иррациональную сторону. А почему невозомжно замощение прямоугольниками с обеими рациональными либо с одной рациональной и одной иррациональной сторонами? Просто по площади ограничений нет: сумма иррациональных чисел может быть и рациональной.

Думал на такую тему: любая вертикальная (горизонтальная) прямая, пересекающая квадрат, пересекает и прямоугольник с иррациональной вертикальной (горизонтальной) стороной. И нельзя ли как-то исхитриться доказать, что иногда это один и тот же прямоугольник?

[Ian]

По пятой.идея была такая: покрасим синим те у которых вертикальная рациональна, красным те у которых горизонтальная рациональна. Тогда можно пройти от одной стороны до другой по одному нужному цвету (между горизонтальными по синему, или между вертикальными по красному), не проходя через углы.Если два синих соприкасаются вертикальными сторонами, то их границу считаем красной. Или наоборот.Получается, что путь с вертикальным перемещением [math]\sqrt {2019} состоит из одних рациональных вертикальных, в том числе, может быть, нулевых -по общей синей границе двух красных. Или наоборот.

[zykov]

Source of the post По пятой.идея была такая: покрасим синим те у которых вертикальная рациональна

А какая область математики занимается такими вопросами?
На теорию графов не очень похоже...

[Ian]

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

[zykov]

Source of the post топология

А студентам её преподают?
Нам такого не преподавали...

[Ian]

В полном виде в программе нет, кусками входит во что угодно, от функана до алгебры

[peregoudov]

Ничего не понял. Откуда следует, что можно пройти? Или откуда следует, что существуют два непересекающихся пути? И как в этом "доказательстве" используется, что обе стороны квадрата иррациональны?

[zykov]

Source of the post что обе стороны квадрата иррациональны?

Доказательство "от противного". Предположим что нет "обе стороны иррациональные", тогда каждый цветной - либо красный, либой синий, либо оба сразу.

[Ian]

Если "обе рациональны" выбираем цвет произвольно.Точки границы между красным и синим -покрашены в один из цветов, неважно в какой. И вот тогда путь, дающий противоречие, существует только одного типа -либо сверху вниз , либо слева направо. Потому что какого цвета должна быть точка пересечения путей?. Важный момент в другом. Предположим, существует синий путь сверху вниз. Тогда из одного синего в другой попадаем либо через общую точку их горизонтальных сторон, либо по одномерной горизонтальной тропинке, дающей нулевой вклад в вертикальное перемещение.Поэтому и введены эти тропинки. У участка пути внутри одного синего прямоугольника вертикальное перемещение либо +высота, либо -высота, либо 0, в любом случае рациональна, итого вертикальное перемещение- это сумма рациональных чисел, противоречие.

[zykov]

Интуитивно оно понятно, что должно так работать.
Но всё же тут нужно какое-то строгое доказательство, что оно так.
Вот на картинке пример пути, когда ширины не складываются.

square2019_path.png (2.47 KiB) 22868 просмотра

(Понятно, что в данном конкретном случае разбиения на 4 прямоугольника всё легко доказать. Но как это сделать в общем случае?)

[peregoudov]

При таком расположении Ian предлагает красить соприкасающуюся часть сторон в синий цвет, так что пройти нельзя.

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

[Ian]

При таком расположении Ian предлагает красить соприкасающуюся часть сторон в синий цвет, так что пройти нельзя.

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

[zykov]

Если оставить в стороне рациональные/иррациональные, то у нас есть просто квадрат разбитый как-то на прямоугольники. При этом каждый прямоугольник либо красный, либо синий (плюс ещё цвет границ, как Ian писал). Нужно показать, что либо есть красный путь слева направо, либо есть синий путь сверху вниз.

Возьмем на верхней границе самую левую и самую правую синие точки. (Если таких нет, то вдоль верхней границы есть красный путь слева направо.)
И из этих двух точек начнем заливать зелёным все соприкасающиеся соседние синие области (как в графическом редакторе рекурсивный алгоритм заливки области).
Тогда, либо зелёный дойдёт до нижней границы, что даст синий путь сверху вниз. Либо зелёный не дойдёт до нижней границы, тогда вдоль границы зеленой области будет красный путь слева направо.
(Тут не важно, сольются ли две изначально не связные области, или так и останутся две не связанные друг с другом области.)

При этом при движении вдоль пути, в силу правил раскраски границ переход от одного прямоугольника до другого может быть для красного только через вертикальную границу, или через вертикальный отрезок между синими прямоугольниками. Переход через горизонтальный отрезок (как на моём рисунке) для красного запрещен. Аналогично для синего.

В итоге, возвращаясь к рациональным/иррациональным, вдоль пути сумма рациональных размеров прямоугольников даст иррациональное число (сторона квадрата) - противоречие.

[zykov]

Source of the post (Тут не важно, сольются ли две изначально не связные области, или так и останутся две не связанные друг с другом области.)

Не совсем так. Нужно начать заливать не с двух точек, а со всех синих точек на верхней границе. Тогда изначально будет конечное количество несвязных областей (или может просто одна связная). По окончании заливки они могут слится или нет - не важно.

По алгоритму, у нас есть конечное количество дискретных объектов - прямоугольников и отрезков. На каждом шаге мы расширяем текущее множество зеленых объектов, добавляя к нему те синие объекты, которые касаются зеленых. За конечное количество шагов алгоритм завершится (когда нельзя добавить новый объект к множеству зеленых), т.к. количество объектов конечно. При этом синие объекты могут остатся, а могут и не остатся - не важно.

Первый шаг алгоритма - перекрашиваем все синие прямоугольники касающиеся верхней границы в зеленый.