Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 40 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 39. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Найдите все такие значения числа S, при которых Петя может выиграть за один ход. В качестве ответа укажите без пробелов и запятых наименьшее и наибольшее возможные значения. Например, если S = 10...20, то в ответе необходимо указать 1020. Для игры, описанной в предыдущем задании, укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Давайте рассмотрим игру, чтобы определить, какие значения S позволят Пете выиграть за один ход, а также то значение S, при котором Петя не может выиграть, но Ваня сможет выиграть в ответ на любой ход Пети.
1. Найдем значения S, при которых Петя может выиграть за один ход
Петя может выиграть за один ход, если:
- Добавит 1 камень: S + 1 ≥ 40
- Добавит 2 камня: S + 2 ≥ 40
- Удвоит количество камней: 2 * S ≥ 40
Таким образом, решаем соответствующие неравенства:
- S + 1 ≥ 40 => S ≥ 39
- S + 2 ≥ 40 => S ≥ 38
- 2 * S ≥ 40 => S ≥ 20
Итак, возможные значения S для выигрыша Пети за один ход:
- S = 39 (можно добавить 1 камень)
- S = 38 (можно добавить 2 камня)
- S = 20 (можно удвоить)
Таким образом, наименьшее и наибольшее S, при которых Петя может выиграть за один ход, это 20 и 39 соответственно. Ответ: 2039.
2. Теперь определим значение S, при котором Петя не может выиграть за один ход, но Ваня может выиграть на своем первом ходе
Для этого определим такие позиции S, что:
- Для любого хода Пети (добавление 1, добавление 2, удвоение), Ваня сможет ответить таким образом, чтобы достичь 40 или более камней в следующем ходе.
Переберем возможные значения S:
- S = 36: Петя может добавлять 1 или 2, будет 37 или 38, Ваня удваивает до 74 или добавляет 2 до 40. Ваня выигрывает.
- S = 37: Петя не может выиграть, Ваня может добавить 2 и победить.
- S = 38: С прошлого анализа, если Петя добавит 1, Ваня добавляет 2 до 40, либо удваивает и выигрывает, не оставляя шансов.
- S = 39: Здесь Петя точно выигрывает, поскольку добавив 1, он достигает 40.
Таким образом, единым S, где Петя не может выиграть, а Ваня может победить на следующем ходе, является 37.
Ответ: 37.
