1. Главная
  2. Библиотека
  3. Теория вероятностей
  4. Реши задачу по информатике: Два игрока, Петя и Ваня, иг...
Решение задачи на тему

Реши задачу по информатике: Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в

  • Теория вероятностей
  • #Дискретная математика
  • #Теория игр
Реши задачу по информатике: Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в

Условие:

Реши задачу по информатике: Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 65 или больше камней. В начальный момент в куче былоS камней; 1 ≤ S ≤ 64.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Решение:

Найдем такие исходные количества камней S, при которых Петя не может выиграть за один ход (то есть ни добавлением 1, ни удвоением не получится получить не менее 65 камней) и при этом у него существует стратегия, позволяющая выиграть своим вторым ходом вне зависимости от ответов Вани.

Шаг 1. Ограничим значения S по условию отсутствия выигрыша за один ход. При ходе Петя может сделать одно из двух действий:   – добавить один камень: S → S + 1;   – удвоить камни: S → 2·S. Чтобы ни один из этих ходов не выигрывал (то есть результат меньше 65), должны выполняться неравенства:   S + 1 65 ⇒ S ≤ 63, ...

Выбери предмет