M1589. О свойстве 5-раскрашиваемой карты

Задача из журнала «Квант» (1997, №2)

Условие

Докажите, что как бы ни раскрасить плоскость в 5 цветов, найдутся 2 точки одного цвета, расстояние между которыми отличается от одного не более чем на 0,001.

Решение

Начнём с того, что, поскольку мы должны найти две точки на расстоянии 1 лишь «с точностью до любого \varepsilon», мы можем ограничиться лишь раскрасками сравнительно простых «карт». В самом деле, нарисуем на плоскости мелкую сетку из квадратов или, удобнее, правильных шестиугольников со стороной \varepsilon /4 и раскрасим каждую шестиугольную клетку в тот цвет, который имел в первоначальной раскраске её центр.

Если мы найдём такие точки A, B «с точностью до \varepsilon /2» на новой карте, то центры A^{'}, B^{'} клеток, которым принадлежат A и B, удовлетворяют условию «с точностью до \varepsilon»: ведь \left|AB - A^{'}B^{'}\right|\leq 2\cdot \varepsilon /4\leq \varepsilon /2, так что если \left|1-AB \right|\leq \varepsilon /2, то \left|1-A^{'}B^{'} \right|\leq \varepsilon. Мы можем считать при этом, что границы клеток раскрашены в два (а вершины — в три) цвета.

Предположим, что для некоторой раскраски (и некоторого \varepsilon) утверждение задачи неверно. Рассмотрим случай, когда некоторые три клетки разного цвета имеют общую вершину X. Пусть эти три цвета — Красный, Синий и Белый. Тогда кольцо радиусом 1 с центром X шириной \varepsilon должно быть целиком покрашено в два других цвета- скажем, Чёрный и Зелёный. Если оно целиком одного цвета — Ч, то, очевидно, на нём есть две точки этого цвета на расстоянии 1. В другом случае на кольце есть точка Y двух цветов: Ч и З; тогда достаточно рассмотреть точки кольца на расстоянии 1 от Y (см. рисунок).

M1589

Осталось рассмотреть случай, когда никакие три разных цвета не сходятся вместе. Тогда граница области каждого цвета должна иметь какой-то один определённый цвет — иначе, идя по границе, мы должны были бы наткнуться на тройную точку. Рассмотрим некоторую точку X на границе двух цветов, скажем цветов К и С. Кольцо радиусом 1 (шириной \varepsilon) и центром Y имеет цвета К, С, З. Рассмотрим Зелёную область, содержащую одну из точек пересечения двух колец. У неё не может быть границы одного цвета: в одном из колец она имеет цвета Ч или Б, в другом — К или С. Получили противоречие, завершающее решение.

Замечание

Известна следующая проблема. Плоскость раскрашена в n цветов. При каком n обязательно найдутся две точки на единичном расстоянии? Нетрудно показать справедливость этого утверждения при n=3. При n=7 относительно легко строится контрпример (конструкция типа пчелиных сот). Недавно был построен контрпример при n=6. Про n=4,5 ничего не известно. Известно только, что если раскраска, не допускающая единичных расстояний, существует, то некоторые множества точек одного цвета неизмеримы.

Если же требовать «почти единичных расстояний», то точный ответ таков: n=5 (это следует из построенного ранее контрпримера).

А. Канель

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *