Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в четыре раза. Например, пусть в одной куче 7 камней, а в другой 9 камней; такую позицию мы будем обозначать (7, 9). За один ход из позиции (7, 9) можно получить любую из четырёх позиций: (8, 9), (28, 9), (7, 10), (7, 36). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 151. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 151 или больше камней. В начальный момент в первой куче было 9 камней, во второй куче — S камней; 1 ≤ S ≤ 141. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Answer 1

Ответ:

Заметим, что игра должна закончиться в 2 хода. Минимальное значение количества камней в обеих кучах, при котором игра заканчивается — 77. Эта ситуация возможна, например, когда в первой куче 7 камней, а во второй — 70. Значит, чтобы Ваня мог выиграть своим первым ходом, количество камней во второй куче должно быть ≥35. Поскольку удваиванием число 35 получить нельзя, после первого хода Пети во второй куче должно получиться 36 камней. Это возможно при значении S = 18. При таком минимальном значении S Ваня выиграет своим первым ходом после неудачного хода Пети.

Ответ:18.

Объяснение:

Answer 2

Для поиска двух таких значений S, при которых у Пети есть выигрышная стратегия, удовлетворяющая указанным условиям, мы можем воспользоваться динамическим программированием.

Давайте начнем с S = 141 (максимальное значение для S). Создадим таблицу, в которой будем хранить информацию о том, может ли Петя выиграть из каждой возможной позиции. Для этого будем идти от S = 141 и уменьшать S, проверяя каждую позицию.

1. Начнем с S = 141. Петя не может выиграть за один ход, так как S слишком большое, и он не может добавить столько камней, чтобы добраться до 151.

2. Теперь рассмотрим ходы Вани из позиции (9, 141). Ваня может либо добавить один камень в первую кучу, получив (10, 141), либо увеличить количество камней во второй куче в четыре раза, получив (9, 564). Важно отметить, что в этой ситуации Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Если Ваня добавит один камень в первую кучу, Петя увеличит количество камней во второй куче в четыре раза, превратив ее в (9, 2256). Если Ваня увеличит количество камней во второй куче в четыре раза, Петя добавит один камень в первую кучу, превратив ее в (10, 564). В обоих случаях Петя добьется победы на своем втором ходу, так как у него будет возможность привести одну из куч к 151 или больше, независимо от хода Вани.

Таким образом, одним из ответов является S = 141.

Теперь давайте рассмотрим S = 140. Изначально у нас будет позиция (9, 140).

1. Петя начинает, и он не может выиграть за один ход.

2. Теперь рассмотрим ходы Вани:

   • Если Ваня добавит один камень в первую кучу, получится (10, 140).
   • Если Ваня увеличит количество камней во второй куче в четыре раза, получится (9, 560).

3. Петя может выиграть своим вторым ходом в обоих случаях:

   • Если Ваня выберет (10, 140), Петя увеличит количество камней во второй куче в четыре раза, превратив ее в (9, 560).
   • Если Ваня выберет (9, 560), Петя добавит один камень в первую кучу, превратив ее в (10, 560).

В обоих случаях Петя сможет добиться победы на своем втором ходу, так как у него будет возможность привести одну из куч к 151 или больше, независимо от хода Вани.

Таким образом, вторым ответом является S = 140.

Итак, два значения S, при которых у Пети есть выигрышная стратегия, удовлетворяющая указанным условиям, это S = 140 и S = 141.