MAX-SAT: дерандомизация/Задачи/shell-game — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 31: Строка 31:
 
Подсчитайте матожидание выигрыша для каждой из стратегий.
 
Подсчитайте матожидание выигрыша для каждой из стратегий.
  
[[Category:Нерешенные задачи]]
+
[[Category:На проверку]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 +
 +
===Стенина Мария, группа 974===
 +
 +
<latex>
 +
Обозначим через $x$ наш выигрыш. Посчитаем математическое ожидание $\mathbb{E}x$ для каждой стратегии.
 +
 +
а) Не играть. $\mathbb{E}x = 0$.
 +
 +
б) Выбираем наперсток А и открываем его. Вероятность того, что шарик окажется именно в этом наперстке, равна $\frac{1}{3}$. Отсюда имеем ожидаемый выигрыш
 +
$$
 +
    \mathbb{E}x = \frac{1}{3} \cdot 50 + 2 \cdot \left( \frac{1}{3} \cdot (-50) \right) = -\frac{50}{3}.
 +
$$
 +
 +
Стратегии в) и г) укладываются в схему так называемого парадокса Монти Холла. Мы выбираем наперсток А. Вероятность того, что шарик находится именно в этом наперстке, равна $\frac{1}{3}$, а вероятность того, что в одном из двух не выбранных, $\frac{2}{3}$. Причем до открытия ведущим пустого наперстка из двух невыбранных вероятность того, что шарик в любом из них, равна $\frac{2}{3} \cdot \frac{1}{2}$, где $\frac{1}{2}$ --- условная вероятность нахождения шарика в наперстке В или С. После же открытия пустого наперстка В условные вероятности для этих двух наперстков перераспределяются и получается, что в наперстке В шарик находится с вероятностью $\frac{2}{3} \cdot 0 = 0$, а в наперстке С с вероятностью $\frac{2}{3} \cdot 1 = \frac{2}{3}$. Отсюда для двух последних стратегий имеем ожидаемые выигрыши (считаем, что доплаченные 10 рублей идут ведущему безвозвратно)
 +
 +
в) $\mathbb{E}x = \frac{1}{3} \cdot 40 + \frac{2}{3} \cdot (-60) = -\frac{80}{3}$,
 +
 +
г) $\mathbb{E}x = \frac{1}{3} \cdot (-60) + \frac{2}{3} \cdot 40 = \frac{20}{3}$.
 +
 +
Из чего можно сделать вывод, что наиболее предпочтительна стратегия г). Хотя в любом случае не советую играть в азартные игры со случайными попутчиками в проезде :)
 +
 +
</latex>

Версия 11:38, 9 ноября 2014

Shell-game.svg

Честный попутчик в поезде предлагает вам сыграть в следующую игру, вариант классического «наперстка». т. е. есть

  • три наперстка,
  • шарик,
  • ваша задача
    • обнаружить шарик - тогда вы выигрываете,
    • иначе - выигрывает сдающий.

Каждый раз на кон, вы и сдающий, ставите по 50 рублей.

Сдающий тасует три наперстка, и прячет под одним из них шарик. Затем он предлагает вам выбрать наперсток.

После того, как вы выбрали наперсток (пусть это будет наперсток «A»), вы можете

  • открыть его, либо,
  • заплатив еще 10 рублей, потребовать от сдающего, открыть пустой наперсток из двух оставшихся (пусть открытый будет «B»), после чего выбрать один из двух закрытых наперстков (т.е. «A» или «С»).

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

Какая стратегия оптимальна?

  • Не играть. Выигрыш - «0».
  • Выбрать наперсток «A» и открыть его.
  • Выбрать наперсток «A», «купить» открытие пустого наперстка «B», но выбрать наперсток «A».
  • Выбрать наперсток «A», «купить» открытие пустого наперстка «B», и выбрать наперсток «С».

Дорога длинная, играть можно много раз, правильная стратегия может привести к существенному обогащению, неправильная - к разорению…

Обоснуйте. Подсчитайте матожидание выигрыша для каждой из стратегий.

Стенина Мария, группа 974