Задача Нелсона-Хадвигера

[EvgenyNechaev]

mihaild в сообщении #1308400 писал(а):

EvgenyNechaev в сообщении #1308389 писал(а):

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

Который? На плоскости континуальное число шестиугольников с данной длиной стороны.

Верно, но каждый из них является подграфом бесконечного графа единичных расстояний плоскости, вершинами которого являются все точки плоскости.

[Brukvalub]

EvgenyNechaev в сообщении #1308405 писал(а):

Верно, но каждый из них является подграфом бесконечного графа единичных расстояний плоскости, вершинами которого являются все точки плоскости.

Бессмысленная фраза, просто наукообразный набор слов.

[EvgenyNechaev]

Формулировка: каково хроматические число метрического пространства по отношению к запрещенному расстоянию $1$?

Решение:

1. Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет.

2. Радиус $\varepsilon$-окрестности точки равен запрещённому расстоянию, т.е. на расстоянии меньше запрещённого не может существовать двух точек.

3. Докажем, что шести цветов для раскраски плоскости недостаточно. Для этого покажем, что при любом выборе шести точек в круге радиуса $\sqrt{3}$ найдётся пара точек, удалённых одна от другой более чем на $\sqrt{3}$. Произведём построение, показанное на рисунке. Радиус большой окружности равен $\sqrt{3}$, радиус малой $1$.


4. По принципу Дирихле так как число клеток больше, чем число точек, то как минимум одна клетка пуста, т.е. такая пара точек найдётся.

5. Следовательно, мы можем построить вокруг нее одноцветную окружность радиусом $\sqrt{3}$ Между некоторыми точками этой окружности точно будет расстояние $1$, что противоречит условию.

6. Вывод: хроматическое число плоскости по отношению к запрещённому расстоянию $1$ равно $7$.

Аналогично для трехмерного пространства, ответ $13$.

[EvgenyNechaev]

Готов второй вариант решения, гораздо более формальный.
topic126659.html

Lia: темы объединены. EvgenyNechaev, замечание за дублирование темы.

[photon]

EvgenyNechaev в сообщении #1308756 писал(а):

1. Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет.

Это как? Рассмотрим точку, покрашенную в какой-то цвет. Если следовать вашему утверждению, то все точки, лежащие на окружности радиусом $\sqrt{3}$ с центром в выбранной точке, покрашены в один и тот же цвет. Но на этой окружности можно всегда найти пару точек, удаленных друг от друга на любое наперед заданное расстояние от $0$ до $2\sqrt{3}$, в том числе и запрещенное единичное.

[EvgenyNechaev]

photon в сообщении #1308776 писал(а):

Рассмотрим точку, покрашенную в какой-то цвет. Если следовать вашему утверждению, то все точки, лежащие на окружности радиусом $\sqrt{3}$ с центром в выбранной точке, покрашены в один и тот же цвет. Но на этой окружности можно всегда найти пару точек, удаленных друг от друга на любое наперед заданное расстояние от $0$ до $2\sqrt{3}$, в том числе и запрещенное единичное.

Нет, нельзя найти. Возьмем ромб, состоящий из двух склеенных между собой по стороне правильных единичных треугольников, и попытаемся его раскрасить. Две склеенных вершины пусть будут синего и красного цвета, а оставшиеся две либо окажутся третьего, например зеленого, цвета либо также разных цветов, например зелёного и жёлтого. В первом случае расстояние между двумя зелеными вершинами равно $\sqrt{3}$. Повторим это построение ещё $2$ раза, поворачивая ромб на $60$ градусов и получим либо $6$ одинаково раскрашенных точек, лежащих на окружности радиуса $\sqrt{3}$ на расстоянии $\sqrt{3}$ друг от друга (и больше точки впихивать некуда), то есть никаких противоречий с условием задачи не возникнет, либо вынуждены будем признать, что хроматическое число Веретена Мозера относительно запрещённого расстояния равно $7$.

-- 30.04.2018, 19:18 --

EvgenyNechaev в сообщении #1308774 писал(а):

Готов второй вариант решения, гораздо более формальный.
topic126659.html

Lia: темы объединены. EvgenyNechaev, замечание за дублирование темы.

Прощу прощения, посчитал что принципиально другое решение должно быть выделено в отдельное обсуждение.

[photon]

Откуда у вас появились какие-то запреты на углы поворота? Почему только кратно $60$ градусам? В вашем доказательстве нет обоснования для такого ограничения. А следуя условию

EvgenyNechaev в сообщении #1308756 писал(а):

1. Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет.

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

[mihaild]

EvgenyNechaev в сообщении #1308789 писал(а):

Нет, нельзя найти.

Упражнение: доказать, что в транзитивном замыкании отношении "лежать на расстоянии $x$" лежат все возможные пары точек.
Видимо, вы под

EvgenyNechaev в сообщении #1308756 писал(а):

Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет

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

EvgenyNechaev в сообщении #1308756 писал(а):

Радиус $\varepsilon$-окрестности точки равен запрещённому расстоянию

Brukvalub в сообщении #1308428 писал(а):

Бессмысленная фраза, просто наукообразный набор слов

EvgenyNechaev в сообщении #1308756 писал(а):

покажем, что при любом выборе шести точек в круге радиуса $\sqrt{3}$ найдётся пара точек, удалённых одна от другой более чем на $\sqrt{3}$.

Очевидная неправда - в любом нетривиальном круге можно найти сколько угодно точек на сколь угодно малом расстоянии друг от друга.

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

[EvgenyNechaev]

photon в сообщении #1308814 писал(а):

