НАИБОЛЬШАЯ СУММА, КОТОРУЮ НЕЛЬЗЯ ЗАПЛАТИТЬ, ТЕПЕРЬ ОЦЕНЕНА ТОЧНО

Представьте кассу, которая принимает лишь несколько видов монет, в неограниченном количестве, и никогда не даёт сдачи. Некоторые суммы можно заплатить точно, другие — никогда. Математики называют номиналы монет образующими (generators) и задают обманчиво простой вопрос: какова наибольшая сумма, которую заплатить нельзя?

Суммы, которые никогда не заплатить

Возьмём целые числа a₁ < a₂ < … < aₙ, у которых нет делителя, общего для всех. Сумма, полученная сложением этих чисел, каждого сколько угодно раз, называется «представимой». Непредставимых целых чисел лишь конечное количество; наибольшее из них — число Фробениуса, F. (Если один из номиналов равен 1, заплатить можно всё, и F полагают равным −1.)

Небольшой пример: монетами 3, 4 и 6 можно заплатить 3, 4, 6, 7, 8 и любую сумму после этого, но никогда 1, 2 или 5. Значит, F = 5. Заметьте, что у 3 и 6 есть общий делитель; важно лишь, чтобы не было делителя, общего для всех трёх.

Для двух монет есть точный ответ — формула Сильвестра: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Для трёх и более работа состоит в том, чтобы оценить F: доказать, что оно не может превышать некоторое значение, вычисляемое по монетам.

Упрямый множитель 2

Пал Эрдёш и Рональд Грэхем доказали для трёх и более образующих:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Здесь aₙ — наибольший номинал, aₙ₋₁ — второй по величине, n — число номиналов, а ⌊ ⌋ означает округление вниз. Как и формула Сильвестра, она задействует две самые крупные монеты.

Они также оценили наихудший случай — наибольшее возможное F, когда все n номиналов не превосходят t. Разрыв между их оценками, примерно в 2 раза, привёл к гипотезе, известной как проблема Эрдёша № 433. Жак Диксмье решил её и заодно доказал более простую оценку, верную для любого набора: F ≤ aₙ²/(n − 1). Множитель 2 исчез, но вместе с ним исчезла и вторая по величине монета.

Сохранить обе самые крупные монеты

Линь Чэнь, Тинвэй Ху, Юйчэнь Мао и Гочуань Чжан из Колледжа компьютерных наук и технологий Чжэцзянского университета хотели и того и другого: никакого множителя 2 — и вторую по величине монету в формуле. Их ответ, верный для любого набора из двух и более номиналов:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Здесь ⌈ ⌉ означает округление вверх. По сравнению с оценкой Эрдёша и Грэхема множитель 2 исчез — ценой деления на n − 1 вместо n и округления вверх. По сравнению с оценкой Диксмье новая может быть существенно меньше, когда вторая по величине монета мала по сравнению с наибольшей.

На примере 3, 4, 6 оценка Эрдёша и Грэхема даёт 10, оценка Диксмье — 18, а новая — 4 × 3 − 6 − 1 = 5, ровно истинное значение. Удивляться нечему: этот набор принадлежит описанному ниже семейству крайних случаев, построенному так, чтобы достигать оценки точно; на типичных наборах статья никакого сравнения не приводит.

Сортировка сумм по остаткам

Доказательство идёт путём Эрдёша и Грэхема. Рассортируем все суммы по остатку от деления на самую крупную монету, aₙ. Как только сумма меньших монет даёт некоторый остаток, добавление копий aₙ позволяет получить любую бо́льшую сумму с тем же остатком. Задача — показать, что каждый остаток достижим дёшево.

Ключевой инструмент — теорема Кнезера о том, насколько большим обязано быть множество сумм. Эрдёш и Грэхем использовали её, чтобы показать, что суммы примерно из aₙ/n монет покрывают больше половины остатков, а затем удвоили их, чтобы покрыть все. Каждая монета в этих суммах стоит не больше aₙ₋₁, поэтому удвоение числа монет удваивает стоимость: отсюда и множитель 2.

Новое доказательство использует суммы из ⌈aₙ/(n − 1)⌉ монет. Когда эти суммы пропускают какие-то остатки, теорема Кнезера говорит, что пропущенные остатки разбросаны не случайно: они образуют целые семейства остатков, расположенных через равные промежутки. Чем больше семейств пропущено, тем больше меньших монет должно скапливаться в каждом достигнутом семействе; поэтому в каждом таком семействе есть несколько маленьких монет, и те немногие дополнительные монеты, которые нужны, чтобы достичь пропущенных семейств, обходятся дёшево. Итог никогда не превышает ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Этот первый шаг даёт оценку без финального «− 1». Последняя единица получается из отдельного рассуждения, опирающегося на теорему Шерка и Кемпермана о суммах, которые можно составить лишь одним способом: оно показывает, что пограничную сумму aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ саму всегда можно заплатить. Согласно разделу благодарностей, авторы сначала доказали более слабую оценку; затем GPT-6 помог найти рассуждение, понижающее её на единицу, а также помог с доказательством того, что оценку нельзя понизить, и с редактурой английского текста. Авторы заявляют, что берут на себя ответственность за окончательный вариант рукописи.

Случаи, точно достигающие предела

Эту оценку нельзя понизить: для каждого n ≥ 3 авторы строят бесконечно много наборов, в которых F в точности равно ей. Возьмём любое q ≥ 2 и номиналы q, 2q, …, (n − 1)q, а также (n − 2)q + 1. Все, кроме одного, кратны q, так что они не оплачивают ничего, чего не могла бы оплатить одна монета q. Набор ведёт себя как две монеты, q и (n − 2)q + 1, и формула Сильвестра даёт F, в точности совпадающее с новой оценкой. При n = 3 и q = 3 этот рецепт даёт именно пример 3, 4, 6, приведённый выше.

Меньше монет — ниже потолок

Оценку можно прочитать и в терминах плотности. Она применима к любому сокращённому набору из i наименьших номиналов плюс наибольший, если у них по-прежнему нет общего делителя. Удаление монет может только затруднить оплату, поэтому потолок, доказанный для сокращённого набора, верен и для полного. Результат определяется примерно величиной aᵢ/i — обратной к тому, насколько плотно первые i номиналов заполняют числа от 1 до aᵢ: побеждает самая плотная группа. В частности, отмечают авторы, вторую по величине монету можно просто отложить в сторону всякий раз, когда у оставшихся монет по-прежнему нет делителя, общего для всех.

Статья остаётся чисто теоретической: в ней нет цифр о том, насколько новая оценка меньше на типичных наборах монет, а её неулучшаемость доказана только для трёх номиналов и более.