Добрый день.
Сегодня я хочу напомнить одну старинную задачу о честном дележе клада, а потом предложу игру, чем-то похожую по постановке, но очень отличающуюcя по сути.
Если два пирата нашли клад, но не считают правильным расправляться друг с другом, чтобы единолично им завладеть, то есть один хороший выход - честно его поделить. Осталось придумать, как бы так распределить добычу, чтобы оба были довольны. Уже не один век известен следующий алгоритм:
1. Один участник делит весь клад на две части, после чего отходит в сторонку.
2. Второй, внимательно изучив две кучи всевозможных ценностей, выбирает себе одну из них.
3. Соответственно, первому остаётся то, что второй не забрал.
Тогда у обоих пиратов прослеживаются простые и ясные цели: первый хочет разделить весь клад на равные по ценности группы, а второй имеет возможность выбрать из них более ценную, если первый попытается схитрить.
Существует естественное расширение этой задачи на группу из более чем двух пиратов, но сейчас мы не будем разбираться с этой интересной проблемой, а перейдём к игре, в которой игроки тоже поочереди подходят к игровому столу, имея возможность чуть-чуть менять снаряды и выбирать их себе для следующего хода.
Но сначала вспомним, что в прошлом году мы уже изучали вопрос «какой шахматист лучше?». Если у нас есть несколько признаков, то не так легко разобраться, какой из них важнее, поэтому задача не такая простая (и порождает массу споров). Проблема стояла серьёзная, поэтому я опубликовал вариант решения. Но суть коротко напомню здесь: тонкость была в том, что до игры в правилах не было чётко сформулировано, что значит «один шахматист лучше другого». А если нет правил, то можно выдумывать сколь угодно красивые аргументы. Поэтому и могли возникать горячие споры, в которых невозможно победить.
Теперь, имея этот опыт, мы будем определять правила предельно ясно ;)
Итак, есть 3 шестигранных игральных кости с чистыми гранями и один маркер. Двое игроков действуют следующим образом:
1. Первый рисует на гранях костей числа от 1 до 18 (без повторов, поэтому использует все 18 чисел на всех 18-ти гранях).
2. Второй выбирает себе одну из трёх игральных костей.
3. Первый выбирает одну из двух оставшихся.
4. После этого игроки бросают свои кости - выигрывает тот, на чьём кубике выпадет большее число.
Вопрос: кто будет чаще выигрывать при правильных действиях обоих игроков? Решая задачу, надо исходить из того, что игра честная, а оба участника хотят выигрывать как можно чаще.
Приглашаю обсудить эту задачку в комментариях. Хороших вам выходных!
15 нояб. 2009 г.
Клад и кости
Темы:
математика
Подписаться на:
Комментарии к сообщению (Atom)
Понравилась заметка? Подпишитесь на
RSS-feed или email-рассылку.
Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
RSS-feed или email-рассылку.Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
По идее, рисующий циферки может выиграть, если нарисует их так, чтобы кубики получились как камень-ножницы-бумага, то есть любой из них в среднем был лучше одного и хуже второго из оставшихся.
ОтветитьУдалитьТогда какой бы кубик не взял второй игрок, первый всегда может взять тот, который лучше.
А вот возможно ли такое расположение чисел, и как это сделать - пока не придумал :)
Второй очевидно будет побеждать чаще, так как сможет выбрать самую сильную кость, в независимости от того как на них цифры рисовали :-)
ОтветитьУдалитьПри правильных действиях, первый никогда не сможет выигрывать чаще, если такое случится - значит второй сделал неправильный выбор. Но к ничьей свести можно. Например, так:
ОтветитьУдалитьНа одном кубике нарисовать 18,17,16 и 1,2,3, на втором 15,14,13,12,11,10, на третьем 9,8,7,6,5,4. Я нарисовал, выбирайте. Выбор той или иной стороной первого кубика фиксирует ничью.
Мне пока пришло в голову только расписывать кубики «змейкой». То есть:
ОтветитьУдалить1 кубик — 1; 6; 7; 12; 13; 18;
2 кубик — 2; 5; 8; 11; 14; 17;
3 кубик — 3; 4; 9; 10; 15; 16;
Тогда получится, что на каждом кубике одинаковое количество чисел, которые будут меньше или больше тех, что остались на других кубиках. Потому, интуитивно шансы уравниваются. А так это, или нет — пока доказать не могу =).
А если вернуться к вопросу о том, кто будет чаще выигрывать, то мне интуитивно кажется, что тот, кто будет выбирать кубик вторым. Птому что он будет выбирать из 2-х кубиков, а не из 3-х. А потому шанс выбрать выиграшный кубик у него больше.
Paskal_07, что значит «кубики идентичны»? Если на моём кубике числа 13,14,15,16,17,18, а на Вашем - 1,2,3,4,5,6, то мой кубик всегда будет побеждать Ваш, так как на нём будет выпадать большее число. Ни о каком 50/50 речь идти не может в таком случае.
ОтветитьУдалитьJekyll, ну да, как свести к ничьей Вы придумали. Но как доказать, что ни один из игроков не сможет сыграть лучше?
r-i-zhaya, предложенный Вами способ разместить числа на кубиках приводит к ничьей, так как нет совершенно никакой разницы, какой кубик выберет каждый из игроков.
A 1, 6, 8,10,15,17
ОтветитьУдалитьB 2, 4, 9,11,13,18
C 3, 5, 7,12,14,16
A проигрывает B с вер. 19/36
B проигрывает C с вер. 19/36
C проигрывает A с вер. 19/36
но эту задачу я слышал раньше,
возможно у гарднера.
Кстати, решение задачи про пиратов не самое лучшее. Тот, кто разделяет кучи, будет в худшем положении, чем тот, кто выбирает.
ОтветитьУдалитьЕсли первый будет расставлять цифры таким образом, как указал AAbrosov, то он выиграет, т.к. он делает выбор вторым. Вопрос в том, как первый "догадался" расставить цифры таким образом :)
ОтветитьУдалитьAAbrosov, это хороший вариант, но лучший ли?
ОтветитьУдалитьАнонимный
ОтветитьУдалитьОх уж мне эти "очевидно". Очевидно - это когда посмотрел и сразу понял. В противном случае это "очевидно" является лишь "давлением на психику" и ничем более.
Andrew
Вовсе не важно как первый догадался до этой комбинации. AAbrosov же как-то догадался :)
Denis
Задача состоит не в том чтобы найти максимально возможную выигрышную комбинацию и решения AAbrosov'а вполне достаточно.
Чтож. Расскажу немного о своем решении (ответ схож с ответом AAbrosov'а).
Ничья/Проигрыш/Выигрыш будем считать как усредненные значения при числе опытов стремящемся к бесконечности при неизменном раскладе цифр на гранях кубиков(а не единичным случаем). Вариант с ничьей довольно легко реализуется. Поэтому выигрывает точно не второй игрок. Попробуем найти варианты когда выигрывает первый игрок.
Чтобы выиграл первый между кубиками должна существовать связь аналогичная "камень-ножницы-бумага".
Попробуем упростить задачу.
Пройдя двугранные "кубики" (там ничего внятного не получилось), попробуем проанализировать трехгранные "кубики" (так такие реализовать - загадка, но будем считать что таковые существуют).
Будем записывать числа на кубиках в левой колонке, а в правой количество раз которые он перебьет нижний. Исключение - третий кубик - сколько раз он перебьёт первый кубик.
Итак. На трех трехгранных кубиках всего 9 граней. Значит числа от 1 до 9. Что значительно упростит перебор значений.
Попробуем начать с такого: на первый кубик запишем 9, на второй - 8, на третий - 7.
1. 9 3(так как 9 больше всех)
2. 8 3(8 больше всех в 3ей строке)
3. 7 2(так как 7 больше всех цифр возможных на первом кубике кроме 9)
1. 9 3
2. 8 3
3. 7 2
Для минимального выигрыша сумма цифр в каждой строке второго столбика должна быть больше или равна 5. Попробуем уравнять к пяти на всех сроках.
Осталось попробовать расставить 6 чисел. Так как 3-я строка выигрывает первую только два раза, то другой гранью она должна уметь выигрывать два раза (три уже не сможет, 9 - не перебьёшь). А другой - 1 раз.
попробуем записать туда 6 (наибольшее из оставшихся чисел).
1. 9 3
2. 8 3
3. 76 22
Мы можем записать в первую строку 5. Тогда количество её выигрышей перед второй строкой станет на два больше = 5. То есть нужное нам количество.
1. 95 32
2. 8 3
3. 76 22
Мы видим, что во второй строке мы можем записать только числа меньшие 5. Значит, третье число в третьей строке должно быть таким маленьким, чтобы позволило себя побить два раза числами из второй строки, но настолько большим чтобы один раз побить первую строку. А первая строка не должна побить ни разу вторую.
1. 95t 32
2. 8xy 3
3. 76z 22
Имеем систему:
x > z,
y > z,
z > t.
Где значения t,z,x,y могут быть выбраны из чисел 1,2,3,4 без повторов.
Видим, что t самое маленькое число, это 1. z побольше, но меньше двух других, это 2, а x и y - это 3 и 4.
Получили.
1. 951 320 = 5
2. 834 311 = 5
3. 762 221 = 5
Т.е. расклад для трехгранных кубиках такой:
1. 951
2. 834
3. 762
.
При этом первый бьет второй, второй бьет третий, а третий бьет первый. (все с вероятностью 5/9)
Но кубики то у нас шестигранные! А не как в нашем упрощении. Переносим наши тройки чисел на шестигранные кубики. Дописать попробуем простым повторением первых чисел с добавлением 9.
1. 9 5 1 18 14 10
2. 8 3 4 17 12 13
3. 7 6 2 16 15 11
Каждый кубик выигрывает у следующего с вероятностью 19/36.
Значит, расклад нам подходит и выигрывает первый игрок.
В попытке сделать все "правильно", мне кажется, что пропущена одна ниточка. В задаче не требуется сделать кубики "равно-выигрышными". Вполне достаточно спихнуть первые маленькие номера на первый кубик (1-6) и затем уже работать с оставшимися двумя.
ОтветитьУдалитьЧестно говоря, не понял, почему вдруг кубики, которые предложили AAbrosov и Yku, выигрывают друг у друга по принципу камень-ножницы-бумага.
ОтветитьУдалитьПоправьте меня, если я неправ, но если сумма чисел на всех шести сторонах для двух кубиках равна, то в бесконечности они выиграют друг у друга одинаковое число раз.
Если один из трех кубиков будет с большей суммой, чем два других, то его может взять второй игрок, и тогда он будет чаще выигрывать. Поэтому для того, чтобы обеспечить лучший для себя вариант, первый сделает так, чтобы лучших кубиков было как минимум два. Он может сделать либо три кубика с одинаковой суммой, либо два кубика с одинаковой суммой, которая больше, чем сумма на третьем.
yku, спасибо за интересное описание хода мысли!
ОтветитьУдалитьeyeless-watcher, у Вас потрясающая интуиция! Мне кажется, самое главное - придумать эту идею. Реализовать её (как это сделали AAbrosov и yku) уже можно тупым перебором. Впрочем, реализовать тоже очень важно :)
Denis, хороший вопрос! Я знаю расстановку чисел на кубиках, которая позволяет выигрывать с вероятностью 21/36, что круче заявленной эффективности 19/36 :)
В данной постановке задачи не требуется находить наилучшее решение - достаточно показать, что первый сможет чаще выигрывать. Но было бы интересно произвести перебор всех возможных расстановок чисел по кубикам, чтобы найти наилучший вариант (кстати, это хорошая исследовательская задачка для школьников).
Shooshpanchick, могли бы Вы пояснить свою мысль?
cheaster, рассмотрим пару кубиков со следующими числами на гранях
ОтветитьУдалить1) 2, 3, 4, 5, 17, 18 (сумма 49);
2) 1, 6, 7, 8, 9, 10 (сумма 41).
У второй кости сумма значений на гранях меньше, но выигрывает она в 5 случаях из 9. Другими словами, мы только что опровергли Ваше предположение о том, что сумма чисел на гранях прямо указывает на победителя.
Пока максимум что нашел:
ОтветитьУдалить1 2 11 12 15 16
3 4 7 8 17 18
5 6 9 10 13 14
вероятность выиграть 24/36, т.е. в 2/3 случаев.
Есть подозрение что это максимум - доказательства пока придумать не могу...
dvz:
ОтветитьУдалитьесть подозрение что в таком раскладе вероятность выигрыша 20/36 а не 24/36. Автор обещает 21/36.
Проведенное мною компьютерное моделирование на 500 000 случайно раскрашенных троек кубиков показало, что
ОтветитьУдалитьполагающийся на удачу первый игрок выиграет в среднем в 40.6% случаев. Раскраска кубиков будет на стороне
стороне второго игрока с вероятностью 89.6%, справедливой с вероятностью 10.1%, на стороне первого - 0.4%.
Вероятность же оптимального, судя по комментариям, решения, настолько мала, что оно попалось лишь в двух случаях
из 500 000. Вот оно:
1 8 10 11 13 14
2 3 4 15 16 17
5 6 7 9 12 18
Раскрасив таким образом кубики, первый игрок выиграет с вероятностью 58.3% (или 21/36, или 7/12).
Интересно, кстати, к чему стремится вероятность выигрыша первого игрока при стремлении числа граней к бесконечности?
ОтветитьУдалитьdvz, 24/36 - это очень хорошая вероятность. Увы, в Вашей расстановке чисел по граням кубиков она не достигается.
ОтветитьУдалитьУважаемый аноним, Вы провели интересный эксперимент и нашли хорошее решение!
Поскольку первый игрок не обязан полагаться на удачу, то он всегда может рисовать себе оптимальные кубики. После того, как второй игрок выберет одну из трёх костей, первый возмёт ту из оставшихся двух, что победит с вероятностью 21/36.
Написав "тупой" алгоритм (не отличающийся универсальностью), но имеющий кое-какие оптимизации (например число 1 всегда на первом кубике), который перебрал все возможные комбинации. И блин, действительно 21/36 - самая лучшая "равновесная" комбинация. Есть, конечно, комбинации 25,21,21 из 36, но толку от них ноль (так как второй игрок, тоже умный).
ОтветитьУдалитьPS. Перебор был написан на 1С, и поэтому исполнялся довольно долго: около 5 часов. При этом было просмотренно всего около 6 миллионов комбинаций (возможно, можно еще оптимизировать, но я ничего не придумал). Обидно, а я так хотел получить хотя бы 22/36
Код не выкладываю, так как мне за него стыдно, и он очень большой для такой задачи :)
yku, уважаю! Спасибо, что рассказали об этом интересном эксперименте!
ОтветитьУдалитьКак сократить перебор ещё в два раза я написал в комментарии к следующей заметке: можно считать, что на втором кубике всегда будет самое маленькое из оставшихся 12-ти чисел (как Вы поступили с первым). Тогда как раз получится моя оценка в 3 миллиона комбинаций. Но это не такая уж и существенная оптимизация, так как ускорение в два раза в подобных одноразовых вычислениях ни на что не влияет :)
Если хочеться увидеть все комбинации, то
ОтветитьУдалитьперебор (Ruby):
def a_win_b( a, b )
a.inject( 0 ){ |result, elem|
result + b.inject( 0 ){ |r, e| if e < elem then r + 1 else r end }
}
end
def find_cubes( a, b, c, numbers )
total = 0
if( a.size == 6 and b.size == 6 and c.size == 6) then
if a_win_b( a, b ) > 18 and
a_win_b( b, c ) > 18 and
a_win_b( c, a ) > 18 then
puts " #{a}\t#{b}\tin #{a_win_b( a, b )}"
puts " #{b}\t#{c}\tin #{a_win_b( b, c )}"
puts " #{c}\t#{a}\tin #{a_win_b( c, a )}"
puts "\n"
total = 1
end
else
if a.size < 6 then
total += find_cubes( a + [ numbers[0] ], b, c, numbers[1..-1])
end
if b.size < 6 then
total += find_cubes( a, b + [ numbers[0] ], c, numbers[1..-1])
end
if c.size < 6 then
total += find_cubes( a, b, c + [ numbers[0] ], numbers[1..-1])
end
end
total
end
puts "\n\n#{find_cubes( [18], [], [], (1..17).map{|x| x}.reverse)}"
К сожалению формаитрование пропадает :(
cola, спасибо за код.
ОтветитьУдалитьПредложу ещё одни вариант, если не ошибаюсь выше он рассмотрен не был:
ОтветитьУдалитьА 1 2 3 4 5 6
Б 10 11 12 13 14 15
В 7 8 9 16 17 18
идея следующая - один кубик отбрасывается двумя игроками сразу, это от части упрощает выбор, отчасти позволяет сделать игру максимально честной. Что бы не выпало на кубике Б решающим будет кубик В, половина его чисел будет проигрышной, половина выигрышной, учитывая, что выпадение любого из чисел на кубике В событие равновероятное(3*1/6 на проигрыш и 3*1/6 на выигрыш) получаем строгие 50/50.
Интересный факт - при броске двух одинаковых 6ти гранных кубиков вероятность одного выиграть у другого равна 5/12 или 0,416666667, за счёт ничьей. При этом шансы действительно равны у обоих игроков, как проиграть, так и выиграть. При подкидывании монетки с числами 1 и 2 вероятность выигрыша 1/4 или 0,25. Оптимисты - берите кубики с большим количеством граней, это повысит ваш шанс на успех, пессимисты - кидайте монетку, вероятность проигрыша минимальна))