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

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

Условие

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

Решение

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

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

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

M1589

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

Замечание

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

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

А. Канель

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

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