Гипотеза Грэма о перестановке чисел доказана спустя 55 лет

О чём спрашивал Грэм

Возьмём набор различных целых чисел без нуля. Всегда ли можно расставить их так, чтобы все частичные суммы (первые два числа, первые три, первые четыре и так далее) были разными? На языке жонглирования: если каждый мяч остаётся в воздухе разное время, можно ли подобрать порядок бросков, при котором два мяча не упадут в один такт.

Для положительных чисел ответ очевиден: суммы только растут. Известно, что «да» и для смеси положительных и отрицательных. Грэм спросил о конечном мире, то есть о «часовой» арифметике, где числа повторяются после простого числа p. Он предполагал, что ответ по-прежнему положительный.

Случайность и трудный середняк

Сложность зависит от размера набора по сравнению с p. Алп Мюйессер из Оксфорда и Алексей Покровский из Университетского колледжа Лондона занялись наборами, включающими почти все числа до p. Они взяли случайный порядок, отложили несколько специально выбранных чисел и с их помощью исправляли участки, дающие в сумме ноль. Результат был опубликован в 2022 году.

Ноа Кравиц и Бенджамин Бедерт из Оксфорда решили случай совсем небольших наборов и выложили доказательство в сентябре 2024 года. Затем они объединились с Мюйессером и ещё двумя коллегами; работа августа 2025 года охватила больше случаев с крупными наборами. Между двумя областями оставался пробел: наборы среднего размера.

По словам Ноги Алона из Принстонского университета, задачу решили сила сотрудничества, молодого поколения и вероятностных методов.