537 ЧИСЕЛ, ШЕСТЬ ЦВЕТОВ, НИ ОДНОЙ СУММЫ

Вот головоломка, понятная даже ребёнку. Возьмите числа 1, 2, 3 и так далее. Дайте каждому цвет. Единственное правило: внутри одного цвета нельзя найти два числа вместе с их суммой. Два числа могут даже совпадать, так что если 2 красное, то 4 не может быть красным, потому что 2 + 2 = 4.

Множество без таких троек называется свободным от сумм. Как далеко можно продвинуться, прежде чем правило заставит остановиться? Этот предел для k цветов — число Шура S(k). Задача восходит к статье И. Шура 1916 года — первой позиции в списке литературы.

Знаменито упрямая последовательность

С одним цветом вы застреваете сразу: 1 + 1 = 2, так что цвет может содержать лишь число 1. Известные значения:

• S(1) = 1
• S(2) = 4
• S(3) = 13
• S(4) = 44
• S(5) = 160 — его установил М. Дж. Х. Хёле (в статье, опубликованной в 2018 году).

Для шести цветов ответа не знает никто. С 2000 года лучшая известная конструкция, найденная Х. Фредриксеном и М. М. Свитом с помощью перебора симметричных раскрасок, доходила до 536. С тех пор это число и цитируется как лучшая нижняя оценка — это нижний предел: S(6) не меньше этого числа, а его истинное значение, пока неизвестное, может оказаться и больше.

Ещё одно число

Чжиян Чэнь и Фань Лун из Университета Торонто и Лигэн Чжу из NVIDIA Research теперь довели её до 537. Их доказательство из тех, что математики любят за прямоту: они печатают ответ. Шесть списков чисел — из 76, 76, 88, 70, 76 и 151 числа, — которые вместе содержат каждое целое число от 1 до 537 ровно один раз, причём ни один цвет не содержит x, y и x + y. Проверка сводится к тому, чтобы перебрать все суммы внутри каждого списка, — быстрая работа для компьютера.

У решения поразительная форма. Оно симметрично: каждое число x имеет тот же цвет, что и 538 − x. Первые четыре цвета начинаются с 1, 2, 3 и 4; пятый появляется только с 38, шестой — только со 151, и шестой цвет заполняет весь средний участок от 237 до 301. Даже первый цвет можно восстановить из «зерна» всего из 14 небольших чисел с помощью зеркального отражения, сдвига и одного добавленного числа.

Волны выше по лестнице

Числа Шура подпитывают друг друга. Известные рецепты превращают хорошую раскраску в k цветов в раскраску в k + 2 или k + 5 цветов: S(k + 2) не меньше 10 S(k) + 2, а S(k + 5) — не меньше 380 S(k) + 148. Поэтому новое 537 поднимает и другие рекорды:

• восемь цветов: с 5362 до 5372 — и эту раскраску команда тоже построила явно;
• одиннадцать цветов: с 203 828 до 204 208;
• тринадцать цветов: с 2 038 282 до 2 042 082.

Это улучшает и одно число Рамсея, R₆(3): наименьшее число точек, попарно соединённых связями, при котором любая раскраска связей в шесть цветов обязательно содержит одноцветный треугольник. Пронумеруйте 538 точек от 0 до 537 и покрасьте связь между i и j в цвет их разности |i − j|: раскраска, свободная от сумм, не оставляет ни одного одноцветного треугольника. Значит, R₆(3) не меньше 539, тогда как прежняя оценка была 538.

131 способ это сделать

Поиск нашёл не одно решение, а 131 действительно различное; авторы разбивают их на пять семейств и публикуют целиком. Большинство очень близки к первому: решения из семейств F1–F4 совпадают с ним как минимум в 462 из 537 позиций. Одно семейство нарушает зеркальную симметрию; другое построено смешиванием трёх перетасованных копий исходного.

В статье не объясняется, как именно проводился сам поиск. Авторы подчёркивают, что их 131 раскраска — не полный каталог решений с шестью цветами, а лишь свежие отправные точки для всех, кто захочет попытаться дойти до 538.