Question

Отдам все баллы решите пожалуйста Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 52. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 52 камня или больше. В начальный момент в первой куче было 6 камней, во второй – S камней, 1 ≤ S ≤45. Определите выигрышная или проигрышная позиция для игрока, делающего первый ход, если перед игроками лежит: а) 17; б) 20; с) 21 камней.

Answer 1

Ответ:

a) проигрышная позиция

б) выигрышная позиция

с) выигрышная позиция

Answer 2

Для определения выигрышных или проигрышных позиций в этой игре, можно использовать метод динамического программирования. Обозначим через "W" выигрышную позицию (то есть позицию, при которой игрок, делающий ход, выигрывает), а через "L" проигрышную позицию (позицию, при которой игрок, делающий ход, проигрывает).

Посмотрим на различные ситуации:

а) Начальное количество камней: 17. Петя может либо добавить 3 камня, либо удвоить кучу (получив 12 или 34). Если Петя добавит 3 камня, то останется 20 камней, что является проигрышной позицией для следующего игрока. Если Петя удвоит кучу, то останется 34 камня, что также является проигрышной позицией для следующего игрока. Итак, начальная позиция (17) является выигрышной: W.

б) Начальное количество камней: 20. Петя может либо добавить 3 камня, либо удвоить кучу (получив 15 или 40). Если Петя добавит 3 камня, то останется 23 камня, что является проигрышной позицией для следующего игрока. Если Петя удвоит кучу, то останется 40 камней, что также является проигрышной позицией для следующего игрока. Итак, начальная позиция (20) является выигрышной: W.

с) Начальное количество камней: 21. Петя может либо добавить 3 камня, либо удвоить кучу (получив 18 или 42). Если Петя добавит 3 камня, то останется 24 камня, что является выигрышной позицией для следующего игрока (так как следующий игрок получит 21 камень и окажется в позиции, которая для него выигрышная). Если Петя удвоит кучу, то останется 42 камня, что также является выигрышной позицией для следующего игрока. Итак, начальная позиция (21) является проигрышной: L.

Итак, ответы на вопросы:

а) Начальное количество камней: 17 - выигрышная позиция (W). б) Начальное количество камней: 20 - выигрышная позиция (W). с) Начальное количество камней: 21 - проигрышная позиция (L).