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

Проект МЦНМО
при участии
школы 57
Задача 65264
Темы:    [ Дискретное распределение ]
[ Делимость чисел. Общие свойства ]
Сложность: 3+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Петя играет в компьютерную игру “Куча камней”. Сначала в куче 16 камней. Игроки по очереди берут из кучи 1, 2, 3 или 4 камня. Выигрывает тот, кто заберёт последний камень. Петя играет впервые и поэтому каждый раз берёт случайное число камней, при этом он не нарушает правила игры. Компьютер играет по следующему алгоритму: на каждом ходу он берёт столько камней, чтобы оказаться в наиболее выгодном положении. Игру начинает всегда Петя. С какой вероятностью Петя выиграет?


Решение

  Заметим, что игрок, делающий первый ход, всегда имеет преимущество и выигрывает при правильной стратегии. Действительно, на первом шаге нужно взять один камень из кучи, а на каждом последующем шаге брать такое количество камней, чтобы число оставшихся камней делилось на 5. Поскольку согласно правилам игры на каждом шаге разрешено брать 1, 2, 3 или 4 камня, то такая стратегия всегда осуществима.
  В то же время, если на каком-то из шагов игрок, делающий первый ход, отступит от этой стратегии, то его соперник имеет возможность выиграть игру, воспользовавшись той же стратегией. Заметим также, что если в игре побеждает игрок, делающий первый ход, то он обязательно делает за игру 4 хода.
  Таким образом, у Пети при каждом ходе есть только одна возможность не проиграть: если он возьмёт один камень первым ходом, оставит компьютеру ровно 10 камней вторым ходом, ровно 5 камней третьим и возьмёт все оставшиеся камни на четвёртом.
  После каждого Петиного хода компьютер, чтобы минимизировать вероятность своего проигрыша, должен взять один камень. Тогда Петя выигрывает, только если будет брать 4 камня из четырёх оставшихся до делимости на 5.
  Таким образом, вероятность выигрыша Пети равна  (¼)4 = 1/256,  где ¼ – вероятность того, что в свой ход Петя возьмёт правильное количество камней.


Ответ

1/256.

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

олимпиада
Название Заочная олимпиада по теории вероятностей и статистике
год
Дата 2008
задача
Номер 7

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

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