Раскраска точек плоскости

[mencar]

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

[TOTAL]

mencar в сообщении #339482 писал(а):

1.) Можно ли плоскость, замощенную одноцветными квадратами, раскрасить в 7 цветов так, чтобы на расстоянии 1 не было двух точек одного цвета?

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

[mencar]

Предполагается, что каждый цвет есть объединение квадратов

[TOTAL]

mencar в сообщении #339484 писал(а):

Предполагается, что каждый цвет есть объединение квадратов

Что, что?

[gris]

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

[mencar]

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

[gris]

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

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

[mencar]

Цитата:

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

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

[neo66]

Плоскость "правильно" разбита на одинаковые квадраты?

[gris]

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

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

[BapuK]

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

[neo66]

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

[Circiter]

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.