Дубли на кубиках

[Dendr]

Задача 12538 из The American Mathematical Monthly от 23 июня 2025 года (в моем переводе)

Даны 5 шестигранных игральных кубиков. После каждого броска вы можете отложить любое количество кубиков, возможно все, в сторону - тем самым исключая их из последующих бросков - а потом бросить остальные повторно. Требуется получить такую комбинацию чисел на верхних гранях, чтобы среди них не было ни одного, которое встречается ровно один раз. Другими словами, чтобы любое показание было задублировано. то есть либо 5 одинаковых, либо 3 одного вида и 2 второго.

При какой стратегии матожидание количества бросков наименьшее? (под единичным броском понимается бросок всей "кучки" кубиков)

[worm2]

Dendr в сообщении #1707920 писал(а):

тем самым исключая их из последующих бросков

То есть если я однажды отложил кубики, я навсегда лишаюсь права когда-нибудь в будущем их бросать?

[Yadryara]

Dendr, приведите пожалуйста численные примеры.

Сейчас в тему придёт сами знаете кто, с программой на PARI

[wrest]

Наивно кажется так, что после броска надо откладывать кубики с 2 или более одинаковыми значениями.

[worm2]

wrest, да, мне тоже так кажется. Но я пока что ниасилил посчитать матожидание даже для одной этой стратегии.

Давайте для начала посмотрим, какие конфигурации у нас могут быть после первого броска. Считаем за аксиому, что первым броском мы должны бросать все кубики.
Всего возможны $6^5=7776$ вариантов, которые разбиваются на 7 возможных классов (подсчитано с помощью компьютерной программы, ибо плохо умею по-другому):
1) Все числа разные (ABCDE) — 720 исходов
2) Три числа разные, два одинаковые (AABCD) — 3600 исходов
3) Два числа разные, три одинаковые (AAABC) — 1200 исходов
4) Одно число, два одинаковых, и ещё два одинаковых (AABBC) — 1800 исходов
5) Два одинаковых и ещё три одинаковых (AAABB) — 300 исходов
6) Одно число и четыре одинаковых (AAAAB) — 150 исходов
7) Все числа одинаковые (AAAAA) — 6 исходов
Немедленный успех (один бросок) — это классы 5) и 7), матожидание 1.
Для класса 6) до посинения бросаем кубик B, пока на нём не выпадет A — матожидание 6, плюс первый бросок, итого 7.
Уф, ещё не начал решать, а уже устал.

-- Сб ноя 01, 2025 13:38:40 --

Для класса 4) бросаем кубик C, пока на нём не выпадет A или B — матожидание 3, плюс первый бросок, итого 4.

[12d3]

Тут лучше считать с конца, сначала с 4 отложенными кубиками, потом с 3, потом с 2, потом уже из начальной позиции (откладывать 1 кубик смысла нет).
Пока что выяснились следующие матожидания в зависимости от уже отложенных кубиков:
AAAA - 6
AAAB - 6
AABB - 3
AAA - 6
AAB - $\frac{60}{11} \approx 5.45$ (откладываем B если попадется)
AA - $\frac{44}{9} \approx 4.88$ (откладываем BB)
AB - $\frac{69}{11} \approx 6.27$ (откладываем AB если получится, иначе откладываем только A или только B)

UPD. Посчитано для двух отложенных кубиков. Кажется, выгоднее всего ловить комбинацию AABB либо откладывать пару одинаковых.

[EUgeneUS]

ИМХО,
1. Откладывать одинарные кубики нет смысла. Это не улучшает ситуацию (но это не точно). Поэтому при ABCDE ничего не откладываем и перебрасываем.
2. Если выпало: AAABC, AAAAB, AABBC, то нужно откладывать тройку (тройка или четверка - всё равно), или две пары. После чего матожидание выигрыша: для тройки\четверки - $1/6$, и для двух пар: $1/3$
3. И тогда основной вопрос философии: нужно ли откладывать пару при выпадении AABCD? Или лучше перебросить все кубики и ждать комбинации из пункта 2?

[12d3]

С использованием результатов первого броска, посчитанными уважаемым worm2, получилось матожидание $\frac{2336}{441} \approx 5.3$. Стратегия такова - в отложенных кубиках должно быть либо две различных пары, либо одна пара, первый вариант приоритетнее. Больше никаких комбинаций не откладываем.

[EUgeneUS]

12d3
А если выпало AAABC, то откладываем пару или тройку?

[12d3]

EUgeneUS
Пару. Тогда в среднем меньше 5 бросков понадобится, а для тройки ровно 6.

[EUgeneUS]

12d3 в сообщении #1707954 писал(а):

Пару. Тогда в среднем меньше 5 бросков понадобится, а для тройки ровно 6.

Контринтуитивно.
Хорошая задача.

[wrest]

