Разбиение квадрата

[grizzly]

Думаю, эта задача стоит олимпиадного раздела:

12d3 в сообщении #954668 писал(а):

можно ли квадрат разбить на три множества точек ненулевой меры, чтобы любая тройка точек из разных множеств не лежала на одной прямой?

Надеюсь, автор не будет возражать.

[levtsn]

ясно что нет

[grizzly]

levtsn в сообщении #958413 писал(а):

ясно что нет

Да, забыл предупредить, что это не голослование.

[gris]

А не можно ли ещё усилить? Похоже, что единственный случай, когда не существует такой тройки, это если объединение двух частей есть пересечение квадрата и прямой. Ну, например, два множества заполняют полностью диагональ, а третье — дополнение до квадрата
Хотя, если первое множество просто точка, а второе "конус" с вершиной в нём, то тоже подойдёт.

[grizzly]

gris в сообщении #958471 писал(а):

Хотя, если первое множество просто точка, а второе "конус" с вершиной в нём, то тоже подойдёт.

Множества они такие множества. Поставим в центр квадрата точку, и проведём через неё все возможные прямые $y=kx+b$. Прямые с рациональным $k$ покрасим в цвет одного множества, а с иррациональным -- в цвет другого.

А можете посоветовать какую-нибудь идею доказательства предложенной формулировки? Я замучился с этими раскрасками. Кажется, что всё уже покрасил в 2 цвета и никаких вариантов быть не может, но когда доходит до строгих рассуждений, все эти краски размываются и мутнеют.

[worm2]

Если "ненулевой меры" подразумевается по Жордану, то нельзя.
От противного. Обзовём множества "красным", "синим" и "жёлтым". Пусть квадрат раскрашен в три этих цвета так, что любая пересекающая его прямая покрашена не более чем в 2 цвета. Существуют красный, синий и жёлтый круги радиуса $\varepsilon > 0$. Рассмотрим красный и синий такие круги. Полоса, лежащая между их общими параллельными касательными, покрашена только в красный и синий цвета. Рассмотрим её из центра жёлтого круга. Каждый отрезок её пересечения с лучом, исходящим из центра жёлтого круга, окрашен в один цвет: либо красный, либо синий. Причём есть отрезки и того и другого цветов. Найдутся два таких разноцветных отрезка, лежащих сколь угодно близко друг от друга. Подберём расстояние между ними так, чтобы нашлась прямая, пересекающая их оба и всё ещё пересекающая жёлтый круг. Бинго.

[grizzly]

Спасибо, worm2.
Имелась в виду измеримость по Лебегу (обратите внимание на приведенный мной пример множеств в предыдущем сообщении). Но и этот вариант представлял интерес, чтобы посмотреть, какие возможны идеи доказательства.

Ваша идея в некотором смысле развивает предложенную мной простую идею в первоначальном сообщении (из которого взята ссылка). Я планировал дойти там с ТС до такого обобщения. Это доказательство я видел, вижу также доказательство для двух кругов первых множеств и трёх (а, возможно, и двух) точек третьего -- в этом случае чуть хитрее, но примерно на таком же уровне сложности идеи.

-- 09.01.2015, 14:34 --

grizzly в сообщении #959067 писал(а):

и трёх (а, возможно, и двух) точек третьего

Ой, только сейчас понял, что у Вас то же. Наши идеи изоморфны, хотя я подходил с другой стороны.

[grizzly]

grizzly в сообщении #959067 писал(а):

я видел, я вижу, я умею...

Меняем позицию -- одно из двух: или не умничать, или приводить доказательства. А то потом на поверку, как оказывается, стыда не оберёшься.

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

Пусть, для определённости, множества $A$ и $B$ содержат внутренние точки $a$ и $b$, соответственно. Пусть $x$ -- ближайшая к $a$ точка чужого множества.
1) Если $x\in C$, то прямая, проходящая вблизи точки $b$ через $x$ пересечёт все 3 множества (очевидно в силу шевеления касательной).
2) Пусть $x \in B$. Используя тот же приём касательных, убеждаемся, что все точки $C$ должны лежать на одной прямой, иначе найдём прямую, пересекающую три множества.
2.1) Рассмотрим теперь точку $b$. Рассуждая так же, как в п. 1), получаем, что проблемная ситуация возникает только в случае, когда точка $y$ на границе окрестности $b$ принадлежит $A$. Соединяя $y$ с точками $c\in C$, убеждаемся (как в п.2), что только для точек, лежащих на касательной к кругу с центром в $b$, прямая может не пересечь все множества.
3) Из предыдущих рассуждений заключаем, что единственной точкой в $C$, не дающей нужного решения, может быть только точка пересечения касательных.

Уменьшить третье множество до одной точки невозможно, что показывает пример gris с конусом.

