2014 dxdy logo

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

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




 
 Раскраска точек плоскости
Сообщение16.07.2010, 10:24 
Здравствуйте, у меня такой вопрос:
1.) Можно ли плоскость, замощенную одноцветными квадратами, раскрасить в 7 цветов так, чтобы на расстоянии 1 не было двух точек одного цвета?
2.) Как доказать, что для аналогичной раскраски в случае не с квадратами, а с равносторонними треугольниками, 5-ти цветов будет недостаточно?

 
 
 
 Re: Раскраска точек плоскости
Сообщение16.07.2010, 10:47 
Аватара пользователя
mencar в сообщении #339482 писал(а):
1.) Можно ли плоскость, замощенную одноцветными квадратами, раскрасить в 7 цветов так, чтобы на расстоянии 1 не было двух точек одного цвета?

Какая связь между замощением плоскости квадратами и тем, как раскрасить плоскость?

 
 
 
 Re: Раскраска точек плоскости
Сообщение16.07.2010, 10:57 
Предполагается, что каждый цвет есть объединение квадратов

 
 
 
 Re: Раскраска точек плоскости
Сообщение16.07.2010, 11:00 
Аватара пользователя
mencar в сообщении #339484 писал(а):
Предполагается, что каждый цвет есть объединение квадратов
Что, что?

 
 
 
 Re: Раскраска точек плоскости
Сообщение16.07.2010, 11:42 
Аватара пользователя
в принципе вопрос понятен, только непонятно, как раскрашивать границы квадратов и можно ли делать квадраты полуоткрытыми.
То есть квадрат закрашивается целиком одним цветом, но как быть с общей стороной соседних квадратов? Или точки на сторонах вообще "не считаются"?
Сторона квадрата может быть произвольной, но они все одинаковы?
Ясно, что диагональ квадрата меньше 1. Может быть равна 1, если каждый квадрат включает только правую и нижнюю сторону ( ну или другой угол).
Вот такая раскраска, например, пройдёт для диагонали длиной от 0,7 до 1:
...................................
...123123123123..........
...456456456456...........
...789789789789...........
...123123123123............
.....................................
Она явно избыточна по цветам, но надо же и условие узнать.
Стороны квадратов можно делать как угодно маленькими?

 
 
 
 Re: Раскраска точек плоскости
Сообщение16.07.2010, 11:57 
Общая сторона соседних квадратов может быть закрашена произвольно в цвет одного из этих квадратов, размер сторон не имеет значения

 
 
 
 Re: Раскраска точек плоскости
Сообщение16.07.2010, 12:29 
Аватара пользователя
Если я правильно понял, то нужно доказать, что при произвольном разбиении плоскости на квадраты нельзя для раскраски обойтись 7-ю цветами при условии, что внутренность каждого квадрата закрашена одним цветом, точка на стороне квадрата может закрашиваться в любой из цветов квадрата, для которого она является граничной, и что не существует одноцветных точек на расстоянии 1?

То есть, если в разбиении есть квадрат с диагональю больше 1, то раскраска вообще невозможна.

 
 
 
 Re: Раскраска точек плоскости
Сообщение17.07.2010, 09:35 
Цитата:
нужно доказать, что при произвольном разбиении плоскости на квадраты нельзя для раскраски обойтись 7-ю цветами при условии, что внутренность каждого квадрата закрашена одним цветом, точка на стороне квадрата может закрашиваться в любой из цветов квадрата, для которого она является граничной, и что не существует одноцветных точек на расстоянии 1?

Да, задача именно в этом. А также в случае с разбиением плоскости на правильные треугольники. В случае с квадратами кажется, меньше чем 9 цветами не обойтись, но как это показать?

 
 
 
 Re: Раскраска точек плоскости
Сообщение17.07.2010, 11:40 
Плоскость "правильно" разбита на одинаковые квадраты?

 
 
 
 Re: Раскраска точек плоскости
Сообщение17.07.2010, 11:52 
Аватара пользователя
А это не имеет значения, так как можно показать, что при любом разбиении, в котором существует минимальный размер квадрата, конечно, хотя можно и рассмотреть разбиения в котором нет минимального размера, все размеры относятся рационально, поэтому можно просто взять обыкновенную решётку с соответствующим шагом. Если это называть правильным разбиением.
Или нельзя этого показать? То есть существует разбиение плоскости на квадраты с несоизмеримыми сторонами? Вроде бы я даже и постоил такое на бумажке...

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

 
 
 
 Re: Раскраска точек плоскости
Сообщение17.07.2010, 16:25 
Аватара пользователя
а можно немного уточнить для глупых условие задачи? :oops: т.е. мы берем точку на плоскости проводим окружность радиуса 1 и нужно, чтобы при правильной раскраске на окружности не лежало точек того же цвета, что и центр?

 
 
 
 Re: Раскраска точек плоскости
Сообщение17.07.2010, 17:13 
Да. Минимальное число цветов, в которое можно раскрасить плоскость называется хроматическим числом плоскости. Назовем его $\chi$. Хорошим (легким) упражнением является доказательство того что $\chi > 3$. Известно что $4 \le \chi \le  7$. Больше ничего неизвестно.

 
 
 
 Re: Раскраска точек плоскости
Сообщение21.07.2010, 19:48 
2mencar
Как уже вам сказал neo66, $\chi(\mathbb{R}^2)\leqslant 7$. Этот известный результат может служить ответом к первой задаче. Для ответа на вопрос второй задачи можно воспользоваться неравенством $\chi(\mathbb{R}^2)\geqslant 6$, выполняющимся при замощении плоскости выпуклыми многоугольниками. Вывод этой оценки представлен в доступном on-line конспекте C.F.Miller'а: D.Coulson, On the Chromatic Number of Plane Tilings, J.Aust.Math.Soc. 77 (2004), 191-196.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group