ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 67138
Тема:    [ Теория алгоритмов (прочее) ]
Сложность: 4
Классы: 7,8,9,10,11
В корзину
Прислать комментарий

Условие

Казино предлагает игру по таким правилам. Игрок ставит любое целое число долларов (но не больше, чем у него в этот момент есть) либо на орла, либо на решку. Затем подбрасывается монета. Если игрок угадал, как она упадёт, он получает назад свою ставку и столько же денег впридачу. Если не угадал — его ставку забирает казино. Если игроку не повезёт четыре раза подряд, казино присуждает ему в следующей игре утешительную победу вне зависимости от того, как упадёт монета. Джо пришёл в казино со 100 долларами. Он обязался сделать ровно пять ставок и ни разу не ставить больше 17 долларов. Какую наибольшую сумму денег он сможет гарантированно унести из казино после такой игры?

Решение

Главное наблюдение в этой задаче такое: как только игрок один раз угадает, как упадёт монетка — все оставшиеся игры он может не угадать. Поэтому все ставки после победы должны быть по 1 доллару.

Для начала покажем, что уйти, потеряв 1 доллар или меньше, игроку не удастся. Посмотрим, что для этого ему пришлось бы делать.

  1. В первый раз игроку придётся поставить не менее 3 долларов, потому что он мог выиграть эту игру и проиграть 4 следующие.
  2. Если бы он проиграл в первой игре, то во второй ему бы пришлось поставить не менее 5 долларов: ведь он может выиграть только эту партию, а проиграть минимум 3 доллара на предыдущей и ещё минимум 3 на следующих трёх.
  3. Если он проиграл и вторую игру, то на третьей его ставка должна быть уже минимум 9 долларов: если выиграет, то ему надо компенсировать минимум 10 долларов от поражений (3 за первую игру, 5 за вторую, по 1 за четвёртую и пятую).
  4. Если он проиграл и третью игру, то на четвёртой ему придётся поставить уже минимум 17 долларов: выигрыш должен компенсировать минимум 3 + 5 + 9 + 1 = 18 долларов от поражений.
  5. Если он проиграл и четвёртую игру, то он уже проиграл минимум 3 + 5 + 9 + 17 = 34 доллара и даже максимальной ставкой в 17 долларов он не сможет компенсировать себе убыток.

Теперь докажем, что игрок может ставить так, чтобы уйти, потеряв всего 2 доллара. Аналогично рассуждениям выше, понимаем, что пока игрок проигрывает, он должен ставить 2, затем 3, 5, 9 и 17 долларов, а как только выиграет — все следующие партии ставить по 1 доллару. Несложно проверить, что в каждой ситуации игрок потеряет не более 2 долларов.

Комментарий. Заметим, что если разрешить игроку ставить не более 5 раз, то он может «остаться в плюсе». Для этого ему достаточно ставить 1, 2, 4, 8 и 16 долларов и уходить после того, как он выиграл: тогда он точно выиграет 1 доллар. Доказательство того, что в этом случае нельзя выиграть больше, аналогично доказательству из решения.

Ответ

98.

Источники и прецеденты использования

олимпиада
Название Турнир им.Ломоносова
номер/год
Год 2022
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .