Задание 26. Выигрышная стратегия. ЕГЭ 2020 по информатике

За это задание ты можешь получить 3 балла. На решение дается около 30 минут. Уровень сложности: высокий.
Средний процент выполнения: 48.6%
Ответом к заданию 26 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).

Задачи для практики

Задача 1

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (60, 10), (20, 11), (20, 30).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 143. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах всего будет 143 или больше камней. В начальный момент в первой куче было 34 камня, во второй куче — S камней; 1 ≤ S ≤ 140.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть за один ход и соответствующие выигрышные ходы. Если при некотором значении S Коля может выиграть несколькими способами, достаточно указать один выигрышный ход.

б) Укажите, сколько существует значений S, при которых Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.

Задание 2. Укажите такое значение S, при котором у Коли есть выигрышная стратегия, причём одновременно выполняются два условия:

—Коля не может выиграть за один ход;

—Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.

Для указанного значения S опишите выигрышную стратегию Коли.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

— у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

—у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Саши.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Саши (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.

В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.

Решение

Пусть S —исходное количество камней во второй куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {37, 38, . . . , 140}.

Во всех случаях ему нужно утроить количество камней во второй куче. Если количество камней во второй куче меньше 37, то за один ход нельзя получить суммарное число камней в двух кучах более 142.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно во второй куче будет S = 36 камней, то есть начальной будет позиция (34, 36), то после первого хода Коли может получиться одна из четырёх позиций: (35, 36)—всего 71, (34, 37) — всего 71, (102, 36) — всего 138, (34, 108) — всего 142. В каждом из полученных случаев суммарное число камней не превышает 142. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней во второй куче, получит соответственно позиции (35, 108)— всего 143, (34, 111)— всего 145, (102, 108)—всего 210, (35, 324)—всего 359.В каждом случае суммарное число камней не менее 143. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Возможное значение S = 35. Если начальная позиция (34, 35), то Коля, чтобы выиграть своим вторым ходом, должен получить позицию (34, 36). Для этого ему нужно в кучу с 35 камнями добавить один камень. Считая позицию (34, 36) начальной, мы приходим к рассмотрению ситуации задания 1б.

При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (34, 35), то выиграет Коля своим вторым ходом.

Задание 3. Возможное значение S = 34. Если начальная позиция (34, 34), то после первого хода Коли может получиться одна из четырёх позиций: (34, 35), (35, 34) — всего 69, (102, 34), (34, 102)—всего 136.

Если после хода Коли получены позиции (34, 102), (102, 34), то Саша, утроив число камней в куче с 34 камнями, получит позицию с суммарным числом камней, равным 204, и выиграет своим первым ходом.

Если после хода Коли получены позиции (34, 35), (35, 34), то Саша, увеличив в одной из куч число камней на 1, получит позиции (34, 36) или (36, 34) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(34, 34) (34, 35) (34, 36) (35, 36) (35, 108)
  (34, 37) (34, 111)
(102, 36) (102, 108)
(34, 108) (34, 324)
(35, 34) (36, 34) (36, 35) (108, 35)
(37, 34) (111, 34)
(36, 102) (108, 102)
(108, 34) (324, 34)
(102, 34) (102, 102)    
(34, 102) (102, 102)    
Ответ:
Показать решение

Задача 2

Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (60, 10), (20, 11), (20, 30).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 167. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 167 или больше камней. В начальный момент в первой куче было 40 камней, во второй куче—S камней; 1 ≤ S ≤ 160.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

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

Задание 2. Укажите такое значение S, при котором у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:

—Паша не может выиграть за один ход;

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

Для указанного значения S опишите выигрышную стратегию Паши.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

— у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;

—у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вовы.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.

В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.

Решение

Пусть S —исходное количество камней во второй куче.

Задание 1. a) Паша может выиграть первым ходом, если S ∈ {43, 44, . . . , 160}.

Во всех случаях ему нужно удвоить количество камней во второй куче.

Если количество камней во второй куче меньше 43, то за один ход нельзя получить суммарное число камней в двух кучах более 166.

Задание 1. б) Вова может выиграть первым ходом (как бы ни играл Паша), если исходно во второй куче будет S = 42 камня, то есть начальной будет позиция (40, 42), то после первого хода Паши может получиться одна из четырёх позиций: (41, 42)— всего 83, (120, 42)—всего 162, (40, 43)—всего 83, (40, 126)— всего 166.

В каждом из полученных случаев суммарное число камней меньше, чем 169. Значит, Паша не может выиграть своим первым ходом. Для каждой из полученных позиций Вова, утроив число камней во второй куче, получит соответственно позиции (41, 126)—всего 167, (120, 126)—всего 246, (40, 129)—всего 169, (40, 378) — всего 418. В каждом случае суммарное число камней не менее 167. Следовательно, Вова выигрывает своим первым ходом.

Задание 2. Возможное значение S = 41. Если начальная позиция (40, 41), то Паша, чтобы выиграть своим вторым ходом, должен получить позицию (40, 42). Для этого ему нужно в кучу с 42 камнями добавить один камень. Считая позицию (40, 42) начальной, мы приходим к рассмотрению ситуации задания 1б.

При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (40, 41), то выиграет Паша своим вторым ходом.

Задание 3. Возможное значение S = 40. Если начальная позиция (40, 40), то после первого хода Паши может получиться одна из четырёх позиций: (40, 41), (41, 40) — всего 81, (120, 40), (40, 120)—всего 160.

Если после хода Паши получены позиции (120, 40), (40, 120), то Вова, утроив число камней в куче со 120 камнями, получит позицию с суммарным числом камней, равным 400, и выиграет своим первым ходом.

Если после хода Паши получены позиции (40, 41), (41, 40), то Вова, увеличив в одной из куч число камней на 1, получит позиции (40, 42) или (42, 40) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Вовы. Заключительные позиции (в них выигрывает Вова) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Паши
(разобраны все ходы)
1-й ход Вовы
(только ход по стратегии)
2-й ход Паши
(разобраны все ходы)
2-й ход Вовы
(только ход по стратегии)
(40, 40) (40, 41) (40, 42) (120, 42) (120, 126)
  (41, 42) (41, 126)
(40, 126) (40, 378)
(40, 43) (40, 129)
(41, 40) (42, 41) (42, 120) (126, 120)
(42, 41) (126, 41)
(126, 40) (378, 40)
(43, 40) (129, 40)
(120, 40) (120, 120)    
(40, 120) (120, 120)    
Ответ:
Показать решение

Задача 3

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (40, 10), (20, 11), (20, 20).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 62. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 62 или больше камней. В начальный момент в первой куче было 19 камней, во второй куче—S камней; 1 ≤ S ≤ 60. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть за один ход и соответствующие выигрышные ходы. Если при некотором значении S Коля может выиграть несколькими способами, достаточно указать один выигрышный ход.

б) Укажите, сколько существует значений S, при которых Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.

Задание 2. Укажите такое значение S, при котором у Коли есть выигрышная стратегия, причём одновременно выполняются два условия:

—Коля не может выиграть за один ход;

—Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.

Для указанного значения S опишите выигрышную стратегию Коли.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

— у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

—у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.

Решение

Пусть S —исходное количество камней во второй куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {22, 23, . . . , 60}. Во всех случаях ему нужно удвоить количество камней во второй куче. Если количество камней во второй куче меньше 22, то за один ход нельзя получить суммарное число камней в двух кучах более 62.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно во второй куче будет S = 21 камень, то есть начальной будет позиция (19, 21), то после первого хода Коли может получиться одна из четырёх позиций: (19, 22) — всего 41, (20, 21) — всего 41, (38, 21) — всего 59, (19, 42) — всего 61. В каждом из полученных случаев суммарное число камней не превышает 62. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (19, 44) — всего 63, (20, 42) — всего 62, (38, 42) — всего 80, (19, 84)—всего 103.

