Числа Шура: раскраски без монохромных троек

Возьмём отрезок натуральных чисел от $1$ до $n$ и раскрасим их в несколько цветов. Можно ли сделать это так, чтобы ни в одном цвете не нашлось тройки $x, y, z$ с условием $x + y = z$? Оказывается, при достаточно большом $n$ это становится невозможным при любой раскраске - обязательно появится одноцветное (монохромное) решение уравнения. Число Шура $S(r)$ отвечает на вопрос: до какого предела ещё можно «увернуться» от такой тройки, имея $r$ цветов. Ниже разберём определение, точные значения, доказательство существования и связь чисел Шура с числами Рамсея.

Что такое число Шура

Зафиксируем число цветов $r$. Число Шура $S(r)$ - это наибольшее $n$, при котором множество $\{1, 2, \ldots, n\}$ можно раскрасить в $r$ цветов так, чтобы ни в одном цветовом классе не было решения уравнения

$$x + y = z,$$

где $x, y, z$ принадлежат одному цвету (при этом разрешается $x = y$). Раскраску без монохромных троек называют бессуммной по цветам: каждый цвет образует так называемое суммобессуммное множество.

Как только мы переходим к $n = S(r) + 1$, увернуться уже нельзя: в любой раскраске чисел $1, \ldots, S(r)+1$ в $r$ цветов найдётся хотя бы одна монохромная тройка $x + y = z$. Именно эта граница и есть содержание теоремы Шура, доказанной Иссаи Шуром в 1916 году.

Чтобы прочувствовать определение, удобно сразу повозиться с раскраской руками: возьмите небольшой $n$, раскидайте числа по цветам и попробуйте не допустить тройки. Инструмент ниже соберёт для вас точную учебную постановку по числам Шура и отправит её в разбор.

Маленький пример: почему S(1) = 1

Начнём с одного цвета. Если $n = 1$, то единственное число - это $1$, и тройку $x + y = z$ из него собрать нельзя: минимальная сумма $1 + 1 = 2$ уже выходит за пределы множества. Значит, для $n = 1$ монохромного решения нет, раскраска (тривиальная, в один цвет) подходит.

А вот при $n = 2$ всё ломается: числа $1$ и $2$ дают $1 + 1 = 2$ - это монохромная тройка, ведь цвет один. Уйти от неё некуда. Поэтому наибольшее $n$, при котором одноцветная раскраска ещё проходит, равно $1$, то есть $S(1) = 1$.

Рассчитать для своей задачи

Этот крошечный пример показывает главный механизм: число Шура измеряет, насколько долго удаётся «прятать» суммы по разным цветам, прежде чем комбинаторика заставит их встретиться внутри одного класса.

Точные значения S(r)

Известных точных значений чисел Шура немного - задача вычислительно тяжёлая. На сегодня надёжно установлены пять:

$$S(1) = 1, \quad S(2) = 4, \quad S(3) = 13, \quad S(4) = 44, \quad S(5) = 160.$$

Значение $S(2) = 4$ проверяется почти вручную. Раскрасим $\{1, 2, 3, 4\}$ так: цвет А - числа $1$ и $4$, цвет Б - числа $2$ и $3$. В цвете А сумма $1 + 1 = 2$ ведёт в другой цвет, $1 + 4 = 5$ выходит за пределы, $4 + 4 = 8$ тоже - монохромной тройки нет. В цвете Б: $2 + 2 = 4$ уходит в цвет А, $2 + 3 = 5$ за пределами, $3 + 3 = 6$ за пределами - снова чисто. Значит, $\{1,2,3,4\}$ раскрашивается без троек, а вот для пятёрки уже доказуемо нельзя, поэтому $S(2) = 4$.

Дальше сложность растёт стремительно. Значение $S(5) = 160$ было установлено лишь в 2017 году масштабным компьютерным перебором (проект на основе SAT-решателей с проверяемым сертификатом); $S(6)$ до сих пор точно неизвестно. Темп роста этих чисел тесно связан с числами Рамсея, о чём ниже.

Теорема Шура: почему монохромная тройка неизбежна

Утверждение, что $S(r)$ конечно при любом $r$, и есть теорема Шура: для каждого числа цветов $r$ существует такое $N$, что при любой раскраске $\{1, \ldots, N\}$ в $r$ цветов найдётся монохромное решение $x + y = z$.

Идея доказательства - свести задачу к рамсеевскому факту о монохромных треугольниках, который сам близок к сюжетам раскраски графов. Возьмём полный граф на вершинах $1, 2, \ldots, N$ и покрасим его рёбра: ребро между вершинами $i$ и $j$ (пусть $i < j$) получает тот же цвет, что число $j - i$ в нашей раскраске чисел. Если $N$ достаточно велико (больше числа Рамсея $R_r(3)$ для $r$ цветов и треугольников), то по теореме Рамсея в графе обязательно найдётся монохромный треугольник на вершинах $a < b < c$.

