Вверх

Линия заданий 26, ЕГЭ по информатике

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

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче - S камней; 1 ⩽ S ⩽ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

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

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

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

Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).
В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.

Задание 1
а) Петя может выиграть при 35 ⩽ S ⩽ 69.
б) S = 18.

Задание 2
Возможное значение S: 34. В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию (8, 34). После хода Вани может возникнуть одна из четырёх позиций: (9, 34), (16, 34), (8, 35), (8, 68). В каждой из этих позиций Петя может выиграть одним ходом, удвоив количество камней во второй куче.
Ещё одно возможное значение S для этого задания - число 31. В этом случае Петя первым ходом должен удвоить количество камней в меньшей куче и получить позицию (7*2, 31) = (14, 31). При такой позиции Ваня не может выиграть первым ходом, а после любого хода Вани Петя может выиграть, удвоив количество камней в большей куче. В решении достаточно указать одно значение 5 и описать для него выигрышную стратегию.

Задание 3
Возможное значение S: 33. После первого хода Пети возможны позиции: (8, 33), (14, 33), (7, 34), (7, 66). В позициях (14, 33) и (7, 66) Ваня может выиграть первым ходом, удвоив количество камней во второй куче. Из позиций (8, 33) и (7, 34) Ваня может получить позицию (8, 34). Эта позиция разобрана в п. 2. Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.

Ещё одно возможное значение S для этого задания - число 30. После первого хода Пети возможны позиции: (8, 30), (14, 30), (7, 31), (7, 60). Из позиции (8, 30) Ваня может получить позицию (16, 30) и независимо от ответного хода Пети выиграть своим следующим ходом, удвоив количество камней во второй куче. Из позиций (14, 30) и (7, 31) Ваня может получить позицию (14, 31). Эта позиция разобрана в замечании к заданию 2. В позиции (7, 60) Ваня может выиграть первым ходом, удвоив количество камней во второй куче.

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике
Дерево всех партий, возможных при Ваниной стратегии. Ходы Пети показаны пунктиром; ходы Вани — сплошными линиями. Прямоугольником обозначены позиции, в которых партия заканчивается.
Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12226.

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

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 75. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 75 или больше камней. В начальный момент в первой куче было семь камней, во второй куче - S камней; 1 ⩽ S ⩽ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

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

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

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

Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).
В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.

Задание 1
а) Петя может выиграть при 35 ⩽ S ⩽ 69.
б) S = 18.

Задание 2
Возможное значение S: 34. В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию (6, 34). После хода Вани может возникнуть одна из четырёх позиций: (7, 34), (12, 34), (6, 35), (6, 68). В каждой из этих позиций Петя может выиграть одним ходом, удвоив количество камней во второй куче.
Ещё одно возможное значение S для этого задания - число 32. В этом случае Петя первым ходом должен удвоить количество камней в меньшей куче и получить позицию (5*2, 32) = (10, 32). При такой позиции Ваня не может выиграть первым ходом, а после любого хода Вани Петя может выиграть, удвоив количество камней в большей куче. В решении достаточно указать одно значение 5 и описать для него выигрышную стратегию.

Задание 3
Возможное значение S: 33. После первого хода Пети возможны позиции: (6, 33), (10, 33), (5, 34), (5, 66). В позициях (10, 33) и (5, 66) Ваня может выиграть первым ходом, удвоив количество камней во второй куче. Из позиций (6, 33) и (5, 34) Ваня может получить позицию (6, 34). Эта позиция разобрана в п. 2. Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.

Ещё одно возможное значение S для этого задания - число 31. После первого хода Пети возможны позиции: (6, 31), (10, 31), (5, 32), (5, 62). Из позиции (6, 31) Ваня может получить позицию (12, 31) и независимо от ответного хода Пети выиграть своим следующим ходом, удвоив количество камней во второй куче. Из позиций (10, 31) и (5, 32) Ваня может получить позицию (10, 32). Эта позиция разобрана в замечании к заданию 2. В позиции (5, 62) Ваня может выиграть первым ходом, удвоив количество камней во второй куче.

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике
Дерево всех партий, возможных при Ваниной стратегии. Ходы Пети показаны пунктиром; ходы Вани — сплошными линиями. Прямоугольником обозначены позиции, в которых партия заканчивается.
Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12253.

12280. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 48. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 48 или больше камней.
В начальный момент в куче было S камней; 1 ⩽ S ⩽ 47.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