В каждом случае суммарное число камней не менее 62. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Возможное значение S = 20. Если начальная позиция (19, 20), то Коля, чтобы выиграть своим вторым ходом, должен получить позицию (19, 21). Для этого ему нужно в кучу с 20 камнями добавить один камень. Считая позицию (19, 21) начальной, мы приходим к рассмотрению ситуации задания 1б.

При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (19, 20), то выиграет Коля своим вторым ходом.

Задание 3. Возможное значение S = 19. Если начальная позиция (19, 19), то после первого хода Коли может получиться одна из четырёх позиций: (20, 19), (19, 20) — всего 39, (38, 19), (19, 38) — всего 57. Если после хода Коли получены позиции (19, 38), (38, 19), то Саша, удвоив число камней в куче с 38 камнями, получит позицию с суммарным числом камней, равным 95, и выиграет своим первым ходом. Если после хода Коли получены позиции (20, 19), (19, 20), то Саша, увеличив в куче с 20 камнями их число на 1, получит позиции (21, 19) или (19, 21) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом. В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(19, 19) (19, 20) (19, 21) (19, 22) (19, 44)
  (20, 21) (20, 42)
(19, 42) (19, 84)
(38, 21) (38, 42)
(20, 19) (21, 19) (22, 19) (44, 19)
(21, 20) (42, 20)
(42, 19) (84, 19)
(21, 38) (42, 38)
(38, 19) (76, 19)    
(19, 38) (19, 76)    
Ответ:
Показать решение

Задача 4

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (40, 10), (20, 11), (20, 20).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 86. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 86 или больше камней. В начальный момент в первой куче было 27 камней, во второй куче—S камней; 1 ≤ S ≤ 85.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть за один ход и соответствующие выигрышные ходы. Если при некотором значении S Коля может выиграть несколькими способами, достаточно указать один выигрышный ход.

б) Укажите, сколько существует значений S, при которых Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.

Задание 2. Укажите такое значение S, при котором у Коли есть выигрышная стратегия, причём одновременно выполняются два условия:

—Коля не может выиграть за один ход;

—Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.

Для указанного значения S опишите выигрышную стратегию Коли.

Задание 3. Укажите значение S, при котором одновременно выполняются условия:

— у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

—у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Саши.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Саши (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.

В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.

Решение

Пусть S —исходное количество камней во второй куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {30, 36, . . . , 85}.

Во всех случаях ему нужно удвоить количество камней во второй куче.

Если количество камней во второй куче меньше 30, то за один ход нельзя получить суммарное число камней в двух кучах более 85.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно во второй куче будет S = 29 камней, то есть начальной будет позиция (27, 29), то после первого хода Коли может получиться одна из четырёх позиций: (28, 29) — всего 57, (54, 29) — всего 83, (27, 30) — всего 57, (27, 58) — всего 85. В каждом из полученных случаев суммарное число камней не превышает 86.

Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (28, 58) — всего 86, (54, 58)—всего 112, (27, 60)—всего 87, (27, 116)—всего 143. В каждом случае суммарное число камней не менее 86. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Возможное значение S = 28. Если начальная позиция (27, 28), то Коля, чтобы выиграть своим вторым ходом, должен получить позицию (27, 29). Для этого ему нужно в кучу с 28 камнями добавить один камень. Считая позицию (27, 29) начальной, мы приходим к рассмотрению ситуации задания 1б.

При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (27, 28), то выиграет Коля своим вторым ходом.

Задание 3. Возможное значение S = 27. Если начальная позиция (27, 27), то после первого хода Коли может получиться одна из четырёх позиций: (28, 27), (27, 28) — всего 55, (54, 27), (27, 54)—всего 81.

Если после хода Коли получены позиции (54, 27), (27, 54), то Саша, удвоив число камней в куче с 54 камнями, получит позицию с суммарным числом камней, равным 135, и выиграет своим первым ходом.

Если после хода Коли получены позиции (28, 27), (27, 28), то Саша, увеличив в одной из куч число камней на 1, получит позиции (27, 29) или (29, 27) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(27, 27) (28, 27) (29, 27) (29, 28) (58, 28)
  (29, 54) (58, 54)
(30, 27) (60, 27)
(58, 27) (116, 27)
(27, 28) (27, 29) (28, 29) (123, 29)
(54, 29) (360, 29)
(27, 30) (120, 30)
(27, 58) (120, 87)
(54, 27) (108, 27)    
(27, 54) (27, 108)    
Ответ:
Показать решение

Задача 5

Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 8 камней, за один ход можно получить кучу из 10 или 16 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 32. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 32 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

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

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

Задание 2. Укажите два таких значения S, при которых у Паши есть выигрышная стратегия, причём

—Паша не может выиграть за один ход;

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

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

Задание 3. Укажите значение S, при котором

— у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;

—у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вовы.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.

Решение

Пусть S —исходное количество камней в куче.

Задание 1. a) Паша может выиграть первым ходом, если S ∈ {16, 17, . . . , 28}.

Во всех случаях ему нужно удвоить количество камней в куче. Если количество камней в куче меньше 16, то за один ход нельзя получить кучу, в которой больше 30 камней.

б) Вова может выиграть первым ходом (как бы ни играл Паша), если исходно в куче будет S = 14 камней. Тогда после первого хода Паши в куче будет или 16 камней, или 28 камней. В любом случае Вове достаточно удвоить количество камней и выиграть своим первым ходом.

Задание 2. Возможные значения S: 12 и 7. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу с 12 камнями 2 камня или удвоив кучу из 7 камней, он может получить кучу из 14 камней. Эта позиция разобрана в п. 1б.

Если в куче 14 камней, то игрок, который будет ходить (теперь это Вова), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.

Задание 3. Возможное значение S: 10.После первого хода Паши в куче будет или 12 камней, или 20 камней. Если в куче станет 20 камней, Вова удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 12 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Вова), выигрывает своим вторым ходом. В таблице изображено дерево возможных партий при описанной стратегии Вовы. Заключительные позиции (в них выигрывает Вова) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Паши
(разобраны все ходы)
1-й ход Вовы
(только ход по стратегии)
2-й ход Паши
(разобраны все ходы)
2-й ход Вовы
(только ход по стратегии)
10 10 + 2 = 12 12 + 2 = 14 14 + 2 = 16 16 · 2 = 32
14 · 2 = 28 28 · 2 = 56
10 · 2 = 20 20 · 2 = 40    
Ответ:
Показать решение

Задача 6

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 8 камней, за один ход можно получить кучу из 9 или 24 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 109. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 109 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 108.

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

Выполните следующие задания. Во всех случаях обоснуйте свой ответ. Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрышный ход для каждого указанного значения S.

б) Укажите такое значение S, при котором Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.

Задание 2. Укажите два таких значения S, при которых у Коли есть выигрышная стратегия, причём

—Коля не может выиграть за один ход;

—Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.

Для каждого указанного значения S опишите выигрышную стратегию Коли.

Задание 3. Укажите значение S, при котором

— у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

—у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Саши.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Саши (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.

Решение

Пусть S —исходное количество камней в куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {37, 38, . . . , 108}.

Для S ∈ {37, 38, . . . , 107} ему нужно утроить количество камней в куче. Для S = 108 он может либо добавить 1 камень, либо утроить количество камней. Если количество камней в куче меньше 37, то за один ход нельзя получить кучу, в которой больше 108 камней.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно в куче будет S = 36 камней. Тогда после первого хода Коли в куче будет или 37 камней, или 108 камней. В любом случае Саше достаточно утроить количество камней и выиграть своим первым ходом.

Задание 2. Возможные значения S: 12 и 35. В этих случаях Коля, очевидно, не может выиграть первым ходом. Однако, добавив в кучу с 35 камнями 1 камень или утроив кучу из 12 камней, он может получить кучу из 36 камней. Эта позиция разобрана в п. 1б. Если в куче 36 камней, то игрок, который будет ходить (теперь это Саша), выиграть не может, а его противник (то есть Коля) следующим ходом выиграет.

Задание 3. Возможное значение S: 34. После первого хода Коли в куче будет или 35 камней, или 102 камня. Если в куче станет 102 камня, Саша утроит количество камней и выиграет первым ходом. Ситуация, когда в куче 35 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Саша), выигрывает своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
34 34 + 1 = 35 35 + 1 = 36 36 + 1 = 37 37 · 3 = 111
36 · 3 = 108 108 + 1 = 109
34 · 3 = 102 102 · 3 = 306    
Ответ:
Показать решение

Задача 7

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза.Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 40.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрышный ход для каждого указанного значения S.

б) Укажите такое значение S, при котором Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.

Задание 2. Укажите два таких значения S, при которых у Коли есть выигрышная стратегия, причём

– Коля не может выиграть за один ход;

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

Задание 3. Укажите значение S, при котором

– у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

– у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Решение

Пусть S —исходное количество камней в куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {21, 22, . . . , 40}. Для S ∈ {21, 22, . . . , 38} ему нужно удвоить количество камней в куче. Для S = 39 он может либо добавить 2 камня, либо удвоить количество камней. Для S = 40 Коля может добавить 1 или 2 камня, или удвоить количество камней. Если количество камней в куче меньше 21, то за один ход нельзя получить кучу, в которой больше 40 камней.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно в куче будет S = 20 камней. Тогда после первого хода Коли в куче будет или 21 камень, или 22 камня, или 40 камней. В любом случае Саше достаточно удвоить количество камней и выиграть своим первым ходом.

Задание 2. Возможные значения S: 19 и 18. В этих случаях Коля, очевидно, не может выиграть первым ходом.Однако, добавив в кучу 1 или 2 камня, он может получить кучу из 20 камней. Эта позиция разобрана в п. 1б). Если в куче 20 камней, то игрок, который будет ходить (теперь это Саша), выиграть не может, а его противник (то есть Коля) следующим ходом выиграет.

Задание 3. Возможное значение S: 17.После первого хода Коли камней в куче будет или 18, или 19, или 34. Если в куче станет 34 камня, Саша удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 18 или 19 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Саша), выигрывает своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
17 17 + 1 = 18 18 + 2 = 20 20 + 1 = 21 21 · 2 = 42
  20 + 2 = 22 22 · 2 = 44
20 · 2 = 40 40 · 2 = 80
17 + 2 = 19 19 + 1 = 20 20 + 1 = 21 21 · 2 = 42
20 + 2 = 22 22 · 2 = 44
20 · 2 = 40 40 · 2 = 80
17 · 2 = 34 34 · 2 = 68    
Ответ:
Показать решение

Задача 8

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 23.Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 23 или больше камней. В начальный момент в куче было S камней, 1 6 S 6 22.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрышный ход для каждого указанного значения S. б) Укажите такое значение S, при котором Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.

Задание 2. Укажите два таких значения S, при которых у Коли есть выигрышная стратегия, причём

—Коля не может выиграть за один ход;

—Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.

Для каждого указанного значения S опишите выигрышную стратегию Коли.

Задание 3. Укажите значение S, при котором

— у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

—у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Решение

Пусть S —исходное количество камней в куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {12, 14, . . . , 22}.

Для S ∈ {13, 14, . . . , 20} ему нужно удвоить количество камней в куче. Для S = 21 он может либо добавить 2 камня, либо удвоить количество камней. Для S = 22 Коля может добавить 1 или 2 камня или удвоить количество камней.

Если количество камней в куче меньше 11, то за один ход нельзя получить кучу, в которой больше 22 камней.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно в куче будет S = 11 камней. Тогда после первого хода Коли в куче будет или 12 камней, или 13 камней, или 22 камня. В любом случае Саше достаточно удвоить количество камней и выиграть своим первым ходом.

Задание 2. Возможные значения S: 10 и 9. В этих случаях Коля, очевидно, не может выиграть первым ходом. Однако, добавив в кучу 1 или 2 камня, он может получить кучу из 11 камней. Эта позиция разобрана в п. 1б. Если в куче 11 камней, то игрок, который будет ходить (теперь это Саша), выиграть не может, а его противник (то есть Коля) следующим ходом выиграет.

Задание 3. Возможное значение S: 8. После первого хода Коли в куче будет или 9, или 10, или 16 камней. Если в куче станет 16 камней, Саша удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 10 или 9 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Саша), выигрывает своим вторым ходом. В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
8 8 + 1 = 9 9 + 2 = 11 11 + 1 = 12 12 · 2 = 24
  11 + 2 = 13 13 · 2 = 26
11 · 2 = 22 22 · 2 = 44
8 + 2 = 10 10 + 1 = 11 11 + 1 = 12 12 · 2 = 24
11 + 2 = 13 13 · 2 = 26
11 · 2 = 22 22 · 2 = 44
8 · 2 = 16 16 · 2 = 32    
Ответ:
Показать решение

Задача 9

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче 15 камней, а в другой—20 камней; такую позицию будем обозначать (15, 20). Тогда за один ход можно получить любую из четырёх позиций (17, 20), (15, 22), (30, 20), (15, 40).У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (54, 3), (40, 30), (50, 15) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно удвоить количество камней в первой куче.

Выполните следующие задания.

Задание 1. Для каждой из начальных позиций (15, 47), (44, 20) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2.Для каждой из начальных позиций (15, 45), (13, 47), (42, 20) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (13, 45) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

Решение

Задание 1. Если начальными являются позиции (15, 47), (44, 20), то выигрывает Саша своим первым ходом.

Если начальная позиция (15, 47), то после первого хода Коли может получиться одна из четырёх позиций: (17, 47) — всего 64, (30, 47) — всего 77, (15, 49) — всего 64, (15, 94) — всего 109. В каждом из полученных случаев суммарное число камней не превышает 110. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (17, 94), (30, 94), (15, 98), (15, 188).

В каждом случае суммарное число камней не менее 110. Следовательно, Саша выигрывает своим первым ходом.

Если начальная позиция (44, 20), то после первого хода Коли может получиться одна из четырёх позиций: (46, 20) — всего 66, (44, 22) — всего 66, (88, 20) — всего 108, (44, 40) — всего 84. В каждом из полученных случаев суммарное число камней не превышает 110. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней в первой куче, получит соответственно позиции (92, 20), (88, 22), (176, 20), (88, 40). В каждом случае суммарное число камней не менее 110. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Если начальными являются позиции (15, 45), (13, 47), (42, 20), то выигрывает Коля своим вторым ходом.

Если начальной является одна из позиций (15, 45) или (13, 47), то, чтобы выиграть, Коля должен после своего хода получить позицию (15, 47). Для этого он должен увеличить на 2 число камней либо во второй куче (для позиции (15, 45)), либо в первой (для позиции (13, 47)).Считая позицию (15, 47) начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом.