Откуда у вас появились какие-то запреты на углы поворота? Почему только кратно $60$ градусам? В вашем доказательстве нет обоснования для такого ограничения.

Нет у меня никаких ограничений на угол поворота. Я лишь показал, что достаточно всего $2$ раза повернуть ромб для того, чтобы получить 6 точек на окружности, чего, в свою очередь, достаточно для того, чтобы либо согласиться с тем что окружность радиуса $\sqrt{3}$ окрашена в один цвет, либо отказаться от принципа жадной раскраски.

[photon]

Brukvalub в сообщении #1308428 писал(а):

EvgenyNechaev в сообщении #1308405 писал(а):

Верно, но каждый из них является подграфом бесконечного графа единичных расстояний плоскости, вершинами которого являются все точки плоскости.

Бессмысленная фраза, просто наукообразный набор слов.

Думаю, имеется в виду следующее: при решении задачи про хроматическое число плоскости строится бесконечный граф, вершинами которого являются все точки плоскости, а ребра соединяют вершины, соответствующие точкам, расположенным на единичном расстоянии друг от друга. Действительно, любой правильный шестиугольник с единичной стороной будет подграфом этого бесконечного графа, но танцы с бубном вокруг этих шестиугольников у ТС для меня остаются загадкой.

[EvgenyNechaev]

mihaild в Видимо, вы под[quote="EvgenyNechaev в [url=http://dxdy.ru/post1308756.html#p1308756]сообщении #1308756 писал(а):

Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет подразумевали что-то другое (это предложение создает впечатление, что вы предлагаете раскраску с каким-то свойством), но что именно - понять нельзя.

Я (пока) не могу объяснить очевидное мне, но непонятное Вам, без введения дополнительной терминологии и слишком мало знаком с теорией множеств чтобы попытаться объяснить на строго формальном языке. Сейчас я немного обману вас и скажу, что если окружность окрашена в зелёный цвет, то каждая её точка окрашена в другой зелёный цвет, позднее попробую объяснить языком теории множеств.
Вопрос в другом: если (пока) принять п.1 как аксиому, верно ли остальное решение?

[mihaild]

EvgenyNechaev в сообщении #1308831 писал(а):

без введения дополнительной терминологии

Ни разу не видел, чтобы здесь кого-то критиковали за введение дополнительной терминологии. Только нужно ее аккуратно и явно ввести. Что-то типа "гладиолусом радиуса $r$ вокруг точки $x$ назовем множество точек, лежащих на расстоянии не более $r$ от точки $x$, имеющих тот же цвет, что и $x$, и имеющих точки хотя бы четырех других цветов на расстоянии не более $\frac{r}{10}$ от себя".

EvgenyNechaev в сообщении #1308831 писал(а):

если окружность окрашена в зелёный цвет, то каждая её точка окрашена в другой зелёный цвет

В другой по отношению к чему? И да, непонятно, что такое "другой зеленый цвет".
Можете просто считать, что в каждой точке плоскости написано натуральное число от $1$ до количества цветов.

EvgenyNechaev в сообщении #1308831 писал(а):

Вопрос в другом: если (пока) принять п.1 как аксиому, верно ли остальное решение?

Т.к. п.1 не является законченным утверждением, то принять его как аксиому нельзя. Если его сформулировать в виде "существует раскраска плоскости, при которой любые точки на расстоянии $\sqrt{3}$ друг от друга окрашены в один цвет, а любые две точки на расстоянии $1$ - в разные", то да, его добавление в качестве аксиомы позволит доказать, что хроматическое число плоскости равно $7$. А заодно - что это число равно $42$, $\spadesuit^\Join$ и желтым ботинкам.

[Brukvalub]

EvgenyNechaev в сообщении #1308831 писал(а):

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

Кажется, я понял! Есть разные зеленые цвета - зеленый , зеленый и зеленый, и окружность окрашена не просто в зеленый цвет, а в зеленый, который не тот зеленый, а этот зеленый!
Тут никакого языка-то и не требуется, все и так понятно!

[EvgenyNechaev]

Третий вариант решения. Жду конструктивной критики.

Формулировка: каково хроматические число метрического пространства по отношению к запрещенному расстоянию $1$?

Решение:

1. Возьмём плоскость (назовём её моноплоскость) все точки которой окрашены в один цвет.

1. Определим запрещённое расстояние как расстояние на котором все точки плоскости становятся изолированными в некотором смысле.

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

3. Определим дискретную плоскость как геометрическое место точек, находящихся друг от друга на некотором расстоянии. Плоскость относительно запрещённого расстояния является дискретной плоскостью.

4. Следовательно, можно утверждать что все точки на плоскости находятся в общем положении.

5. Бесконечное множество точек в общем положении содержит пустой шестиугольник. Доказано, и тут, длина стороны этого шестиугольника равна $1$.

6. Возьмём плоскость (назовём её хроматическая плоскость) каждая точка которой окрашена в уникальный цвет, отличный от цвета моноплоскости.

7. Наложим плоскости друг на друга, получим 6 новый точек на моноплоскости, окрашенных в уникальные цвета.

Вывод: хроматическое число плоскости равно $7$ при расстоянии между точками $1$ и запрещённом расстоянии $1$.

[Lia]

EvgenyNechaev в сообщении #1309058 писал(а):

все точки плоскости становятся в некотором смысле изолированными.

EvgenyNechaev в сообщении #1309058 писал(а):

(множество точек) относительно запрещённого расстояния $1$ является разрешимым множеством.

EvgenyNechaev в сообщении #1309058 писал(а):

дискретной плоскостью.

EvgenyNechaev в сообщении #1309058 писал(а):

в общем положении.

...
Пока хватит. Определяйте понятия.