Задание 3
Укажите значение S, при котором:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах - количество камней в куче.

1. а) Петя может выиграть, если S = 16, …, 47. Во всех этих случаях достаточно утроить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 47 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 15 камней. Тогда после первого хода Пети в куче будет 16 или 45 камней. В обоих случаях Ваня утраивает количество камней и выигрывает в один ход.

2. Возможные значения S: 5 и 14. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 15 камней: в первом случае утроением, во втором добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (т.е. Петя) следующим ходом выиграет.

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

Задание ЕГЭ по информатике
Дерево всех партий, возможных при Ваниной стратегии. Знаком >> обозначены позиции, в которых партия заканчивается.

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12280.

12307. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 39. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 39 или больше камней.
В начальный момент в куче было S камней; 1 ⩽ S ⩽ 38.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

Задание 3
Укажите значение S, при котором:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах - количество камней в куче.

1. а) Петя может выиграть, если S = 13, …, 38. Во всех этих случаях достаточно утроить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 38 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 12 камней. Тогда после первого хода Пети в куче будет 13 или 36 камней. В обоих случаях Ваня утраивает количество камней и выигрывает в один ход.

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

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

Задание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12307.

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

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 31. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 31 или больше камней.
В начальный момент в куче было S камней; 1 ⩽ S ⩽ 30.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

Задание 3
Укажите значение S, при котором:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах - количество камней в куче.

1. а) Петя может выиграть, если S = 16, …, 30. Во всех этих случаях достаточно удвоить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 30 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 15 камней. Тогда после первого хода Пети в куче будет 16, 17 или 30 камней. Во всех случаях Ваня удваивает количество камней и выигрывает первым ходом.

2. Возможные значения S: 13, 14. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 15 камней: в первом случае добавлением двух камней, во втором добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (т.е. Петя) следующим ходом выиграет.

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике
Дерево всех партий, возможных при Ваниной стратегии. Знаком >> обозначены позиции, в которых партия заканчивается.

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12334.

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

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 27. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 27 или больше камней.
В начальный момент в куче было S камней; 1 ⩽ S ⩽ 26.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

Задание 3
Укажите значение S, при котором:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах - количество камней в куче.

1. а) Петя может выиграть, если S = 14, …, 26. Во всех этих случаях достаточно удвоить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 26 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 13 камней. Тогда после первого хода Пети в куче будет 14, 15 или 26 камней. Во всех случаях Ваня удваивает количество камней и выигрывает в один ход.

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

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

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12361.

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

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

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

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

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

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

Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла)

1. а) Петя может выиграть, если S =14, …, 27. Во всех этих случаях достаточно удвоить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 27 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 13 камней. Тогда после первого хода Пети в куче будет 14, 15 или 26 камней. Во всех случаях Ваня удваивает количество камней и выигрывает в один ход.

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

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

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

Задание ЕГЭ по информатике
Задание ЕГЭ по информатике
Дерево всех партий, возможных при Ваниной стратегии. Знаком >> обозначены позиции, в которых партия заканчивается.

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12388.

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 32.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 32 или больше камней.
В начальный момент в куче было S камней, 1 ⩽ S ⩽ 31.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

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

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

1. а) Петя может выиграть, если S = 16, …, 31. Во всех этих случаях достаточно удвоить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 31 камня.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 15 камней. Тогда после первого хода Пети в куче будет 16, 17 или 30 камней. Во всех случаях Ваня удваивает количество камней и выигрывает первым ходом.

2. Возможные значения S: 13, 14. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 15 камней: в первом случае добавлением двух камней, во втором добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (т.е. Петя) следующим ходом выиграет.

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

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

Задание ЕГЭ по информатике
Задание ЕГЭ по информатике
Дерево всех партий, возможных при Ваниной стратегии. Знаком >> обозначены позиции, в которых партия заканчивается.

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12415.

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 38. Если при этом в куче оказалось не более 66 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 35 камней и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 37.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

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

