2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 18:44 


27/04/18
40
mihaild в сообщении #1308400 писал(а):
EvgenyNechaev в сообщении #1308389 писал(а):
Правильный шестиугольник с длиной стороны равной запрещённому расстоянию.
Который? На плоскости континуальное число шестиугольников с данной длиной стороны.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 20:36 
Заслуженный участник
Аватара пользователя


01/03/06
13488
Москва
EvgenyNechaev в сообщении #1308405 писал(а):
Верно, но каждый из них является подграфом бесконечного графа единичных расстояний плоскости, вершинами которого являются все точки плоскости.

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

 Профиль  
                  
 
 Задача Нелсона-Хадвигера (вариант второй, комбинаторный)
Сообщение30.04.2018, 14:27 


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

Решение:

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение30.04.2018, 15:53 


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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера (вариант второй, комбинаторный)
Сообщение30.04.2018, 16:03 
Экс-модератор
Аватара пользователя


23/12/05
11530
EvgenyNechaev в сообщении #1308756 писал(а):
1. Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера (вариант второй, комбинаторный)
Сообщение30.04.2018, 17:13 


27/04/18
40
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, замечание за дублирование темы.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение30.04.2018, 18:05 
Экс-модератор
Аватара пользователя


23/12/05
11530
Откуда у вас появились какие-то запреты на углы поворота? Почему только кратно $60$ градусам? В вашем доказательстве нет обоснования для такого ограничения. А следуя условию
EvgenyNechaev в сообщении #1308756 писал(а):
1. Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет.
без дополнительных ограничений вы получите ровно то, что я написал выше: произвольные расстояния между точками одного цвета. Пока вы не пропишете в явном виде почему и откуда у вас берутся ограничения, остается только догадываться и, соответственно, нет никакого смысла пытаться проверять огрызки доказательства.

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение30.04.2018, 18:12 
Заслуженный участник
Аватара пользователя


16/07/14
3853
Москва
EvgenyNechaev в сообщении #1308789 писал(а):
Нет, нельзя найти.
Упражнение: доказать, что в транзитивном замыкании отношении "лежать на расстоянии $x$" лежат все возможные пары точек.
Видимо, вы под
EvgenyNechaev в сообщении #1308756 писал(а):
Любые две точки на плоскости, расположенные друг от друга на расстоянии $\sqrt{3}$, окрашены в один и тот же цвет
подразумевали что-то другое (это предложение создает впечатление, что вы предлагаете раскраску с каким-то свойством), но что именно - понять нельзя.
EvgenyNechaev в сообщении #1308756 писал(а):
Радиус $\varepsilon$-окрестности точки равен запрещённому расстоянию

Brukvalub в сообщении #1308428 писал(а):
Бессмысленная фраза, просто наукообразный набор слов

EvgenyNechaev в сообщении #1308756 писал(а):
покажем, что при любом выборе шести точек в круге радиуса $\sqrt{3}$ найдётся пара точек, удалённых одна от другой более чем на $\sqrt{3}$.
Очевидная неправда - в любом нетривиальном круге можно найти сколько угодно точек на сколь угодно малом расстоянии друг от друга.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение30.04.2018, 18:24 


27/04/18
40
photon в сообщении #1308814 писал(а):
Откуда у вас появились какие-то запреты на углы поворота? Почему только кратно $60$ градусам? В вашем доказательстве нет обоснования для такого ограничения.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение30.04.2018, 18:26 
Экс-модератор
Аватара пользователя


23/12/05
11530
Brukvalub в сообщении #1308428 писал(а):
EvgenyNechaev в сообщении #1308405 писал(а):
Верно, но каждый из них является подграфом бесконечного графа единичных расстояний плоскости, вершинами которого являются все точки плоскости.

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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение30.04.2018, 18:41 


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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение30.04.2018, 18:50 
Заслуженный участник
Аватара пользователя


16/07/14
3853
Москва
EvgenyNechaev в сообщении #1308831 писал(а):
без введения дополнительной терминологии
Ни разу не видел, чтобы здесь кого-то критиковали за введение дополнительной терминологии. Только нужно ее аккуратно и явно ввести. Что-то типа "гладиолусом радиуса $r$ вокруг точки $x$ назовем множество точек, лежащих на расстоянии не более $r$ от точки $x$, имеющих тот же цвет, что и $x$, и имеющих точки хотя бы четырех других цветов на расстоянии не более $\frac{r}{10}$ от себя".

EvgenyNechaev в сообщении #1308831 писал(а):
если окружность окрашена в зелёный цвет, то каждая её точка окрашена в другой зелёный цвет
В другой по отношению к чему? И да, непонятно, что такое "другой зеленый цвет".
Можете просто считать, что в каждой точке плоскости написано натуральное число от $1$ до количества цветов.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение01.05.2018, 00:24 
Заслуженный участник
Аватара пользователя


01/03/06
13488
Москва
EvgenyNechaev в сообщении #1308831 писал(а):
если окружность окрашена в зелёный цвет, то каждая её точка окрашена в другой зелёный цвет, позднее попробую объяснить языком теории множеств.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение01.05.2018, 12:51 


27/04/18
40
Третий вариант решения. Жду конструктивной критики.

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

Решение:

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

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

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение01.05.2018, 12:58 
Модератор
Аватара пользователя


20/03/14
10557
EvgenyNechaev в сообщении #1309058 писал(а):
все точки плоскости становятся в некотором смысле изолированными.

EvgenyNechaev в сообщении #1309058 писал(а):
(множество точек) относительно запрещённого расстояния $1$ является разрешимым множеством.
EvgenyNechaev в сообщении #1309058 писал(а):
дискретной плоскостью.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 74 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group