Если начальная позиция (42, 20), то, чтобы выиграть, Коля должен увеличить в первой куче число камней на 2. Тогда после его хода получится позиция (44, 20). Считая эту позицию начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом.

Задание 3. Если начальной является позиция (13, 45), то выигрывает Саша не более чем за два хода. После первого хода Коли из начальной позиции (13, 45) можно получить одну из следующих: (15, 45), (26, 45), (13, 47), (13, 90).

Если на начало хода Саши будет одна из позиций (15, 45), (13, 47), то он выиграет своим вторым ходом. Эти позиции, как начальные, были рассмотрены в задании 2. Если на начало хода Саши будет позиция (26, 45), то Саша, удвоив число камней во второй куче, получит позицию (26, 90) (здесь суммарное число камней 116) и выиграет.

Если на начало хода Саши будет позиция (13, 90), то Саша, удвоив число камней во второй куче, получит позицию (13, 180) (здесь суммарное число камней 193 > 110) и также выиграет. Таблица выигрышных стратегий для позиции (13, 45). Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(13, 45) (15, 45) (15, 47) (17, 47) (17, 94)
  (15, 49) (15, 98)
(30, 47) (30, 94)
(15, 94) (15, 188)
(13, 47) (15, 47) (17, 47) (123, 29)
(15, 49) (360, 29)
(30, 47) (120, 30)
(15, 94) (120, 87)
(26, 45) (26, 90)    
(13, 90) (13, 180)    
Ответ:
Показать решение

Задача 10

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче 15 камней, а в другой—20 камней; такую позицию будем обозначать (15, 20). Тогда за один ход можно получить любую из четырёх позиций (17, 20), (15, 22), (30, 20), (15, 40).У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в кучах становится не менее 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах всего будет 100 камней или больше. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50, 3), (35, 30), (40, 25) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно удвоить количество камней в первой куче.

Выполните следующие задания.

Задание 1. Для каждой из начальных позиций (10, 44), (20, 39) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (10, 42), (8, 44), (20, 37) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (8, 42) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

Решение

Задание 1. Если начальными являются позиции (10, 44), (20, 39), то выигрывает Саша своим первым ходом.

Если начальная позиция (10, 44), то после первого хода Коли может получиться одна из четырёх позиций: (12, 44) — всего 56, (20, 44) — всего 64, (10, 46) — всего 56, (10, 88) — всего 98.

В каждом из полученных случаев суммарное число камней не превышает 100. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (12, 88), (20, 88), (10, 92), (10, 176).

В каждом случае суммарное число камней не менее 100. Следовательно, Саша выигрывает своим первым ходом.

Если начальная позиция (20, 39), то после первого хода Коли может получиться одна из четырёх позиций: (22, 39) — всего 61, (40, 39) — всего 79, (20, 41) — всего 61, (20, 78) — всего 98.

В каждом из полученных случаев суммарное число камней не превышает 100. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (22, 78), (40, 78), (20, 82), (20, 156). В каждом случае суммарное число камней не менее 100. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Если начальными являются позиции (10, 42), (8, 44), (20, 37), то выигрывает Коля своим вторым ходом.

Если начальной является одна из позиций (10, 42) или (8, 44), то, чтобы выиграть, Коля должен после своего хода получить позицию (10, 44). Для этого он должен увеличить на 2 число камней либо во второй куче (для позиции (10, 42)), либо в первой (для позиции (8, 44)). Считая позицию (10, 44) начальной, мы приходим к рассмотрению ситуации задания 1.

Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом. Если начальная позиция (20, 37), то, чтобы выиграть, Коля должен увеличить во второй куче число камней на 2. Тогда после его хода получится позиция (20, 39). Считая эту позицию начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым.

Значит, выиграет Коля своим вторым ходом.

Задание 3. Если начальной является позиция (8, 42), то выигрывает Саша не более чем за два хода. После первого хода Коли из начальной позиции (8, 42) можно получить одну из следующих: (10, 42), (16, 42), (8, 44), (8, 84).

Если на начало хода Саши будет одна из позиций (10, 42), (8, 44), то он выиграет своим вторым ходом. Эти позиции, как начальные, были рассмотрены в задании 2. Если на начало хода Саши будет позиция (16, 42), то Саша, удвоив число камней во второй куче, получит позицию (16, 84) (здесь суммарное число камней 100) и выиграет.

Если на начало хода Саши будет позиция (8, 84), то Саша, удвоив число камней во второй куче, получит позицию (8, 168) (здесь суммарное число камней 176 > 100) и также выиграет.

Таблица выигрышных стратегий для позиции (8, 42). Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(8, 42) (10, 42) (10, 44) (12, 44) (12, 88)
  (20, 44) (20, 88)
(10, 46) (10, 92)
(10, 88) (10, 176)
(8, 44) (10, 44) (12, 44) (123, 29)
(20, 44) (360, 29)
(10, 46) (120, 30)
(10, 88) (120, 87)
(16, 42) (16, 84)    
(8, 84) (8, 168)    
Ответ:
Показать решение

Задача 11

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один или увеличить количество камней в куче в три раза. Например, пусть в одной куче 15 камней, а в другой 20 камней; такую позицию будем обозначать (15, 20). Тогда за один ход можно получить любую из четырёх позиций (16, 20), (15, 21), (45, 20), (15, 60). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в кучах становится не менее 150. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, когда в кучах всего будет 150 камней или больше. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50, 3), (40, 30), (48, 10) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно утроить количество камней в первой куче.

Выполните следующие задания.

Задание 1. Для каждой из начальных позиций (40, 29), (20, 43) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (40, 28), (39, 29), (20, 42) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (39, 28) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

Решение

Задание 1. Если начальными являются позиции (40, 29), (20, 43), то выигрывает Саша своим первым ходом.

Если начальная позиция (40, 29), то после первого хода Коли может получиться одна из четырёх позиций: (41, 29)—всего 70, (120, 29) — всего 149, (40, 30) — всего 70, (40, 87) — всего 127. В каждом из полученных случаев суммарное число камней не превышает 150. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней в первой куче, получит соответственно позиции (123, 29), (360, 29), (120, 30), (120, 87). В каждом случае суммарное число камней не менее 150. Следовательно, Саша выигрывает своим первым ходом.

Если начальная позиция (20, 43), то после первого хода Коли может получиться одна из четырёх позиций: (21, 43) — всего 64, (60, 43)—всего 103, (20, 44)—всего 64, (20, 129)—всего 149.В каждом из полученных случаев суммарное число камней не превышает 150. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней во второй куче, получит соответственно позиции (21, 129), (60, 129), (20, 132), (20, 387). В каждом случае суммарное число камней не менее 150. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Если начальными являются позиции (40, 28), (39, 29), (20, 42), то выигрывает Коля своим вторым ходом.

Если начальной является одна из позиций (40, 28) или (39, 29), то, чтобы выиграть, Коля должен после своего хода получить позицию (40, 29). Для этого он должен увеличить на 1 число камней либо во второй куче (для позиции (40, 28)), либо в первой (для позиции (39, 29)).

Считая позицию (40, 29) начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом.

Если начальная позиция (20, 42), то, чтобы выиграть, Коля должен увеличить во второй куче число камней на 1. Тогда после его хода получится позиция (20, 43). Считая эту позицию начальной, мы приходим к рассмотрению ситуации задания 1.

Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым.