Рассмотрим разности: $x = b - a$, $y = c - b$, $z = c - a$. Все три ребра треугольника одного цвета, значит числа $x$, $y$, $z$ одного цвета в нашей раскраске. При этом

$$x + y = (b - a) + (c - b) = c - a = z.$$

Получили монохромную тройку $x + y = z$ - ровно то, что требовалось. Конечность $S(r)$ доказана, а заодно мы получили оценку $S(r) < R_r(3)$.

Рассчитать для своей задачи

Связь с числами Рамсея

Числа Шура - частный, «арифметический» случай общей рамсеевской философии: в достаточно большой структуре нельзя избежать упорядоченности. Из доказательства выше прямо следует оценка

$$S(r) \le R_r(3) - 1,$$

где $R_r(3)$ - число Рамсея для $r$ цветов и монохромного треугольника. Снизу же справедливо $S(r) \ge \tfrac{1}{2}(3^r - 1)$, что даёт экспоненциальный рост: каждый дополнительный цвет примерно утраивает «пространство для манёвра».

Сравним известные значения. Для трёх цветов $S(3) = 13$, тогда как $R_3(3) = 17$ (классическое число Рамсея для треугольников в трёх цветах) - оценка $S(3) \le 16$ выполняется с запасом. Эта пара показывает, что числа Шура чуть «мягче» полных рамсеевских: монохромная тройка разностей появляется раньше, чем произвольный монохромный треугольник в самом общем смысле.

Где это встречается и зачем

Помимо чистой комбинаторики, теорема Шура - один из первых результатов аддитивной комбинаторики и теории Рамсея на числах. Исторически Шур доказал её, изучая малые решения теоремы Ферма по модулю простого: он показал, что уравнение $x^k + y^k \equiv z^k \pmod{p}$ имеет нетривиальные решения для всех достаточно больших простых $p$ - и монохромные суммы возникли как инструмент.

Сегодня числа Шура - стандартный сюжет курсов дискретной математики и олимпиадной подготовки: они компактно демонстрируют, как принцип Дирихле и теорема Рамсея превращаются в конкретную числовую границу. Базовый счётный аппарат, на котором всё это держится, - правило суммы и произведения и принцип Дирихле, с которых и начинается комбинаторика.

Частые ошибки

• Путают $S(r)$ с числом цветов или с самим $n$. $S(r)$ - это максимальный размер отрезка $\{1, \ldots, n\}$, а $r$ - лишь параметр (сколько цветов разрешено). Не наоборот.
• Забывают, что разрешено $x = y$. Тройка $x + x = 2x$ тоже монохромная и тоже запрещена внутри цвета - это часто упускают при ручной проверке.
• Считают, что граница «работает в обе стороны мягко». При $n = S(r)$ безопасная раскраска существует, но уже при $n = S(r) + 1$ её нет ни одной - переход резкий, а не постепенный.
• Смешивают числа Шура и числа Рамсея. Они связаны оценкой $S(r) \le R_r(3) - 1$, но это разные величины: Шур - про суммы разностей, Рамсей - про монохромные подграфы вообще.
• Думают, что все $S(r)$ известны. Точно вычислены лишь $S(1)$–$S(5)$; уже $S(6)$ открыто.

FAQ

Чем число Шура отличается от числа Рамсея? Число Рамсея $R_r(3)$ гарантирует монохромный треугольник в раскрашенном графе, а число Шура $S(r)$ - монохромную тройку $x + y = z$ среди чисел. Шур доказывается через Рамсея и даёт оценку $S(r) \le R_r(3) - 1$, поэтому числа Шура всегда чуть меньше.

Почему $S(5)$ так трудно было найти? Пространство раскрасок растёт экспоненциально: проверить вручную, что для $n = 161$ при пяти цветах монохромная тройка неизбежна, невозможно. Значение $S(5) = 160$ получили в 2017 году распределённым SAT-перебором с машинно-проверяемым сертификатом доказательства.

Что такое суммобессуммное множество? Это множество чисел, в котором нет решения $x + y = z$ с элементами самого множества. В задаче Шура каждый цвет должен быть таким множеством; число Шура измеряет, как долго удаётся разбить отрезок на $r$ суммобессуммных классов.

Коротко

Число Шура $S(r)$ - наибольший размер отрезка $\{1, \ldots, n\}$, который можно раскрасить в $r$ цветов без монохромной тройки $x + y = z$. Теорема Шура гарантирует, что $S(r)$ конечно: через теорему Рамсея монохромный треугольник разностей неизбежен при больших $n$. Точно известны $S(1)=1$, $S(2)=4$, $S(3)=13$, $S(4)=44$, $S(5)=160$; рост экспоненциальный и ограничен сверху числами Рамсея.