Ну в общем у chatgpt получилось матожидание 5.23469387755102
И отличий от "наивной" стратегии "держи как минимум пару, остальное сбрось" довольно много.
Все отличия пояснены, и это весьма длинный текст.
Например, если первым ходом выпало 4,1 то отложить надо не 4 и бросать 1, а отложить (держать) надо пару плюс одиночку, а бросать вторую пару.

Почему:

Если держать 4, вы оставляете только 1 кубик для броска — шанс получить пятёрку = 1/6; если не получилось, вы снова в похожей ситуации и потребуется ещё много бросков.
Если вместо этого держать пару+одиночку и бросать 2 кубика, вы увеличиваете шансы получить требуемую структуру 3+2 в один бросок (или быстро в два), потому что 2 переброшенных кубика могут сформировать пару, дополнить тройку и т.д. В среднем это уменьшает количество требуемых бросков до достижения 3+2 / 5+0.

-- 01.11.2025, 15:49 --

EUgeneUS в сообщении #1707950 писал(а):

3. И тогда основной вопрос философии: нужно ли откладывать пару при выпадении AABCD? Или лучше перебросить все кубики и ждать комбинации из пункта 2?

Спрашивали - отвечаем.
Надо откладывать пару + одну из одиночек (итого пара+одиночка), бросать 2 кубика.

Почему:

Пара + одиночка + бросок 2 кубиков даёт хорошие шансы собрать 3+2 быстрее, чем откладывать только пару и бросать 3 кубика.

Ну поскольку это советы ИИ, хотя и основанные на расчёте (есть код на питоне), то относиться с осторожнотью

[wrest]

В общем, после первого броска получаются такая стратегия (последующие ходы очевидны)
AAAAA - игра окончена
AAAAB - откладываем AAB, перебрасываем AA
AAABB - игра окончена
AAABC - откладываем AAB, перебрасыаем AC
AABBC - откладываем AABB, перебрасываем C
AABCD - откладываем AA, перебрасываем BCD
ABCDE - перебрасываем целиком

Контринтуитивно тут конечно варианты AAAAB и AAABC где вместо того, чтобы отложить четверку или тройку, мы откладываем пару плюс одиночку, при том что в варианте AABCD откладываем только пару.

[EUgeneUS]

wrest в сообщении #1707966 писал(а):

Пара + одиночка + бросок 2 кубиков даёт хорошие шансы собрать 3+2 быстрее, чем откладывать только пару и бросать 3 кубика.

Сильно сомнительно, что нужно откладывать одиночку.

[wrest]

Первый бросок + исходы второго
МО - матожидание до победы после первого броска.
Ост. - сколько кубиков перебросить
$\[ \begin{array}{|l|l|c|c|l|} \hline \textbf{Состояние} & \textbf{Отложить} & \textbf{Ост.} & \textbf{МО} & \textbf{Осн. исходы после 2 броска} \\ \hline A A A A A & AAAAA & 0 & 0 & - \\ \hline A A A A B & A A + B & 2 & 1,52 & \begin{array}{l} AABBC:\,1/3,~~AABCD:\,1/3,\\ AAABC:\,2/9,~~AAABB:\,1/12,~~AAAAB:\,1/36жжжжж \end{array} \\ \hline A A A B B & AAABB & 0 & 0 & - \\ \hline A A A B C & A A + B & 2 & 2,07 & \begin{array}{l} AABBC:\,1/3,~~AABCD:\,1/3,\\ AAABC:\,2/9,~~AAABB:\,1/12,~~AAAAB:\,1/36 \end{array} \\ \hline A A B B C & A A + B B & 1 & 2,73 & \begin{array}{l} AAABB:\,1/3,~~AABBC:\,2/3 \end{array} \\ \hline A A B C D & A A & 3 & 3,98 & \begin{array}{l} AAABC:\,5/18,~~AABBC:\,5/18,\\ AABCD:\,5/18,~~AAABB:\,5/54,\\ AAAAB:\,5/72,~~AAAAA:\,1/216 \end{array} \\ \hline A B C D E & - & 5 & 5,23 & \begin{array}{l} AABCD:\,25/54,~~AABBC:\,25/108,\\ AAABC:\,25/162,~~ABCDE:\,5/54,\\ AAABB:\,25/648,~~AAAAB:\,25/1296,\\ AAAAA:\,1/1296 \end{array} \\ \hline \end{array} \] $

-- 01.11.2025, 19:12 --

EUgeneUS в сообщении #1707984 писал(а):

Сильно сомнительно, что нужно откладывать одиночку.

Ну вот расчёт ИИ показывает, что нужно
Выигрыш против "наивной" стратегии (когда откладываем тройку/четверку) где-то 0,54
5,78 "наивная"; 5,23 оптимальная.

-- 01.11.2025, 19:17 --

В общем, получился довольно хитрый покер.