26. Теория игр, выигрышная стратегия
Демонстрационный вариант Единый государственный экзамен ЕГЭ 2017 г. – задание №26 – Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Если при этом в куче оказалось не более 30 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 17 камней и Паша удвоит количество камней в куче, то игра закончится, и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 19.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
1. а) При каких значениях числа S Паша может выиграть в один ход?
Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 18, 17, 16?
Опишите выигрышные стратегии для этих случаев.
2. У кого из игроков есть выигрышная стратегия при S = 9, 8? Опишите соответствующие выигрышные стратегии.
3. У кого из игроков есть выигрышная стратегия при S = 7? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.
Решение:
| Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
|||||||||||||||||||||||||||
| 1. а) Паша может выиграть, если S = 19 или S = 10, 11, 12, 13, 14, 15. При S = 19 первым ходом нужно добавить в кучу один камень, при остальных указанных значениях S нужно удвоить количество камней. б) При S = 16, 17 или 18 удваивать количество камней не имеет смысла, так как после такого хода выигрывает противник. Поэтому можно считать, что единственный возможный ход – это добавление в кучу одного камня. При S = 18 после такого хода Паши в куче станет 19 камней. В этой позиции ходящий (т.е. Валя) выигрывает (см. п. 1а): при S = 18 Паша (игрок, который должен ходить первым) проигрывает. Выигрышная стратегия есть у Вали. При S = 17, после того как Паша своим первым ходом добавит один камень, в куче станет 18 камней. В этой позиции ходящий (т.е. Валя) проигрывает (см. выше): при S = 17 Паша (игрок, который должен ходить первым) выигрывает. Выигрышная стратегия есть у Паши. При S = 16 выигрышная стратегия есть у Вали. Действительно, если Паша первым ходом удваивает количество камней, то в куче становится 32 камня, и игра сразу заканчивается выигрышем Вали. Если Паша добавляет один камень, то в куче становится 17 камней. Как мы уже знаем, в этой позиции игрок, который должен ходить (т.е. Валя), выигрывает. Во всех случаях выигрыш достигается тем, что при своём ходе игрок, имеющий выигрышную стратегию, должен добавить в кучу один камень. Замечание для проверяющего. Скорее всего, решение экзаменуемого будет не столь подробным. Это не является ошибкой. Ученик может, например, нарисовать деревья всех возможных партий для указанных значений S. Другая возможность – (1) указать на то, что удваивать кучу не имеет смысла, и (2) последовательно сводить случай S = 18 к случаю S = 19, случай S = 17 – к случаю S = 18 и т.д. 2. При S = 9 или 8 выигрышная стратегия есть у Паши. Она состоит в том, чтобы удвоить количество камней в куче и получить кучу, в которой будет соответственно 18 или 16 камней. В обоих случаях игрок, который будет делать ход (теперь это Валя), проигрывает (п. 1б). 3. При S = 7 выигрышная стратегия есть у Вали. После первого хода Паши в куче может стать либо 8, либо 14 камней. В обеих этих позициях выигрывает игрок, который будет делать ход (теперь это Валя). Случай S = 8 рассмотрен в п. 2, случай S = 14 рассмотрен в п. 1а. В таблице изображено дерево возможных партий при описанной стратегии Вали. Заключительные позиции (в них выигрывает Валя) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы). |
|||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||
|
Рис. 1. Дерево всех партий, возможных при Валиной стратегии. Знаком >> |
|||||||||||||||||||||||||||
| Указания по оцениванию | Баллы | ||||||||||||||||||||||||||
| Предварительные замечания В задаче от ученика требуется выполнить три задания. Их трудность возрастает. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Пункт 1а считается выполненным, если правильно указаны все позиции, в которых Паша выигрывает первым ходом, и указано, каким должен быть первый ход. Пункт 1б считается выполненным, если (i) правильно указано, кто из игроков имеет выигрышную стратегию в каждой из указанных позиций, и (ii) описаны выигрышные стратегии – так, как это сделано в образце решения, или другим способом. Первое задание считается выполненным полностью, если выполнены полностью оба пункта: 1а и 1б.Замечание для проверяющего. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника (см. условие задачи). Есть два основных способа сделать это. (1) Можно построить дерево всех партий, возможных при выбранной стратегии, и убедиться, что все заключительные позиции являются выигрышными для игрока, реализующего стратегию. (2) Можно свести задачу к рассмотренным выше позициям. Например, выигрышную стратегию для игрока, который ходит первым, можно описать, указав ход, ведущий в позицию, для которой известна выигрышная стратегия для игрока, который ходит вторым. Чтобы подобным образом описать выигрышную стратегию для игрока, который ходит вторым (Вали), нужно перебрать все возможные первые ходы Паши и убедиться, что для всех полученных позиций мы знаем выигрышную стратегию для игрока, который ходит первым. В примере решения мы используем в основном второй способ описания стратегии. Экзаменуемый может описывать стратегию любым удобным ему способом. Существенно (повторим), чтобы (1) для каждой позиции, которая может встретиться игроку, реализующему стратегию, было понятно, какой ход он должен сделать, и (2) было показано, что все возможные заключительные позиции выигрышные для этого игрока.Задание 2 считается выполненным, если (i) правильно указано, кто из игроков имеет выигрышную стратегию в каждой из указанных позиций, и (ii) описаны выигрышные стратегии. Задание 3 считается выполненным, если (i) правильно указано, что выигрышную стратегию имеет Валя; (ii) правильно описано дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). При этом допускаются арифметические ошибки, не искажающие сути решения. Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом |
|||||||||||||||||||||||||||
| Выполнены второе и третье задания. Для первого задания правильно перечислены позиции, в которых Паша выигрывает первым ходом (п. 1а), и правильно указано, кто из игроков имеет выигрышную стратегию при указанных значениях S (п. 1б). При этом допускаются недочёты следующих типов: – в п. 1а не указано, каким ходом выигрывает Паша; – в п. 1б не указано, что игрокам нет смысла удваивать количество камней в куче. Здесь и далее в решениях допускаются арифметические ошибки, которые не искажают сути решения и не приводят к неправильному ответу |
3 | ||||||||||||||||||||||||||
| Не выполнены условия, позволяющие поставить 3 балла, и выполнено одно из следующих условий.
|
2 | ||||||||||||||||||||||||||
| Не выполнены условия, позволяющие поставить 3 или 2 балла, и выполнено одно из следующих условий.
|
1 | ||||||||||||||||||||||||||
| Не выполнено ни одно из условий, позволяющих поставить 1, 2 или 3 балла |
0 | ||||||||||||||||||||||||||
| Максимальный балл | 3 |
Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №26
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Решение:
| Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
|||||||||||||||||||||||||||||||||||
| Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани. При начальной позиции (6, 33) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 33), (12, 33), (6, 34), (6, 66). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Для позиции (8, 32) после первого хода Пети может получиться одна из следующих четырёх позиций: (9, 32), (16, 32), (8, 33), (8, 64). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети выигрывает своим первым ходом.Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети. При начальной позиции (6, 32) он должен первым ходом получить позицию (6, 33), из начальных позиций (7, 32) и (8, 31). Петя после первого хода должен получить позицию (8, 32). Позиции (6, 33) и (8, 32) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (8, 31), (7, 32), (14, 31) и (7, 62). В позициях (14, 31) и (7, 62) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (8, 31) и (7, 32) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или втором ходу.Примечание для эксперта. Последняя фраза в приведённом решении избыточна. Не будет ошибкой, если экзаменуемый просто напишет, например, «При выбранной стратегии партия длится не более двух ходов».В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом. |
|||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||
| Примечание для эксперта. Дерево всех партий может быть также изображено в виде ориентированного графа – так, как показано на рисунке, или другим способом. Например, вершины дерева, соответствующие одной и той же позиции, на рисунке могут быть «склеены». Важно, чтобы множество полных путей в графе находилось во взаимно однозначном соответствии с множеством партий, возможных при описанной в решении стратегии. | |||||||||||||||||||||||||||||||||||
Рис. 1. Дерево всех партий, возможных при описанной стратегии Вани. Ходы Пети показаны пунктирными стрелками, ходы Вани показаны сплошными стрелками. Заключительные позиции обозначены прямоугольником. Примечание для эксперта. В некоторых позициях у Вани есть и другой способ выигрыша: например, в позиции (8, 64) можно добавить один камень в любую кучу. То, что это не указано, не является ошибкой. Экзаменуемый не должен указывать все возможные выигрышные стратегии |
|||||||||||||||||||||||||||||||||||
| Указания по оцениванию | Баллы | ||||||||||||||||||||||||||||||||||
| В задаче от ученика требуется выполнить три задания. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом |
|||||||||||||||||||||||||||||||||||
| Выполнены все три задания.
Здесь и далее в решениях допускаются арифметические ошибки, |
3 | ||||||||||||||||||||||||||||||||||
| Не выполнены условия, позволяющие поставить 3 балла, и выполнено хотя бы одно из следующих условий.
|
2 | ||||||||||||||||||||||||||||||||||
| Не выполнены условия, позволяющие поставить 2 или 3 балла, и выполнено хотя бы одно из следующих условий.
|
1 | ||||||||||||||||||||||||||||||||||
| Не выполнено ни одно из условий, позволяющих поставить 1, 2 или 3 балла | 0 | ||||||||||||||||||||||||||||||||||
| Максимальный балл | 3 |
Единый государственный экзамен ЕГЭ 16.06.2016 по информатике. Основная волна. Вариант 41 (Часть С)
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра заканчивается, когда в куче не меньше 42 камней.
При этом, если число камней в куче не превышает 74, то побеждает игрок, сделавший последний ход, иначе выигрывает его оппонент. В начальный момент в куче было S камней; 1 ≤ S ≤ 41.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1
а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Опишите его стратегию.
б) У кого есть выигрышная стратегия при S = 38, 39, 40?
Задание 2
Кто из игроков имеет выигрышную стратегию при S = 19, 20?
Задание 3
Кто из игроков имеет выигрышную стратегию при S = 18?
В каждом случае опишите выигрышную стратегию. В задании 3 постройте дерево игры или таблицу, где ребрами являются сделанные ходы, а узлами – позиции камней.
Решение:
| Задание 1. а) Паша может выиграть в один ход, если S = 41 или 21<=S <= 37. При S = 41 Паша добавит в кучу один камень:
41+1=42(выигрыш) При 21<=S <= 37 увеличит количество камней в куче в два раза. 21*2=42(выигрыш) 37*2=74(выигрыш) Задание 2. При S=19, у Вали есть выигрышная стратегия. |
|||||||||||||
|
При S=20, у Вали есть выигрышная стратегия.
| Положения после очередных ходов | |||
| И.п. | 1-й ход Паши (только ход по стратегии) |
1-й ход Вали (все ходы) |
2-й ход Паши (только ход по стратегии) |
| 20 | 20*2=40 | 40+1=41 | 41+1=42 |
Задание 3
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 10 камней, за один ход можно получить кучу из 12 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 50 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 49.
- При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
- Назовите три значения S, при которых Петя может выиграть своим вторым ходом.
- При каком S Ваня выигрывает своим первым или вторым ходом?
Решение:
1а. для всех S от 17 до 49
1б. S = 15 или 16
2. S = 5, 13, 14
3. S = 11 или 12
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 75. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 75 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 74.
- При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
- Назовите три значения S, при которых Петя может выиграть своим вторым ходом.
- Назовите одно значение S, при котором Ваня выигрывает своим первым или вторым ходом.
Решение:
1а. для всех S от 25 до 74
1б. S = 24
2. S = 8, 22, 23
3. S = 21
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
- добавить в кучу один камень или
- увеличить количество камней в куче в три раза и убрать из кучи 1 камень.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 29 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 32.
- При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
- Назовите два значения S, при которых Петя может выиграть своим вторым ходом?
- Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.
Решение:
1а. для всех S от 12 до 32
1б. S = 11
2. S = 4, 10
3. S = 9
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 38. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 38 или больше камней.
В начальный момент в первой куче было 8 камней, во второй куче – S камней; 1 ≤ S ≤ 29.
- При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
- Назовите одно любое значение S, при котором Петя может выиграть своим вторым ходом.
- Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.
Решение:
1а. для всех S от 10 до 29
1б. нет таких
2. S = 9
3. S = 8
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в одну из куч (по своему выбору) два камня или
б) увеличить количество камней в куче в два раза.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в обеих кучах всего будет 75 камней или больше.
Задание 1. Для каждой из начальных позиций (10, 32), (11, 31) укажите, кто из игроков имеет выигрышную стратегию.
Задание 2. Для каждой из начальных позиций (10, 31), (11,30), (12,30) укажите, кто из игроков имеет выигрышную стратегию.
Задание 3. Для начальной позиции (10,29) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной выигрышной стратегии.
Решение:
1. Ваня
2. Петя
3. Ваня
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень или
б) увеличить количество камней в куче в два раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче оказалось не более 46 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 £ S £ 27.
Задание 1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.
б) У кого из игроков есть выигрышная стратегия при S = 24, 25, 26? Опишите выигрышные стратегии для этих случаев.
Задание 2. У кого из игроков есть выигрышная стратегия при S = 10, 11? Опишите соответствующие выигрышные стратегии.
Задание 3. У кого из игроков есть выигрышная стратегия при S = 8? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.
Решение:
1а. для S = [14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 27]
1б. S = 24 – Ваня, S = 25 – Петя, S = 26 – Ваня
2. S = 10 – Петя, S = 11 – Ваня,
3. S = 8 – Петя
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) добавить в кучу два камня;
г) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче превышает 73. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 74 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 73.
Задание 1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2. Укажите три значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети.
Задание 3. Укажите такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции.
Решение:
1а. для S = 25, …, 73
1б. S = 24
2. S = 8, 22, 23; из этих позиций Петя может получить кучу из 24 камней.
3. S = 21. Все ходы ведут в выигрышные позиции (для Вани).