Значит, выиграет Коля своим вторым ходом.

Задание 3. Если начальной является позиция (39, 28), то выигрывает Саша не более чем за два хода. После первого хода Коли из начальной позиции (39, 28) можно получить одну из следующих: (40, 28), (117, 28), (39, 29), (39, 84).

Если на начало хода Саши будет одна из позиций (40, 28), (39, 29), то он выиграет своим вторым ходом. Эти позиции, как начальные, были рассмотрены в задании 2. Если на начало хода Саши будет позиция (117, 28), то Саша, утроив число камней во второй куче, получит позицию (117, 84) (здесь суммарное число камней 201 > 150) и выиграет.

Если на начало хода Саши будет позиция (39, 84), то Саша, утроив число камней во второй куче, получит позицию (39, 252) (здесь суммарное число камней 291 > 150) и также выиграет. Таблица выигрышных стратегий для позиции (39, 28). Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(39, 28) (40, 28) (40, 29) (41, 29) (123, 29)
  (120, 29) (360, 29)
(40, 30) (120, 30)
(40, 87) (120, 87)
(39, 29) (40, 29) (41, 29) (123, 29)
(120, 29) (360, 29)
(40, 30) (120, 30)
(40, 87) (120, 87)
(39, 84) (39, 252)    
(117, 28) (117, 84)    
Ответ:
Показать решение

Задача 12

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

Например, пусть в одной куче 15 камней, а в другой— 20 камней; такую позицию будем обозначать (15, 20). Тогда за один ход можно получить любую из четырёх позиций (16, 20), (15, 21), (45, 20), (15, 60). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в кучах становится не менее 120. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, когда в кучах всего будет 120 камней или больше.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50, 3), (35, 15), (40, 10) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно утроить количество камней в первой куче.

Выполните следующие задания.

Задание 1. Для каждой из начальных позиций (5, 38), (20, 33) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (5, 37), (4, 38), (20, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (4, 37) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

Решение

Задание 1. Если начальными являются позиции (5, 38), (20, 33), то выигрывает Саша своим первым ходом.

Если начальная позиция (5, 38), то после первого хода Коли может получиться одна из четырёх позиций: (6, 38) — всего 44, (15, 38) — всего 53, (5, 39) — всего 64, (5, 114) — всего 119. В каждом из полученных случаев суммарное число камней не превышает 120. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней во второй куче, получит соответственно позиции (6, 114), (15, 114), (5, 117), (5, 342). В каждом случае суммарное число камней не менее 120. Следовательно, Саша выигрывает своим первым ходом.

Если начальная позиция (20, 33), то после первого хода Коли может получиться одна из четырёх позиций: (21, 33) — всего 54, (60, 33) — всего 93, (20, 34) — всего 54, (20, 99) — всего 119. В каждом из полученных случаев суммарное число камней не превышает 120. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней во второй куче, получит соответственно позиции (21, 99), (60, 99), (20, 102), (20, 297). В каждом случае суммарное число камней не менее 120. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Если начальными являются позиции (5, 37), (4, 38), (20, 32), то выигрывает Коля своим вторым ходом.

Если начальной является одна из позиций (5, 37) или (4, 38), то, чтобы выиграть, Коля должен после своего хода получить позицию (5, 38). Для этого он должен увеличить на 1 число камней либо во второй куче (для позиции (5, 37)), либо в первой (для позиции (4, 38)). Считая позицию (5, 38) начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом.

Если начальная позиция (20, 32), то, чтобы выиграть, Коля должен увеличить во второй куче число камней на 1. Тогда после его хода получится позиция (20, 33). Считая эту позицию начальной, мы приходим к рассмотрению ситуации задания 1.

Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым.

Значит, выиграет Коля своим вторым ходом.

Задание 3. Если начальной является позиция (4, 37), то выигрывает Саша не более чем за два хода.

После первого хода Коли из начальной позиции (4, 37) можно получить одну из следующих: (5, 37), (4, 38), (12, 37), (4, 111). Если на начало хода Саши будет одна из позиций (5, 37), (4, 38), то он выиграет своим вторым ходом. Эти позиции, как начальные, были рассмотрены в задании 2. Если на начало хода Саши будет позиция (12, 37), то Саша, утроив число камней во второй куче, получит позицию (12, 111) (здесь суммарное число камней 123 > 120) и выиграет.

Если на начало хода Саши будет позиция (4, 111), то Саша, утроив число камней во второй куче, получит позицию (4, 333) (здесь суммарное число камней 337 > 120) и также выиграет. Таблица выигрышных стратегий для позиции (4, 37). Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(4, 37) (5, 37) (5, 38) (6, 38) (6, 114)
  (15, 38) (15, 114)
(5, 39) (5, 117)
(5, 114) (5, 342)
(4, 38) (5, 38) (6, 38) (6, 114)
(15, 38) (15, 114)
(5, 114) (5, 342)
(5, 114) (5, 342)
(12, 37) (12, 111)    
(4, 111) (4, 333)    
Ответ:
Показать решение

Задача 13

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. В начальный момент времени в куче находилось 1 ≤ S ≤ 53 камней. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Игра завершается, когда в куче становится не менее 54 камней. При этом если в куче будет не более 84 камней, то побеждает тот игрок, который сделал последний ход, в противном случае побеждает его соперник.

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

Выполните следующие задания.

Задание 1. а) Найдите все значения S, при которых Коля может выиграть первым ходом. Укажите все такие значения и соответствующие ходы Коли.

б) Определите, кто из игроков имеет выигрышную стратегию при S = 50, S = 51, S = 52. Опишите выигрышные стратегии для этих случаев.

Задание 2. Определите, кто из игроков имеет выигрышную стратегию при S = 16, S = 48. Опишите соответствующие выигрышные стратегии.

Задание 3. Определите, кто из игроков имеет выигрышную стратегию при S = 14. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах—количество камней в позиции.

Решение

Задание 1. а) Коля может выиграть первым ходом, если S ∈ {18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 53}.

Для S ∈ {18, 19, . . . , 28} ему нужно утроить количество камней. Для S = 53—добавить один камень.

Если количество камней меньше 18 или больше 28, то за один ход Коля выиграть не может.

б) При S = 52 выигрывает Саша (второй игрок) своим первым ходом. Если Коля утроит число камней, то в куче станет 156 (= 52 · 3) камней. Так как 156 > 84, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 53 камня. В этом случае Саша (второй игрок), добавив один камень, получит 54 камня и выиграет своим первым ходом.

При S = 51 выиграет Коля (первый игрок) своим вторым ходом. Для выигрыша Коле следует добавить в кучу один камень.

Тогда в куче станет 52 камня. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Коля.

При S = 50 выиграет Саша (второй игрок) своим вторым ходом. Если Коля утроит число камней, то в куче станет 150 (= 50 · 3) камней. Так как 150 > 84, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 51 камень. Как показано выше, в этом случае выиграет тот из игроков, который ходит первым, то есть Саша.

Задание 2. Если S = 48, то выигрывает Саша (второй игрок).

Если Коля утроит число камней, то в куче станет 144 (= 48 · 3) камня. Так как 144 > 84, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 49 камней. Саша, добавив в кучу один камень, получит 50 камней. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Саша.

Если S = 16, то выигрывает Коля (первый игрок). Если Коля утроит число камней, то в куче станет 48 (= 16 · 3) камней. Как показано выше, в этом случае выигрывает тот из игроков, который делает ход вторым, то есть Коля.

Задание 3. Если S = 14, то выигрывает Коля (первый игрок).

