Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 2 камня или увеличить количество камней в куче в 2 раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Если при этом в куче оказалось не более 70 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 68. Укажите такое минимальное значение числа S, при котором Ваня может выиграть своим первым ходом при любой игре Пети.

Ответ: 16

Пошаговое решение:

• Анализ конечной позиции:

  Выигрышная позиция - это когда в куче от 33 до 70 камней включительно. Проигрышная позиция - когда в куче больше 70 камней.

• Определение выигрышных и проигрышных ходов:

  • Если после хода Вани, вне зависимости от хода Пети, Ваня сможет следующим ходом выиграть, то это выигрышная стратегия для Вани.

• Рассмотрим S = 16:

  Первым ходом Ваня удваивает количество камней: 16 * 2 = 32.

  Теперь у Пети есть два варианта хода:

  • Петя добавляет 2 камня: 32 + 2 = 34. Ваня удваивает: 34 * 2 = 68 (Ваня выигрывает, так как 33 ≤ 68 ≤ 70).
  • Петя удваивает количество камней: 32 * 2 = 64. Ваня добавляет 2 камня: 64 + 2 = 66 (Ваня выигрывает, так как 33 ≤ 66 ≤ 70).

  В обоих случаях Ваня выигрывает следующим ходом, значит, S = 16 является выигрышной стратегией для Вани.

• Проверка меньших значений:

  Если S меньше 16, то Ваня не сможет создать ситуацию, при которой любой ход Пети приведет к его проигрышу.

Ответ: 16