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