Я познакомился с Александром Карабеговым во время Всесоюзной математической олимпиады в Ереване. Он был на год старше меня. К тому времени, когда я участвовал в олимпиаде в 1976 году, он уже был первокурсником МГУ.
Он предложил две связанные задачи для Московской олимпиады, которые мне нужно было решить.
Задача 1. Дано конечное число точек на плоскости. Докажите, что существует точка, у которой не более трёх ближайших соседей.
Под ближайшими соседями подразумеваются все точки, находящиеся на минимальном расстоянии от данной точки. Я уверен, что решил обе задачи в то время. Решение первой задачи оставляю читателю.
Задача 2. Можно ли расположить на плоскости конечное число точек так, чтобы у каждой точки было ровно три ближайших соседа?
Последняя задача имеет элегантное решение с 24 точками, выбранными из треугольной сетки.
История продолжилась почти 40 лет спустя, когда Александр прислал мне изображение (ниже) такой конфигурации с 16 точками. Он предполагает, что это минимальная конфигурация.
Гипотеза Карабегова
Любая конечная конфигурация точек на плоскости, в которой каждая точка имеет ровно трёх ближайших соседей, должна содержать не менее 16 точек.
Можете это доказать?
Изначально я не хотел приводить решение для 24 точек, но изображение выше — это большая подсказка, так что вот оно:
Обе конструкции выявляют один и тот же основной паттерн. Конструкции состоят из ромбов, образованных двумя равносторонними треугольниками, и ромбы соединены друг с другом. Конструкция из 24 точек состоит из 6 ромбов, а конструкция из 16 точек — из 4 ромбов.
Что произойдёт, если мы попробуем построить конструкцию с 3 ромбами? На изображении ниже показана такая конфигурация, в которой теперь есть дополнительные рёбра с наименьшим расстоянием. Теперь мы видим 3 точки, у каждой из которых более трёх ближайших соседей, что нарушает условие. Так что гипотеза не нарушается.
Пока все более мелкие попытки не увенчались успехом — можете доказать, что 16 — это минимум?