Решена математическая задача, над которой бились много лет

Во время ужина на игровом фестивале в 2012 году разработчик настольных игр спросил Эрика Харшбаргера, нельзя ли придумать такие кости, которые позволяли бы определять первого игрока без вероятности ничьей. Идея была простой: быстро определить, кто ходит первым, и перейти к игре.

«Цель в том, чтобы сэкономить всем несколько драгоценных секунд и как можно скорее начать играть», — рассказал Харшбаргер ведущей программы As It Happens Нил Кёксал. Харшбаргер, математик и старший преподаватель Обернского университета в Оберне, штат Алабама, говорит, что такая задача пришлась ему как раз по душе. «Это был вопрос без очевидного ответа, а математики обычно очень любят за такие вопросы хвататься».

Харшбаргер вообразил себе такой теоретический набор костей, в котором каждый игрок мог бы бросить по одной кости, все имели бы одинаковые шансы на победу и при этом никакие два игрока не могли бы получить одинаковый результат. Но найти кости, которые действительно работали бы в реальном мире, оказалось гораздо сложнее.

Теперь, почти 15 лет спустя, Харшбаргер и его коллеги наконец создали такой набор: Go First Dice для пяти игроков. Они позволяют честно определить, кто первым ходит в настольной игре, причём победитель гарантирован уже после одного броска.

Упрямая задача

За эти годы Харшбаргер фактически стал хранителем этой задачи. Он вёл сайт, где фиксировал новые результаты, а к проекту в разное время присоединялись и уходили из него около 20 специалистов по информатике и математиков со всего мира.

Довольно быстро Харшбаргер и его команда нашли решение с набором из четырёх 12-гранных костей. Два, три или четыре игрока могли бросить по одному додекаэдру и получить статистически честный результат, причём каждый раз обязательно находился победитель. «Для двух человек мы решили задачу в мгновение ока, для трёх — за день‑два, а кости для четырёх человек придумывали две‑три недели, ну, может быть, месяц», — рассказал Харшбаргер. Но вариант для пяти игроков оказался гораздо более крепким орешком.

По словам Харшбаргера, он и его коллеги всегда знали, что с математической точки зрения такие кости существуют. Оставалось понять, можно ли воплотить математическое решение в физической форме игральной кости, то есть сделать предмет, который реально можно изготовить и бросать. «Я знал, что существует безумное решение вроде 1440 граней у каждой кости, — сказал он. — Но такое невозможно изготовить».

Поэтому исследователи начали разрабатывать разные теории и пытаться уменьшить число граней, постепенно «обтёсывая» задачу. В процессе к группе присоединился исследователь из Австралии и нашёл более практичное решение: набор из пяти 120-гранных костей. Открытие привлекло внимание прессы, и примерно через полгода к работе присоединился ещё один исследователь, на этот раз из Канады.

Прорыв из Канады

Канадский инженер‑программист Пол Мейер связался с Харшбаргером и попросил прислать некоторые старые результаты работ. Через три месяца Мейер отправил Харшбаргеру письмо с отличной новостью: он нашёл решение с пятью 60-гранными костями. За время работы над проектом Харшбаргер получал множество писем от людей, утверждавших, что решили задачу, поэтому первым делом он всегда проверял предложенное решение. На этот раз всё действительно работало. Харшбаргер написал Мейеру: «Вы понимаете, что мы искали это очень давно?»

Мейер подошёл к задаче как к вычислительной проблеме: использовал математические закономерности из предыдущих решений и компьютерный перебор. Пространство поиска было колоссальным: возможных конструкций существовало больше, чем атомов во Вселенной. Но Мейеру удалось достаточно сильно сузить его и найти решение.

Кости размером примерно с мяч для гольфа уже можно купить, хотя некоторые исследователи сомневаются, смогут ли они на практике полностью соответствовать математической модели. Харшбаргер, однако, уверен в математике. Кости спроектированы так, чтобы быть абсолютно честными, а любые отклонения, способные повлиять на результат, могут возникнуть только из‑за особенностей изготовления, а не из‑за самой математической конструкции.

В итоге у каждого игрока своя 60-гранная кость, причём числа на пяти костях не повторяются, поэтому ничья невозможна. Эти числа специально распределены между костями так, чтобы ни одна из них не имела преимущества: при броске любых двух каждая выигрывает с вероятностью 50%, а при игре втроём, вчетвером или впятером все возможные порядки результатов остаются равновероятными. Иными словами, кости разные, но математически «честные» относительно друг друга. Кроме того, любое количество человек, от двух до четырёх, могут взять по одной случайной кости из набора, и они будут работать точно так же, обеспечивая равные шансы и не приводя к ничьей / прим. перев.

Следующие нерешённые вопросы

После этого Мейер вошёл в исследовательскую группу, и работа в ней продолжается. По словам Харшбаргера, они по‑прежнему пытаются понять, можно ли сделать набор для пяти игроков с меньшим числом граней. Известно, что теоретический минимум составляет 30 граней. Кроме того, исследователи хотят выяснить, можно ли распространить эту идею на шесть игроков.

Нынешних математических и вычислительных методов для решения этих задач пока недостаточно, говорит Харшбаргер, но за эти годы команда научилась ждать неожиданностей. «Конечно, вполне может появиться кто‑то ещё с совершенно новой теорией и сказать: „А я сделал вот так“, — говорит Харшбаргер. — По сути, именно это и произошло с Полом. Он возник буквально из ниоткуда».

Для Харшбаргера именно эта непредсказуемость и сделала задачу настолько увлекательной. «С математической точки зрения она казалась очень красивой и интригующей, хотя мы с первого дня понимали, что сам вопрос довольно дурацкий. Но на него не было очевидного ответа, а за такие вопросы математик часто хватается и потом упрямо занимается ими годами».