Математики бросают кости и получают камень-ножницы-бумага

Как рассказывает Билл Гейтс, Уоррен Баффет однажды вызвал его на игру в кости. Каждый выбирал один из четырех кубиков, принадлежащих Баффету, а затем бросал кубики, и выигрывал тот, у кого больше число. Это были не стандартные игральные кости — набор чисел в них отличался от обычных от 1 до 6. Баффет предложил предоставить Гейтсу право выбора первым, чтобы он мог выбрать самый сильный кубик. Но после того, как Гейтс изучил кости, он сделал встречное предложение: Баффет должен выбирать первым.

Гейтс понял, что у игральных костей Баффета есть любопытное свойство: среди них нет сильнейших. Если бы Гейтс выбрал первым, то какую бы кость он ни выбрал, Баффет смог бы найти другую кость, которая могла бы победить ее (то есть с вероятностью выигрыша более 50%).

Четыре кости Баффета (назовем их A, B, C и D) образовали узор, напоминающий камень-ножницы-бумагу, в котором A ударов B, B ударов C, C ударов D и D ударов A. Математики говорят, что такой набор игральных костей «интранзитивен».

«Совершенно не интуитивно понятно, что [непереходные кости] вообще должны существовать», — сказал Брайан Конри, директор Американского института математики (AIM) в Сан-Хосе, написавший влиятельную статью на эту тему в 2013 году.

Математики придумали первые примеры непереходных игральных костей более 50 лет назад, и в конечном итоге доказанный что по мере того, как вы рассматриваете игральные кости со все большим и большим количеством сторон, можно создавать непереходные циклы любой длины. Чего математики не знали до недавнего времени, так это того, насколько распространены нетранзитивные игральные кости. Нужно ли вам тщательно придумывать такие примеры, или вы можете выбрать кости случайным образом и попытаться найти нетранзитивное множество?

Глядя на три кости, если вы знаете, что A ударов B и B ударов C, это похоже на доказательство того, что A является самым сильным; ситуации, когда C ударов A должно быть редко. И действительно, если допустить, что числа на костях складываются в разные суммы, то математики верят, что эта интуиция верна.

Но статья размещена в Интернете конец прошлого года показывает, что в другом естественном окружении эта интуиция терпит неудачу. Предположим, вы хотите, чтобы ваши кости использовали только те числа, которые появляются на обычном кубике, и имели ту же сумму, что и обычный кубик. Затем газета показала, если A ударов B и B ударов C, A и C имеют практически равные шансы победить друг друга.

"Знаю это A ударов B и B ударов C просто не дает вам никакой информации о том, A ударов C," сказал Тимоти Гауэрс из Кембриджского университета, медалист Филдса и один из участников нового результата, который был подтвержден с помощью открытого онлайн-сотрудничества, известного как проект Polymath.

Между тем еще один Недавняя статья анализирует наборы из четырех и более игральных костей. Этот вывод, возможно, еще более парадоксален: если, например, вы выберете четыре кости наугад и обнаружите, что A ударов B, B ударов C и C ударов D, то немного БОЛЕЕ вероятно для D бить A чем наоборот.

Ни сильный, ни слабый

Недавний поток результатов начался около десяти лет назад, после того как Конри посетил собрание учителей математики, посвященное непереходным игральным костям. «Я понятия не имел, что такие вещи могут существовать», — сказал он. «Я был очарован ими».

Он решил (позже к нему присоединился его коллега Кент Моррисон в AIM), чтобы изучить этот предмет с тремя старшеклассниками, которых он наставлял, — Джеймсом Габбардом, Кэти Грант и Эндрю Лю. Группа задалась вопросом, как часто случайно выбранные кости образуют непереходный цикл?

Считается, что непереходные наборы игральных костей встречаются редко, если сумма чисел на гранях игральных костей дает разные суммы, поскольку кость с наибольшим значением, скорее всего, побьет другие. Поэтому команда решила сосредоточиться на кубиках, обладающих двумя свойствами: во-первых, на кубиках используются те же числа, что и на стандартном кубике — от 1 до n, в случае nдвусторонний штамп. И, во-вторых, количество граней в сумме дает ту же сумму, что и на стандартном кубике. Но в отличие от стандартных игральных костей, каждая кость может повторять одни числа и опускать другие.

В случае с шестигранными игральными костями есть только 32 различных игральных кости, обладающих этими двумя свойствами. Таким образом, с помощью компьютера команда могла определить все тройки, в которых A ударов B и B ударов C. Исследователи, к своему удивлению, обнаружили, что A ударов C в 1,756 тройках и C ударов A в 1,731 тройке — почти одинаковые числа. Основываясь на этом вычислении и моделировании игры в кости с более чем шестью сторонами, команда предположила что по мере того, как число сторон игральной кости приближается к бесконечности, вероятность того, что A ударов C приближается к 50%.

Эта гипотеза с ее сочетанием доступности и нюансов показалась Конри хорошей основой для проекта Polymath, в рамках которого многие математики собираются в Интернете для обмена идеями. В середине 2017 года он предложил эту идею Гауэрсу, создателю подхода Polymath. «Мне очень понравился вопрос из-за его неожиданности», — сказал Гауэрс. Он написал блоге о догадке, вызвавшей шквал комментариев, и в течение шести дополнительных постов комментаторам удалось ее доказать.

В своей работе, размещены в Интернете в конце ноября 2022 года ключевая часть доказательства включает в себя демонстрацию того, что по большей части нет смысла говорить о том, является ли отдельная кость сильной или слабой. Кости Баффета, ни один из которых не является самым сильным из набора, не так уж необычны: если вы выберете кубик наугад, как показал проект Polymath, он, вероятно, побьет примерно половину других костей и проиграет другой половине. «Почти каждый кубик довольно средний», — сказал Гауэрс.

Проект отличался от первоначальной модели команды AIM в одном отношении: чтобы упростить некоторые технические детали, в проекте было объявлено, что порядок чисел на игральной кости имеет значение, поэтому, например, 122556 152562 и XNUMX XNUMX будут считаться двумя разными игральными костями. Но результат Polymath в сочетании с экспериментальными данными группы AIM создает сильное предположение, что гипотеза также верна в исходной модели, сказал Гауэрс.

«Я был очень рад, что они нашли это доказательство, — сказал Конри.

Когда дело дошло до набора из четырех или более игральных костей, команда AIM предсказала такое же поведение, как и для трех игральных костей: например, если A ударов B, B ударов C и C ударов D тогда должна быть примерно 50-50 вероятность того, что D ударов A, приближаясь ровно к 50-50 по мере того, как число граней игральной кости приближается к бесконечности.

Чтобы проверить гипотезу, исследователи смоделировали турниры один на один для наборов из четырех игральных костей с 50, 100, 150 и 200 гранями. Моделирование не так точно соответствовало их предсказаниям, как в случае с тремя игральными костями, но все же было достаточно близко, чтобы укрепить их веру в гипотезу. Но хотя исследователи этого не осознавали, эти небольшие несоответствия несли другой смысл: для наборов из четырех и более игральных костей их гипотеза неверна.

«Мы действительно хотели, чтобы [гипотеза] была правдой, потому что это было бы круто», — сказал Конри.

В случае четырех игральных костей Элизабетта Корначчиа Швейцарского федерального технологического института Лозанны и Ян Хазла Африканского института математических наук в Кигали, Руанда, показал в бумаги размещено в Интернете в конце 2020 года, что если A ударов B, B ударов C и C ударов D, то D имеет шанс победить чуть выше 50% A — вероятно, где-то около 52%, — сказал Хазла. (Как и в случае с документом Polymath, Корнаккиа и Хазла использовали несколько иную модель, чем в документе AIM.)

Открытие Корнаккии и Хазлы вытекает из того факта, что, хотя, как правило, одна кость не будет ни сильной, ни слабой, пара костей иногда может иметь общие области силы. Если вы выберете две кости наугад, как показали Корнаккиа и Хазла, существует приличная вероятность того, что кости будут коррелированы: они будут иметь тенденцию побеждать или проигрывать одним и тем же костям. «Если я попрошу вас создать две кости, расположенные близко друг к другу, окажется, что это возможно», — сказал Хазла. Эти небольшие очаги корреляции отклоняют результаты турнира от симметрии, как только на картинке появляется как минимум четыре кубика.

Последние публикации — это не конец истории. Статья Корнаккиа и Хазлы только начинает раскрывать, как именно корреляции между игральными костями нарушают симметрию турниров. Тем временем, однако, теперь мы знаем, что существует множество наборов непереходных игральных костей — может быть, даже один, достаточно тонкий, чтобы обмануть Билла Гейтса, чтобы он сделал выбор первым.