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

Версия 09:08, 20 февраля 2020

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

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

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

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

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

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

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

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

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

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

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