На рисунке представлено дерево выигрышных стратегий для S = 14. Заключительные позиции (в них выигрывает Коля) указаны жирным шрифтом. Дерево содержит только выигрышные ходы для Коли и все ходы Саши.

Ответ:
Показать решение

Задача 14

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. В начальный момент времени в куче находилось 1 ≤ S ≤ 44 камней. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Игра завершается, когда в куче становится не менее 46 камней. При этом если в куче будет не более 68 камней, то побеждает тот игрок, который сделал последний ход, в противном случае побеждает другой игрок.

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

Выполните следующие задания.

Задание 1. а) Найдите все значения S, при которых Коля может выиграть первым ходом. Укажите все такие значения и соответствующие ходы Коли.

б) Определите, кто из игроков имеет выигрышную стратегию при S = 42, S = 40, S = 38. Опишите выигрышные стратегии для этих случаев.

Задание 2. Определите, кто из игроков имеет выигрышную стратегию при S = 21, S = 19. Опишите соответствующие выигрышные стратегии.

Задание 3. Определите, кто из игроков имеет выигрышную стратегию при S = 17. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах—количество камней в позиции.

Решение

Задание 1. а) Коля может выиграть первым ходом, если S ∈ {23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 44}.

Для S ∈ {23, 24, . . . , 34} ему нужно удвоить количество камней. Для S = 44—добавить два камня.

Для других значений S Коля либо наберёт менее 46 камней, либо наберёт более 68 камней.

б) При S = 42 выигрывает Саша (второй игрок) своим первым ходом. Если Коля удвоит число камней, то в куче станет 84 (= 42 ∗ 2) камня. Так как 84 > 68, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу два камня, то в куче станет 44 камня. В этом случае Саша (второй игрок), добавив два камня, получит 46 камней и выиграет своим первым ходом.

При S = 40 выиграет Коля (первый игрок) своим вторым ходом. Для выигрыша Коле следует первым ходом добавить в кучу два камня. Тогда в куче станет 42 камня. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Коля.

При S = 38 выиграет Саша (второй игрок) своим вторым ходом.

Если Коля удвоит число камней, то в куче станет 76 (= 38 · 2) камней. Так как 76 > 68, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу два камня, то в куче станет 40 камней. Как показано выше, в этом случае выиграет тот из игроков, который ходит первым, то есть Саша.

Задание 2. Если S = 21, то выигрывает Коля (первый игрок).

Для этого ему следует удвоить число камней, тогда в куче станет 42 (= 21 ∗ 2) камня. Стратегия игры для данной позиции была рассмотрена в задании 1.

Если S = 19, то выигрывает Коля (первый игрок). Для выигрыша Коле следует первым ходом удвоить число камней. Тогда в куче станет 38 камней. Как показано выше, в этом случае выигрывает тот из игроков, который делает ход вторым, то есть Коля.

Задание 3. Если S = 17, то выигрывает Саша (второй игрок).

Первым ходом Коля может получить либо 19 (= 17 + 2) камней, либо 34 (= 17 · 2) камня. В случае если он получит 19 камней, то Саша выиграет либо вторым, либо третьим ходом, что следует из задания 2. В случае, если Коля получит 34 камня, то Саша выиграет первым ходом, удвоив количество камней в куче.

Таблица выигрышных стратегий для S = 17. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

  К С К С К С
S = 17 19 38 40 42 44 46 победа
84 победа
76 победа    
34 68 победа        
Ответ:
Показать решение

Задача 15

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. В начальный момент времени в куче находилось 1 ≤ S ≤ 37 камней.

За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается, когда в куче становится не менее 38 камней. При этом если в куче было не более 66 камней, то побеждает тот игрок, который сделал последний ход, в противном случае побеждает его соперник.

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

Выполните следующие задания.

Задание 1. а) Найдите все значения S, при которых Коля может выиграть первым ходом. Укажите все такие значения и соответствующие ходы Коли.

б) Определите, кто из игроков имеет выигрышную стратегию при S = 36, S = 35, S = 34. Опишите выигрышные стратегии для этих случаев.

Задание 2. Определите, кто из игроков имеет выигрышную стратегию при S = 18, S = 17. Опишите соответствующие выигрышные стратегии.

Задание 3. Определите, кто из игроков имеет выигрышную стратегию при S = 16. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах—количество камней в позиции.

Решение

Задание 1. а) Коля может выиграть первым ходом, если S ∈ {19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 37}. Для S ∈ {19, 20, . . . , 33} ему нужно удвоить количество камней. Для S = 37—добавить один камень.

Для других значений S Коля либо наберёт менее 38 камней, либо наберёт более 66 камней.

б) При S = 36 выигрывает Саша (второй игрок) своим первым ходом. Если Коля удвоит число камней, то в куче станет 72 (= 36 ∗ 2) камня. Так как 72 > 66, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 37 камней. В этом случае Саша (второй игрок), добавив один камень, получит 38 камней и выиграет своим первым ходом.

При S = 35 выиграет Коля (первый игрок) своим вторым ходом. Для выигрыша Коле следует первым ходом добавить в кучу один камень. Тогда в куче станет 36 камней. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Коля.

При S = 34 выиграет Саша (второй игрок) своим вторым ходом. Если Коля удвоит число камней, то в куче станет 68 (= 34 ∗ 2) камней. Так как 68 > 66, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 35 камней. Как показано выше, в этом случае выиграет тот из игроков, который ходит первым, то есть Саша.

Задание 2. Если S = 18, то выигрывает Коля (первый игрок). Для этого ему следует удвоить число камней, тогда в куче станет 36 (= 18 ∗ 2) камней. Стратегия игры для данной позиции была рассмотрена в задании 1.

Если S = 17, то выигрывает Коля (первый игрок). Для выигрыша Коле следует первым ходом удвоить число камней. Тогда в куче станет 34 камня. Как показано выше, в этом случае выигрывает тот из игроков, который делает ход вторым, то есть Коля.

Задание 3. Если S = 16, то выигрывает Саша (второй игрок). Первым ходом Коля может получить либо 17 (= 16+1) камней, либо 32 (= 16·2) камня. В случае если он получит 17 камней, то Саша выиграет либо вторым, либо третьим ходом, что следует из задания 2. В случае если Коля получит 32 камня, то Саша выиграет первым ходом, удвоив количество камней в куче.

Таблица выигрышных стратегий для S = 16. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

  К С К С К С
S = 16 17 34 35 36 37 38 победа
72 победа
68 победа    
32 64 победа        
Ответ:
Показать решение

Задача 16

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. В начальный момент времени в куче находилось 1 ≤ S ≤ 33 камней. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается, когда в куче становится не менее 34 камней. При этом если в куче будет не более 58 камней, то побеждает тот игрок, который сделал последний ход, в противном случае побеждает его соперник.

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

Выполните следующие задания.

Задание 1. а) Найдите все значения S, при которых Коля может выиграть первым ходом. Укажите все такие значения и соответствующие ходы Коли.

б) Определите, кто из игроков имеет выигрышную стратегию при S = 30, S = 31, S = 32. Опишите выигрышные стратегии для этих случаев.

Задание 2. Определите, кто из игроков имеет выигрышную стратегию при S = 13, S = 14. Опишите соответствующие выигрышные стратегии.

Задание 3. Определите, кто из игроков имеет выигрышную стратегию при S = 11. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах—количество камней в позиции.

Решение

Задание 1. а) Коля может выиграть первым ходом, если S ∈ {17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 33}.