-- 09.01.2015, 18:38 --

В доказательстве есть легко устранимая проблема. Ближайшая точка чужого множества к выбранной внутренней точке может не существовать. Тогда в худшем случае придётся брать нужный супремум в качестве радиуса и рассматривать последовательности "почти"-касательных. Принципиально не испортит, но доказательство удлинится.

-- 09.01.2015, 18:52 --

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

[grizzly]

grizzly в сообщении #959166 писал(а):

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

Это неверно. Касательные не обязаны пересекаться, они могут совпадать. Так же как при обобщении идеи worm2, имеем прямую в третьем множестве. Теперь, с учётом разницы в простоте и эстетике, мою идею "касательных" можно считать ложным следом.

Для обобщения идеи worm2 достаточно иметь по одному отрезку в множествах $A$ и $B$ (не лежащих на одной прямой) и 3 точки множества $C$ (тоже не на одной прямой). Доказательство остаётся дословно авторским. Так что эта идея сильнее. Жить стало немного легче.

gris
Я склонен интуитивно согласиться, что измеримость и ненулевая мера в условии сильно избыточны и достаточно иметь по паре точек в каждом множестве, при условии, что никакие 2 пары из упомянутых не лежат на одной прямой. Но особенно легче от этого не стало :)

[Evgenjy]

Эта задача решается элементарными средствами проективной геометрии. Никакого отношения к теории меры задача не имеет.

[grizzly]

Evgenjy
Никто не собирался решать её методами теории меры :) Эта формулировка естественным образом возникала в процессе обобщений.

Вы согласны побороться с такой формулировкой:
Квадрат разбит на 3 множества. Если в каждом множестве содержится пара точек, и никакие 2 пары из упомянутых не лежат на одной прямой, тогда найдётся прямая, проходящая через точки всех трёх множеств.
?
Я хотел покороче, но если корявость мешает восприятию смысла, можете её подправить под свой вкус -- в любом случае задача самодельная.

Или можете решить хоть что-то большее, чем нам уже удалось. А можно даже и меньшее, если метод будет новым и/или интересным.

В этом разделе Вы можете запросто сразу предлагать свои решения. Чем элементарнее, тем лучше -- это никого не заденет :)

[grizzly]

Пока других идей нет, продолжим эксплуатировать очень плодотворную идею worm2. Оказывается, используя полученное утверждение с двумя отрезками, можно перейти к утверждению с одним отрезком:

Предпоследняя формулировка теоремы:
Квадрат разбит на 3 множества. Пусть множество $A$ содержит отрезок, а множества $B$ и $C$ содержат по паре точек; при этом обе эти пары не лежат на одной прямой и никакая из них не лежит на прямой данного отрезка из $A$. Тогда найдётся прямая, проходящая через точки всех множеств.

Казалось бы не ахти какое обобщение (было два отрезка, остался один), но на самом деле от неё до главной формулировки (см. предыдущее сообщение) осталась всего одна лемма:

Лемма:
Квадрат разбит на 3 множества. Каждое из этих множеств является всюду плотным подмножеством квадрата. Тогда найдётся одна прямая, проходящая через точки всех множеств.

Формулировка леммы может быть интересна сама по себе и в некотором смысле интереснее первоначального утверждения. Если кто поможет с Леммой, я соберу всё в одно целое и оформлю аккуратное доказательство главного утверждения.

[grizzly]

Последнее, что я попытался сделать -- покрасить координатную сетку в целых точках плоскости и посмотреть, нельзя ли как-то воспользоваться любимой мной теорией Рамсея. Оказалось, нельзя -- легко удалось построить масштабируемый на всю плоскость контрпример. Это склонило мою интуицию против Леммы.

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

Здесь есть пример раскраски квадрата и замечательное применение "нашей" теоремы к совсем уж практической задаче (ещё более интересной и красивой) -- это удивило и порадовало.

Подведём итоги. Лемма оказалась неверна. Общими усилиями (в основном благодаря worm2) была получена Теорема в предпоследней формулировке (см. выше) -- она же и оказалась последней в серии обобщений. Можно, конечно, заменить ещё отрезок любым куском непрерывной кривой, но на суть вопроса это уже не влияет.

-- 15.01.2015, 14:12 --

Хотелось бы ещё отдать должное Evgenjy, который точно распознал суть задачи. К сожалению, у меня не было ранее опыта в использовании проективных инструментов -- прочитать доказательство было просто, а догадаться самому совсем нереально.
___________

UPD от 22.04.2016. Ссылка на pdf умерла за это время. Зато появилась страница в ру-вики с ссылкой на журнал Квант, где доказывается та же теорема (про невозможность разбить квадрат на нечётное число треугольников равной площади) с использованием аналогичной техники (см. упражнение 6.b).