Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может 1) добавить в кучу три камня или 2) увеличить количество камней в куче в два раза и убрать из кучи 1 камень. Например, имея кучу из 10 камней, за один ход можно получить кучу из 13 или 19 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершится в тот момент, когда количество камней в куче становится не менее 38 камней. Победителем считает игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 38 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 37. 1. При каких S: 1a) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом? 2. Назовите все значения S, при которых Петя может выиграть своим вторым ходом? 3. Назовите все значения S, при которых Ваня выигрывает своим первым или вторым ходом.

Answer 1

1а) Заметим, что для всех S≥5 операция 2) более выгодна, чем 1). Тогда ясно, что для всех S таких, что S∈N, 2S-1≥38 ⇔ S≥20 Петя может использовать операцию 2) и сразу же выиграть. Очевидно, что для остальных S это невозможно.

1б) Ваня выигрывает первым ходом, если к его ходу в куче не меньше 20 камней, причем до хода Пети в куче был меньше 20 камней. Отсюда S+3≥20 ⇔ S≥17. Получаем, что S ∈ [17;19];

2) Очевидно, что Петя выигрывает своим вторым ходом, если выполняются следующие условия: (i) Петя не выиграл первым ходом (⇔S≤19), (ii) Следующим ходом не выиграл Ваня (⇔S≤16). Эти два условия выполняются при S≤16. Ясно также, что при 11≤S≤13 Петя не сможет выиграть вторым ходом: Петя добавляет 3 камня, точно также может поступить Ваня, то есть будет не более 19 камней, чего недостаточно. Если S≤8, то ко второму ходу будет не более 15 камней, а Ваня может добавить всего 3, итого 18, чего опять недостаточно. При S=9 или 10 все работает: ко второму ходу Пети будет не менее 20 камней (Петя может так сделать). S∈[9;10]∪[14;16]

3) Ваня выигрывает своим первым или вторым ходом - это объединение значений, при которых он выигрывает первым ходом и при которых он выигрывает вторым ходом. Первым ходом он выигрывает при S∈[17;19]. Петя не выигрывает своим вторым ходом (и первым) при S∈[11;13]. Поработаем с остальными значениями. Заметим, что, если после первого хода число попадает в область S∈[9;10]∪[14;16] - то это те и только те значения на момент первого хода Вани, при которых он выигрывает вторым ходом. Это неминуемо при 11≤S≤14 - либо Ваня выиграет первым ходом, либо вторым.

Ответ: 1а) 20≤S≤37

           1б) S=17, 18, 19

           2) S=9, 10, 14, 15, 16

           3) S=11, 12, 13, 14, 17, 19

Answer 2

Давайте рассмотрим каждый вопрос по порядку:

1. При каких значениях S: а) Петя выигрывает первым ходом? Петя выиграет первым ходом, если он может достигнуть кучи из 38 или больше камней за один свой ход. Это возможно, если S равно 36 или 37. Петя может либо добавить 3 камня, получив 39 камней, либо увеличить количество камней в два раза и убрать 1, получив 38 камней.

   б) Ваня выигрывает первым ходом? Ваня выиграет первым ходом, если он может достигнуть кучи из 38 или больше камней за один свой ход. Это возможно, если S равно 35. Ваня может либо добавить 3 камня, получив 38 камней, либо увеличить количество камней в два раза и убрать 1, получив 38 камней.

2. Назовите все значения S, при которых Петя может выиграть своим вторым ходом? Чтобы Петя выиграл своим вторым ходом, он должен оставить кучу из 38 камней после своего первого хода (так как он начинает игру). Это возможно, если S равно 31, 32, 33 или 34. Независимо от того, какое из этих значений S он выберет, Петя всегда может добавить 3 камня и получить 34 + 3 = 37 камней. На следующем ходу, при S = 37, он может увеличить количество камней в два раза и убрать 1, достигнув 38 камней и победив.

3. Назовите все значения S, при которых Ваня выигрывает своим первым или вторым ходом? Чтобы Ваня выиграл своим первым или вторым ходом, он должен оставить кучу из 38 камней после своего хода. Это возможно, если S равно 30, 31, 32, 33 или 34. Ваня может добавить 3 камня к значениям S = 30, 31, 32 или 33 и получить 33, 34, 35 или 36 камней соответственно. Затем он может увеличить количество камней в два раза и убрать 1, достигнув 38 камней и победив. Если S = 34, Ваня может достичь 38 камней сразу, добавив 4 камня.

Итак, вот все значения S, удовлетворяющие условиям: 1а) Петя выигрывает первым ходом: S = 36, 37 1б) Ваня выигрывает первым ходом: S = 35

2. Петя выигрывает своим вторым ходом: S = 31, 32, 33, 34
3. Ваня выигрывает своим первым или вторым ходом: S = 30, 31, 32, 33, 34