Для S ∈ {17, 18, . . . , 29} ему нужно удвоить количество камней. Для S = 33—добавить один камень.

Если количество камней меньше 17 или больше 29, то за один ход Коля выиграть не может.

б) При S = 32 выигрывает Саша (второй игрок) своим первым ходом. Если Коля удвоит число камней, то в куче станет 64 (= 32 ∗ 2) камня. Так как 64 > 58, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 33 камня. В этом случае Саша (второй игрок), добавив один камень, получит 34 камня и выиграет своим первым ходом.

При S = 31 выиграет Коля (первый игрок) своим вторым ходом. Для выигрыша Коле следует первым ходом добавить в кучу один камень. Тогда в куче станет 32 камня. Как показано выше, в этом случае выиграет тот из игроков, который ходит вторым, то есть Коля.

При S = 30 выиграет Саша (второй игрок) своим вторым ходом. Если Коля удвоит число камней, то в куче станет 60 (= 30 ∗ 2) камней. Так как 60 > 58, то победит игрок, не сделавший последний ход, то есть Саша. Если Коля добавит в кучу один камень, то в куче станет 31 камень. Как показано выше, в этом случае выиграет тот из игроков, который ходит первым, то есть Саша.

Задание 2. Если S = 14, то выигрывает Саша (второй игрок).

Если Коля удвоит число камней, то в куче станет 28 (= 14 ∗ 2) камней. В этом случае Саша (второй игрок), удвоив число камней, получит 56 камней, и выиграет своим первым ходом. Если Коля добавит в кучу один камень, то в куче станет 15 камней.

Саша (второй игрок), удвоив число камней, получит 30 камней.

Как показано выше (см. задание 1), в этом случае выиграет тот из игроков, который ходит вторым, то есть Саша.

Если S = 13, то выигрывает Коля (первый игрок). Для выигрыша Коле следует первым ходом добавить в кучу один камень.

Тогда в куче станет 14 камней. Как показано выше, в этом случае выигрывает тот из игроков, который делает ход вторым, то есть Коля.

Задание 3. Если S = 11, то выигрывает Коля (первый игрок). На рисунке представлено дерево выигрышных стратегий для S = 14. Заключительные позиции (в них выигрывает Коля) указаны жирным шрифтом. Дерево содержит только выигрышные ходы для Коли и все ходы Саши.

Ответ:
Показать решение

Задача 17

Два игрока, Коля и Саша, играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Коля. Выигрывает тот, кто первый составит слово из заданного набора.

Пример. Пусть заданы слова КОТ, КЛОН, ЛЕТО, ЛЕВ. На первом ходуКоля может написать букву К илиЛ.Пусть он написал букву К. В ответ Саша может написатьОили Л. В первом случае получается КО, и Коля, дописав букву Т, получает слово КОТ из заданного набора и выигрывает. Во втором случае получается КЛ, Коля должен дописать О и Саша выиграет вторым ходом, дописав Н и получив слово КЛОН.

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

Выполните следующие три задания.

Задание 1. Определите, у кого из игроков есть выигрышная стратегия для набора слов РАДИУС, РУЧЕЙ.Опишите эту стратегию.Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 2. В наборе слов, приведённом в задании 1, поменяйте местами две буквы в любом слове так, чтобы выигрышная стратегия была у другого игрока. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 3. Дан набор слов ДЕКАБРЬ, ДЕКАДА, ДЕЛЕГАТ, ОБЛАСТЬ, ОТВАГА, ОТКОС. У кого из игроков есть выигрышная стратегия? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.

Решение

Задание 1. Для набора слов РАДИУС, РУЧЕЙ выигрышная стратегия есть у Саши.

Первый ход делает Коля, записывая единственно возможную букву Р. Второй игрок — Саша, своим первым ходом он пишет букву А. Далее в результате следующих ходов игроков будет получено слово РАДИУС. Так как количество букв в этом слове чётно, то выиграет Саша—второй игрок.

В заданных словах вторые буквы разные. При этом в одном слове чётное число букв, а в другом—нечётное.Поэтому стратегия Саши, второго игрока, заключается в том, что он должен своим первым ходом записать букву того слова, в котором количество букв чётно. Тогда своим последним ходом он допишет последнюю букву этого слова. Для предложенных в задании слов Саша должен записать букву А.

Задание 2. Для набора слов, указанных в задании 1а, выигрывает Саша (второй игрок). Чтобы выиграл Коля, первый игрок, в словах, начиная с какого-либо нечётного места, буквы должны различаться. Так как одно из слов содержит чётное количество букв, а другое нечётное, то у Коли будет возможность записать букву, после которой игроки будут записывать только буквы слова, состоящего из нечётного количества букв. Для заданных слов РАДИУС, РУЧЕЙ это возможно, если в слове РАДИУС поменять местами буквы А и У. В этом случае исходными будут слова РУДИАС, РУЧЕЙ.

При указанной стратегии возможна только одна партия.

В результате этой партии получится слово РАДИУС.

Задание 3. Для набора слов выигрышная стратегия есть у Коли—первого игрока.

Ниже представлена таблица выигрышных стратегий Коли.

В таблице показаны все ходы Саши и только выигрышные ходы Коли. Заключительные позиции (в них выигрывает Коля) подчёркнуты.

Стратегия Коли заключается в том, что он должен своим вторым ходом дописать к У букву Ч.

При указанной стратегии возможна только одна партия. В результате этой партии получится слово РУЧЕЙ.

Коля Д О
Саша ДЕ ОБ ОТ
Коля ДЕК ДЕЛ ОБЛ ОТК
Саша ДЕКА ДЕЛЕ ОБЛА ОТКО
Коля ДЕКАБ ДЕЛЕГ ОБЛАС ОТКОС
Саша ДЕКАБР ДЕЛЕГА ОБЛАСТ -
Коля ДЕКАБРЬ ДЕЛЕГАТ ОБЛАСТЬ -
Ответ:
Показать решение

Задача 18

Два игрока, Коля и Саша, играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Коля. Выигрывает тот, кто первый составит слово из заданного набора.

Пример. Пусть заданы слова КОТ, КЛОН, ЛЕТО, ЛЕВ. За первый ход Коля может написать букву К или Л. Пусть он написал букву К. В ответ Саша может написатьОили Л. В первом случае получается КО, и Коля, дописав букву Т, получает слово КОТ из заданного набора и выигрывает. Во втором случае получается КЛ, Коля должен дописать О и Саша выиграет вторым ходом, дописав Н и получив слово КЛОН.

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

Выполните следующие три задания.

Задание 1. Определите, у кого из игроков есть выигрышная стратегия для набора слов ПЛАМЯ, МАШИНА. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 2. В наборе слов, приведённом в задании 1, поменяйте местами две буквы в любом слове так, чтобы выигрышная стратегия была у другого игрока. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 3. Дан набор слов ЛАТУНЬ, ЛАТИНИЦА, ЛАТКА, РАДУГА, РАДАР, РАБОТА. У кого из игроков есть выигрышная стратегия? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.

Решение

Задание 1. Для набора слов ПЛАМЯ, МАШИНА выигрышная стратегия есть у Коли.

Своим первым ходом он пишет букву П. Далее в результате следующих ходов игроков будет получено слово ПЛАМЯ. Так как количество букв в этом слове нечётно, то выиграет Коля (первый игрок).

Заданные слова начинаются с разных букв, и в одном из слов чётное количество букв, а в другом—нечётное, поэтому стратегия Коли заключается в том, что он должен своим первым ходом записать первую букву того слова, в котором количество букв нечётно. Тогда своим последним ходом он допишет последнюю букву этого слова. Для предложенных в задании слов Коля должен записать букву В.

