Нетранзитивные кубики

В этой задаче очень полезно научиться определять, какой из двух данных кубиков сильнее. Есть довольно простой и наглядный способ это делать.

Сразу отметим, что эта задача имеет много решений. На рис. 1 приведено одно из них: показаны развертки всех шести кубиков с написанными на них числами. На каждом кубике порядок расположения чисел значения не имеет. Как убедиться, что выполняется требуемое соотношение: К > О > Ж > З > Г > С > K?

Рис. 1.

Рассмотрим два первых кубика — красный и оранжевый. У каждого кубика шесть граней, на которых записаны по шесть различных чисел, поэтому при бросках этих кубиков возможно появление 36 различных пар. Выписывать их нет смысла, но можно изобразить графически в виде таблицы, как показано на рис. 2.

Рис. 2.

Каждая клетка этого квадрата 6×6 соответствует одной из возможных пар чисел. Например, клетка, отмеченная точкой, соответствует паре (25, 20): на красном кубике выпало число 25, на оранжевом кубике — число 20. Закрашена эта клетка красным, потому что в этом случае красный кубик сильнее оранжевого. По этому же принципу закрашены остальные клетки. Хорошо видно, что красный кубик чаще побеждает оранжевый. Более того, можно утверждать, что красный кубик выигрывает в 2 раза чаще, потому что красных клеток получилось 24, а оранжевых — всего 12.

Если нарисовать аналогичные таблички для всех шести пар соседних кубиков, то можно обнаружить, что нетранзитивное неравенство выполняется, см. рис. 3. Также можно заметить, что при такой расстановке чисел каждый кубик выигрывает у следующего за ним с вероятностью \(p=\frac{24}{36}=\frac23\).

Рис. 3.

Задача решена, но остаются вопросы. Как найти такую расстановку чисел? Есть ли другие? На них мы ответим в послесловии.

В теории вероятностей много парадоксов, которые, на первый взгляд, противоречат логике. В этой задаче мы рассмотрели вариацию на тему одного из таких парадоксальных случаев. Первый пример нетранзитивных кубиков привел американский математик Брэдли Эфрон (Bradley Efron). Миру о них поведал Мартин Гарднер в своей колонке в журнале Scientific American и в замечательной книге «Крестики-нолики». В этом наборе четыре кубика A, B, C и D, на гранях которых расставлены числа, и выполняется соотношение A > B > C > D > A.

Есть несколько реализаций кубиков Эфрона. Во одна из них: на кубике A расставлены числа 1, 2, 3, 9, 10, 11, на кубике B — числа 0, 1, 7, 8, 8, 9, на кубике C — числа 5, 5, 6, 6, 7, 7, а на кубике D — числа 3, 4, 4, 5, 11, 12.

Рассмотрим игру для двоих: первый игрок берет один из кубиков набора и бросает его, второй берет один из оставшихся трех кубиков и тоже бросает его. Тот, у кого выпало больше очков, победил. Ясно, что ни один из игроков не может обеспечить себе победу при каждом броске, но увеличить свои шансы на победу один из них может. Кто? Давайте разберемся в этом вопросе с помощью таблиц (рис. 4).

Рис. 4.

В этих таблицах, как и в решении, закрашены клетки, которым соответствует случай выпадения большего числа на кубике, соответствующем вертикальному ряду чисел. Считая закрашенные клетки в таблицах, нетрудно проверить, что кубик A сильнее кубика B, кубик B сильнее кубика C, а кубик C сильнее кубика D — во всех трех случаях более сильный кубик побеждает в 22 из 36 возможных исходах броска. Но легко видеть, что самый «слабый» кубик D оказывается сильнее кубика A, и вероятность его победы тоже равна 11/18. Кажущегося парадокса здесь, как и в наборе кубиков из нашей задачи, нет, поскольку сравнение вероятностей не обладает свойством транзитивности.

Получается, что кубики можно ранжировать по замкнутому циклу A > B > C > D > A, а значит, у второго игрока больше шансов на победу, потому что, какой бы кубик ни выбрал первый игрок, найдет кубик сильнее, — его и возьмет второй.

Эфрон придумал нетранзитивные кубики уже больше 50 лет назад. С тех, как уже говорилось, было придумано много разных вариаций на эту тему. Например, Вадим Кряквин предложил набор из четырех кубиков (как и у Эфрона), в котором используются числа от 1 до 24 по одному разу (рис. 5).

Рис. 5.

Причем этот набор получается из кубиков Эфрона в результате очень простой операции: нужно выписать все 24 числа с кубиков Эфрона в порядке неубывания и пронумеровать их числами от 1 до 24. После чего остается каждое число на кубиках Эфрона заменить его номером и получить кубики Кряквина. Интересно, что в результате меняется вероятность победы «сильного» кубика в каждой паре: теперь она равна 2/3.

Наша задача, собственно, получилась как естественное развитие идеи В. Кряквина: хотелось получить нетранзитивные наборы с большим числом кубиков, на гранях которых были бы записаны начальные числа натурального ряда по одному разу. Я придумал набор из пяти кубиков, в котором каждый следующий кубик сильнее предыдущего по циклу (рис. 6). Каждый кубик этого набора тоже в два раза чаще выигрывает у следующего.

Рис. 6.

Задача с пятью кубиками была предложена на «задачном» сайте diofant.ru. Читатели нашли много решений этой задачи, но самое главное — предложены новые методы поиска наборов нетранзитивных кубиков и были придуманы построения для задачи общего вида, в которой ищется набор из n кубиков \(A_i\) \((i=1,\ldots,n)\), таких что \(A_1>A_2>\ldots>A_n>A_1\). Далее нам будет удобно представлять набор кубиков в виде списка (или, если угодно, таблицы) из строк, в котором каждая строка — это числа с граней очередного кубика, записанные в порядке возрастания.

Александр Домашенко придумал простой и понятный способ построения набора, содержащего n нетранзитивных кубиков. Этот метод работает для \(n\ge4\).

Начнем заполнять наш список с чисел от 1 до 9 (ниже они отмечены красным). Остальные числа от 10 до 6n разбиваются на шестерки — по порядку, начиная с числа 10, и эти шестерки построчно заносятся в список снизу вверх (с последней строки). Запись шестерок продолжается до тех пор, пока не будет заполнена четвертая строка списка. В этот момент не использованными останутся 9 чисел от \(6n-8\) до \(6n\). Их допишем в первые три строки — также двигаясь снизу вверх. Получится такой список:

\(A_1\): 6, 7, 8, 9, \(6n-1\), \(6n\)
\(A_2\): 3, 4, 5, \(6n-4\), \(6n-3\), \(6n-2\)
\(A_3\): 1, 2, \(6n-8\), \(6n-7\), \(6n-6\), \(6n-5\)
\(A_4\): \(10+6(n-4)\), \(11+6(n-4)\), \(12+6(n-4)\), \(13+6(n-4)\),        \(14+6(n-4)\), \(15+6(n-4)\)
\(A_5\): \(10+6(n-5)\), \(11+6(n-5)\), \(12+6(n-5)\), \(13+6(n-5)\),        \(14+6(n-5)\), \(15+6(n-5)\)
...
\(A_{n-1}\): 16, 17, 18, 19, 20, 21
\(A_n\): 10, 11, 12, 13, 14, 15

В том, что набор кубиков получился нетранзитивным, легко убедиться. В самом деле, сравнивая кубики \(A_1\) и \(A_2\), заметим, что каждое из чисел 6, 7, 8 и 9 кубика \(A_1\) больше чисел 3, 4 и 5 кубика \(A_2\), а числа \(6n-1\) и \(6n\) кубика \(A_1\) больше любого числа кубика \(A_2\), поэтому кубик \(A_1\) сильнее кубика \(A_2\) в \(4\cdot3+2\cdot6=24\) случаях из 36 возможных, поэтому вероятность выигрыша равна \(P(A_1>A_2)=\frac{24}{36}=\frac23\). Аналогично проверяется, что \(P(A_2>A_3)=P(A_3>A_4)=P(A_n>A_1)=\frac23\). В остальных же \(n-4\) парах кубиков по циклу каждое из шести чисел верхнего кубика больше любого числа нижнего, поэтому вероятности равны по 1.

Михаил Ватник придумал другой метод построения наборов нетранзитивных кубиков, который можно назвать рекуррентным: имея нетранзитивный набор из n кубиков, он позволяет получить нетранзитивный набору из n+1 кубика.

Этот алгоритм состоит из трех шагов:
    1) Удвоить все числа на всех гранях всех кубиков.
    2) Добавить еще один кубик, в котором каждое число на 1 больше, соответствующего числа первого кубика (если на первом кубике после удвоения записаны числа \(2a\), \(2b\), \(2c\), \(2d\), \(2e\), \(2f\), то добавляется кубик с числами \(2a+1\), \(2b+1\), \(2c+1\), \(2d+1\), \(2e+1\), \(2f+1\). Порядок кубиков, естественно, нельзя менять!
    3) Перенумеровать все числа на всех кубиках в возрастающем порядке (то есть проделать то, что сделал Кряквин с кубиками Эфрона).

Нетрудно убедиться, что построенный набор кубиков обладает свойством нетранзитивности. При этом во всех парах, кроме последней, каждый кубик сильнее своего визави с такой же вероятностью, какую имели пары кубиков в наборе с \(n\) кубиками. Для последней пары: \(P(A_{n+1}>A_1)=\frac{1+2+3+4+5+6}{36}=\frac{7}{12}>\frac{1}{2}\). Значит, построенный набор из \(n+1\) кубика тоже является нетранзитивным.

Продемонстрируем этот прием, построив набор из семи кубиков на основе набора из шести кубиков, который мы рассматривали в решении.

Исходный набор из шести кубиков:

\(A_1\): 3, 4, 24, 25, 26, 27
\(A_2\): 5, 6, 20, 21, 22, 23
\(A_3\): 14, 15, 16, 17, 18, 19
\(A_4\): 10, 11, 12, 13, 35, 36
\(A_5\): 7, 8, 9, 32, 33, 34
\(A_6\): 1, 2, 28, 29, 30, 31

Удвоим числа:

\(A_1\): 6, 8, 48, 50, 52, 54
\(A_2\): 10, 12, 40, 42, 44, 46
\(A_3\): 28, 30, 32, 34, 36, 38
\(A_4\): 20, 22, 24, 26, 70, 72
\(A_5\): 14, 16, 18, 64, 66, 68
\(A_6\): 2, 4, 56, 58, 60, 62

Добавим седьмую строку:

\(A_1\): 6, 8, 48, 50, 52, 54
\(A_2\): 10, 12, 40, 42, 44, 46
\(A_3\): 28, 30, 32, 34, 36, 38
\(A_4\): 20, 22, 24, 26, 70, 72
\(A_5\): 14, 16, 18, 64, 66, 68
\(A_6\): 2, 4, 56, 58, 60, 62
\(A_7\): 7, 9, 49, 51, 53, 55

Осталось перенумеровать все числа:

\(A_1\): 3, 5, 26, 28, 30, 32
\(A_2\): 7, 8, 22, 23, 24, 25
\(A_3\): 16, 17, 18, 19, 20, 21
\(A_4\): 12, 13, 14, 15, 41, 42
\(A_5\): 9, 10, 11, 38, 39, 40
\(A_6\): 1, 2, 34, 35, 36, 37
\(A_7\): 4, 6, 27, 29, 31, 33

Развертки кубиков полученного набора приведены на рис. 7.

Рис. 7.