МатематикаПрепринтТеория3 мин чтения

ЕДИНСТВЕННАЯ РУКА В МАДЖОНГЕ, КОТОРАЯ ЖДЁТ ЛЮБУЮ КОСТЬ

В маджонг играют костями с достоинствами от 1 до 9 в трёх мастях, по четыре копии каждой кости. Чтобы выиграть, игрок должен собрать одну пару и четыре сета, где сет — это либо три одинаковые кости, либо три кости последовательных достоинств. Игроки по очереди берут и сбрасывают кости в надежде собрать такую руку.

Среди всех возможных рук одна имеет легендарный статус. «Девять врат» состоит из тринадцати костей одной масти: 1-1-1, 2, 3, 4, 5, 6, 7, 8, 9-9-9. Какая бы кость этой масти ни пришла следующей, рука становится полной. Возьмём, например, 5: пара — 5-5, а сеты — 1-1-1, 2-3-4, 6-7-8 и 9-9-9. Это «девятистороннее ожидание» приносит награду высшей категории во многих вариантах игры.

Народная теорема, проверенная машиной

Игроки давно считали, что «Девять врат» — единственная рука из одной масти с таким свойством, если соблюдается правило четырёх копий каждой кости. До сих пор эта уверенность опиралась на компьютеры. Исследование 2019 года перебрало все 93 600 возможных рук из тринадцати костей одной масти и подтвердило это; другое классифицировало все схемы ожидания по 828 категориям.

Шубинь Сюэ (Shubin Xue) из Пекинского технологического института и Синъюй Чжун (Xingyu Zhong) из Национального университета Сингапура хотели получить доказательство, которое объясняет, а не пересчитывает. Они также задались более широким вопросом. Что, если в масти 3n достоинств вместо девяти, а для выигрышной руки нужны одна пара и n + 1 сетов? Обычный маджонг — это случай n = 3.

Восемь рук, одна выжившая

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

В обычном маджонге один из самозванцев выглядит как 1-1-1, 2, 3, 4, 5, 6-6-6-6, 7, 8. Другой — 2, 3, 4-4-4-4, 5, 6-6-6-6, 7, 8, симметричный относительно своей середины.

Доказательство обходится без полного перебора и не предполагает ответ заранее. Оно работает с руками как со списками количеств костей каждого достоинства и отслеживает, какую пару может использовать для выигрыша каждая взятая кость. Выясняются два факта: рука, ожидающая любое достоинство, всегда содержит каждое внутреннее достоинство хотя бы один раз, и её всегда можно разбить на две пары плюс набор сетов. Для меньшего числа сетов — скажем, пары и трёх сетов на девяти достоинствах — авторы показывают, что ни одна рука не ждёт любую кость.

Когда рука растёт

В тайваньском маджонге используются руки из шестнадцати костей: одна пара и пять сетов. Там это свойство становится обычным, потому что добавление сетов к ожидающей руке сохраняет ожидание. Компьютерный поиск авторов находит 149 рук, ждущих любую кость, из которых 11 действительно можно сыграть, что подтверждает более ранний подсчёт. Чтобы обуздать это изобилие, авторы предлагают сосредоточиться на «минимальных» руках, которые нельзя сократить, убрав сеты, и выдвигают гипотезу о формуле для наибольшего числа сетов, которое может использовать такая рука.

Доказательство, которое проверяется машиной

Авторы создают формальную версию своего доказательства в Lean — языке программирования для проверяемой математики — и описывают эту работу как продолжающуюся и курируемую вручную. Они указывают, что модели GPT и Gemini помогали составлять и редактировать рукопись, доказывать вспомогательные леммы, писать черновики кода на Lean и исследовать направления работы, и что каждое рассуждение авторы независимо проверили. Онлайн-инструмент позволяет любому самостоятельно исследовать эти руки.