1) а) Паша может выиграть, если S = 37 или S = 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33. При S = 37 первым ходом нужно добавить в кучу один камень, при остальных указанных значениях S нужно удвоить количество камней.
б) При S = 34, 35 или 36 удваивать количество камней не имеет смысла, так как после такого хода выигрывает противник. Поэтому можно считать, что единственный возможный ход - это добавление в кучу одного камня.
При S = 36 после такого хода Паши в куче станет 37 камней. В этой позиции ходящий (т.е. Валя) выигрывает (см. п. а)): т.е. при S = 36 Паша (игрок, который должен ходить первым) проигрывает. Выигрышная стратегия есть у Вали.
При S = 35, после того как Паша своим первым ходом добавит один камень, в куче станет 36 камней. В этой позиции ходящий (т.е. Валя) проигрывает (см. выше): т.е. при S = 35 Паша (игрок, который должен ходить первым) выигрывает. Выигрышная стратегия есть у Паши.
При S = 34 выигрышная стратегия есть у Вали. Действительно, если Паша первым ходом удваивает количество камней, то в куче становится 68 камней и игра сразу заканчивается выигрышем Вали. Если Паша добавляет один камень, то в куче становится 35 камней.
Как мы уже знаем, в этой позиции игрок, который должен ходить (т.е. Валя), выигрывает во всех случаях выигрыш достигается тем, что при своём ходе игрок, имеющий выигрышную стратегию, должен добавить в кучу один камень.

2) При S = 18 или 17 выигрышная стратегия есть у Паши. Она состоит в том, чтобы удвоить количество камней в куче и получить кучу, в которой будет соответственно 36 или 34 камня. В обоих случаях игрок, который будет делать ход (теперь это Валя), проигрывает (п. 1б).

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

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

Задание ЕГЭ по информатике
Задание ЕГЭ по информатике
Дерево всех партий, возможных при Валиной стратегии. Знаком >> обозначены позиции, в которых партия заканчивается.

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12442.

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 42. Если при этом в куче оказалось не более 74 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 39 камней и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было 5 камней, 1 ⩽ S ⩽ 41.

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

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

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

Задание 2
У кого из игроков есть выигрышная стратегия при S = 20, 19? Опишите соответствующие выигрышные стратегии.

Задание 3
У кого из игроков есть выигрышная стратегия при S = 18? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах - количество камней в позиции.

1. а) Паша может выиграть, если S = 41 или S = 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37. При S = 41 первым ходом нужно добавить в кучу один камень, при остальных указанных значениях S нужно удвоить количество камней.
б) При S = 38, 39 или 40 удваивать количество камней не имеет смысла, так как после такого хода выигрывает противник. Поэтому можно считать, что единственный возможный ход - это добавление в кучу одного камня.
При S = 40 после такого хода Паши в куче станет 41 камень. В этой позиции ходящий (т.е. Валя) выигрывает (см. п. а)): т.е. при S = 40 Паша (игрок, который должен ходить первым) проигрывает. Выигрышная стратегия есть у Вали.
При S = 39, после того как Паша своим первым ходом добавит один камень, в куче станет 40 камней. В этой позиции ходящий (т.е. Валя) проигрывает (см. выше): т.е. при S = 39 Паша (игрок, который должен ходить первым) выигрывает. Выигрышная стратегия есть у Паши.
При S = 38 выигрышная стратегия есть у Вали. Действительно, если Паша первым ходом удваивает количество камней, то в куче становится 76 камней и игра сразу заканчивается выигрышем Вали. Если Паша добавляет один камень, то в куче становится 39 камней. Как мы уже знаем, в этой позиции игрок, который должен ходить (т.е. Валя), выигрывает.
Во всех случаях выигрыш достигается тем, что при своём ходе игрок, имеющий выигрышную стратегию, должен добавить в кучу один камень.

2. При S = 20 или 19 выигрышная стратегия есть у Паши. Она состоит в том, чтобы удвоить количество камней в куче и получить кучу, в которой будет соответственно 40 или 38 камней. В обоих случаях игрок, который будет делать ход (теперь это Валя), проигрывает (п. 1б).

3. При S = 18 выигрышная стратегия есть у Вали. После первого хода Паши в куче может стать либо 19, либо 36 камней. В обеих этих позициях выигрывает игрок, который будет делать ход (теперь это Валя). Случай S = 19 рассмотрен в п. 2, случай S = 36 рассмотрен в п. 1а.
В таблице изображено дерево возможных партий при описанной стратегии Вали. Заключительные позиции (в них выигрывает Валя) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).

Задание ЕГЭ по информатике
Задание ЕГЭ по информатике
Дерево всех партий, возможных при Валиной стратегии. Знаком >> обозначены позиции, в которых партия заканчивается.

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12469.

Для вас приятно генерировать тесты, создавайте их почаще