При указанной стратегии возможна только одна партия.

В результате этой партии получится слово ПЛАМЯ.

Задание 2. Для набора слов, указанных в задании 1а, выигрывает Коля (первый игрок). Чтобы выиграл Саша (второй игрок), слова должны начинаться с одной буквы и у Саши должна быть возможность записать букву, после которой игроки будут записывать только буквы слова, состоящего из чётного количества букв.

Для заданных слов ПЛАМЯ, МАШИНА это возможно, если в слове ПЛАМЯ поменять местами буквы П и М. В этом случае исходными будут слова МЛАПЯ,МАШИНА.

Стратегия Саши заключается в том, что он должен своим первым ходом дописать к Мбукву А.

При указанной стратегии возможна только одна партия.

В результате этой партии получится слово МАШИНА.

Задание 3. Для набора слов выигрышная стратегия есть у Саши—второго игрока.

Ниже представлена таблица выигрышных стратегий Саши.

В таблице показаны все ходы Коли и только выигрышные ходы Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

Коля Л Р
Саша ЛА РА
Коля ЛАТ РАБ РАД
Саша ЛАТУ ЛАТИ РАБО РАДУ
Коля ЛАТУН ЛАТИН РАБОТ РАДУГ
Саша ЛАТУНЬ ЛАТИНИ РАБОТА РАДУГА
Коля - ЛАТИНИЦ - -
Саша - ЛАТИНИЦА - -
Ответ:
Показать решение

Задача 19

Два игрока, Коля и Саша, играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 12, нельзя сделать фишку, на которой написано 21.

Первый ход делает Коля, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.

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

Пример партии.

Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.

Пусть первый ход Коли 21.

Саша может поставить 12, 11 или 13. Предположим, он ставит 12.Получим цепочку 21-12.

Коля может поставить 22 или 23. Предположим, он ставит 22. Получим цепочку 21-12-22.

Саша может поставить только фишку со значением 23. Получим цепочку 21-12-22-23.

Перед Колей в кучке остались только фишки 11 и 13, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Саша выиграл.

Выполните следующие три задания при исходном наборе фишек в кучке 11, 12, 13, 21, 22, 31, 33.

Задание 1. Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.

Задание 2. Пусть Коля первым ходом пошёл 33. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим третьим ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.

Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.

Решение

Задание 1. Пример кратчайшей партии: 21-12-22.

Возможны другие варианты ответа:

22-21-12;

31-13-33;

33-31-13.

Пояснение. Партия будет кратчайшей, если каждая фишка партии содержит одну и ту же цифру, которая встречается реже остальных. Ответный ход противника в случае кратчайшей партии должен быть «симметричным», если это возможно. То есть на ход фишкой «xy» ответным ходом должен быть «yx».

Задание 2. Стратегия, позволяющая выиграть своим третьим ходом, есть у Саши.

Ниже представлена таблица выигрышных стратегий Саши.

В таблице показаны все ходы Коли и только выигрышные ходы Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

Коля
1-й ход
33
33
Саша
1-й ход
31
33-31
Коля
2-й ход
32
11-13-32
13
33-31-13
12
33-31-12
Саша
2-й ход
12
33-31-11-12
-
-
22
33-31-12-22
Коля
3-й ход
21
33-31-11-12-21
22
33-31-11-12-22
-
-
21
33-31-12-22- 21
Саша
3-й ход
13
33-31-11-12-21-13
21
33-31-11-12-22-21
Игра не окончена
- 13
33-31-12-22-21-13

Пояснение. Стратегия Саши заключается в том, что он должен добавить ещё один дубль и не дать Коле поставить третий дубль; в этом случае количество фишек в партии будет чётным, что необходимо для выигрыша Саши.

Задание 3.Можно убрать фишки 22 и 33. В этом случае Коля выиграет третьим ходом. Стратегия Коли — обязательно поставить любым своим ходом фишку 11.

Пример такой партии:

Игрок Коля Саша Коля Саша Коля
Ход 12 21 11 13 31

Пояснение. После того как из исходного набора будут убраны фишки «22», «33», останется нечётное количество фишек, при этом каждая фишка содержит 1 и у каждой фишки есть «симметричная» ей, поэтому первый игрок при правильной стратегии всегда выигрывает.

Ответ:
Показать решение

Задача 20

Два игрока, Коля и Саша, играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочерёдно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 12, нельзя сделать фишку, на которой написано 21.

Первый ход делает Коля, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.

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

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

Пример партии.

Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.

Пусть первый ход Коли 21.

Саша может поставить 12, 11 или 13. Предположим, он ставит 12.Получим цепочку 21-12.

Коля может поставить 22 или 23. Предположим, он ставит 22. Получим цепочку 21-12-22.

Саша может поставить только фишку со значением 23. Получим цепочку 21-12-22-23.

Перед Колей в кучке остались только фишки 11 и 13, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Саша выиграл.

Выполните следующие три задания при исходном наборе фишек в кучке {11, 12, 13, 21, 23, 31, 32, 33}.

Задание 1. Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.

Задание 2. Пусть Коля первым ходом пошёл 11. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвёртым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.

Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.

Решение

Задание 1. Пример кратчайшей партии: 21-12-23-32.

Возможен другой вариант ответа: 23-32-21-12.

Пояснение: партия будет кратчайшей, если первый игрок начнёт игру с фишки, первая цифра которой встречается реже первых цифр остальных фишек, и, если это возможно, партия не содержит «дублей» — фишек вида «xx». Ответный ход противника, в случае кратчайшей партии, должен быть «симметричным», если это возможно. То есть на ход фишкой «xy» ответным ходом должен быть «yx», если это возможно.

Задание 2. Стратегия, позволяющая выиграть своим четвёртым ходом, есть у Коли.

Ниже представлена таблица выигрышных стратегий Коли. В таблице показаны все ходы Саши и только выигрышные ходы Коли. Заключительные позиции (в них выигрывает Коля) подчёркнуты.

Коля
1-й ход
11
11
Саша
1-й ход
12
11-12
13
11-13
Коля
2-й ход
21
11-12-21
32
11-13-32
Саша
2-й ход
13
11-12-21-13
23
11-13-32-23
21
11-13-32-21
Коля
3-й ход
32
11-12-21-13-32
31
11-13-32-23-31
12
11-13-32-21-12
Саша
3-й ход
23
11-12-21-13-32- 23
12
11-13-32-23-31- 12
23
11-13-32-21-12- 23
Коля
4-й ход
31
11-12-21-13-32- 23-31
21
11-13-32-23-31- 12-21
31
11-13-32-21-12- 23-31

Пояснение. Стратегия Коли заключается в том, что он должен ставить фишки, которые не заканчиваются на 3, тем самым не давая возможность Саше сделать ход «33». Например, если после ходов 11-13-31-12 Коля поставит фишку 23, то выиграет Саша: 11-13-31-12-23-33-32-21.

Задание 3.Можно убрать фишки 11 и 33. В этом случае независимо от ходов обоих игроков Саша выиграет (или своим вторым, или своим третьим ходом).

Пример такой партии:

Игрок Коля Саша Коля Саша Коля Саша
Ход 23 31 13 32 21 12

Пояснение. После того, как из исходного набора будут убраны фишки «11», «33», останется чётное количество фишек, при этом для каждой фишки есть «симметричная» ей, поэтому второй игрок всегда выигрывает.

Ответ:
Показать решение
Показать еще

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе