Егэ информатика куча камней - Помощь в подготовке к экзаменам и поступлению

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

Версия для печати и копирования в MS Word

Задания Д26 C3 № 4861

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 30.

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

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

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

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

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

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

Задания Д26 C3 № 4867

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 40.

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

Задания Д26 C3 № 4958

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

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 100.

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

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

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

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

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

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

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

Задания Д26 C3 № 5069

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

Игра завершается в тот момент, когда количество камней в куче становится более 200. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 201 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 200.

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

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

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

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

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

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

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

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

Задания Д26 C3 № 5225

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

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

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

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

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

Пройти тестирование по этим заданиям

Источник

Сегодня завершаем трилогию по теории игр из первой части ЕГЭ по информатике 2021.

Разберём 21 задание из ЕГЭ по информатике 2021.

Перейдём к примерным задачам из ЕГЭ по информатике 2021.

Задача (Одна куча камней)

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 32.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

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

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

Решение:

S₀ — первоначальное количество камней в куче.

Петя не должен выиграть на своём первом ходе. Найдём при каких значениях S₀ это возможно.

Петя может сделать всего 3 действия. Распишем количество камней в куче для 3-х случаев. Это количество должно быть меньше 33.

+1	+3	*2
S₀ + 1 < 33 S₀ < 32	S₀ + 3 < 33 S₀ < 30	2*S₀ < 33 S₀ < 17 (Округляем в большую сторону)

Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 17.

S₀ < 17

Рассмотрим 1-ый ход, который может сделать Петя в начале игры.

1. S₀+1 — оставил Петя после своего первого хода.

При каких S₀ Ваня может выиграть первым своим ходом ?

+1	+3	*2
S₀ + 2 ≥ 33 S₀ ≥ 31	S₀ + 4 ≥ 33 S₀ ≥ 29	2S₀+2 ≥ 33 2S₀ ≥ 31 S₀ ≥ 16 (Округляем в большую сторону)

Получили первого кандидата для ответа S₀=16. Но если и в двух оставшихся ветках это значение пройдёт на первом ходу Вани, то мы не сможем засчитать этот ответ.

Может ли Петя выиграть вторым своим ходом ?

а) S₀+1+1 = S₀+2 — Ваня оставил после первого своего хода.

+1	+3	*2
S₀ + 3 < 33 S₀ < 30	S₀ + 5 < 33 S₀ < 28	2S₀+4 < 33 2S₀ < 29 S₀ < 15 (Округляем в большую сторону)

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт a) накладывается дополнительное ограничение S₀ < 15

Рассмотрим, при каких значениях S₀ Ваня сможет выиграть на своём втором ходе в пункте a).

1) S₀+1+1+1 = S₀+3 -Петя оставил после своего второго хода.

+1	+3	*2
S₀ + 4 ≥ 33 S₀ ≥ 29	S₀ + 6 ≥ 33 S₀ ≥ 27	2S₀ + 6 ≥ 33 2S₀ ≥ 27 S₀ ≥ 14 (Округляем в большую сторону)

Получили значение S₀ = 14, при котором Ваня может выиграть на своём втором ходе в пункте 1). Это первый кандидат для ответа.

б) S₀+1+3 = S₀+4 — Ваня оставил после первого своего хода.

+1	+3	*2
S₀ + 5 < 33 S₀ < 28	S₀ + 7 < 33 S₀ < 26	2S₀ + 8 < 33 2S₀ < 25 S₀ < 13 (Округляем в большую сторону)

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт б) накладывается дополнительное ограничение S₀ < 13

1) S₀+4+1 = S₀+5 — Петя оставил после второго хода.

+1	+3	*2
S₀ + 6 ≥ 33 S₀ ≥ 27	S₀ + 8 ≥ 33 S₀ ≥ 25	2S₀ + 10 ≥ 33 2S₀ ≥ 23 S₀ ≥ 12 (Округляем в большую сторону)

Получили значение S₀ = 12, при котором Ваня может выиграть на своём втором ходе в пункте 1). Это пока самый приоритетный кандидат для ответа.

Если мы в пунктах 2), 3), 4) получим меньшие значения, то у Пети есть всегда возможность свернуть в пункт 1), и там уже значения меньше, чем 12, подходить не будут. Теоретически Петя в пунктах 2), 3), 4) может создать ситуацию, когда Ваня не сможет выиграть на своём втором ходе («Заблокировать» ветку б). Но мы, перед тем, как записать ответ, сделаем проверку и найдём такую возможность, если она есть.

в) 2*(S₀+1) = 2*S₀+2 — Ваня оставил после первого своего хода.

+1	+3	*2
2S₀ + 3 < 33 2S₀ < 30 S₀ < 15	2S₀ + 5 < 33 2S₀ < 28 S₀ < 14	4S₀ + 4 < 33 4S₀ < 29 S₀ < 8 (Округляем в меньшую сторону)

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт в) накладывается дополнительное ограничение S₀ < 8

1) 2*S₀+2+1 = 2*S₀+3 — Петя оставил после второго хода.

+1	+3	*2
2S₀ + 4 ≥ 33 2S₀ ≥ 29 S₀ ≥ 15	2S₀ + 6 ≥ 33 2S₀ ≥ 27 S₀ ≥ 14 (Округляем в большую сторону)	4S₀ + 6 ≥ 33 4S₀ ≥ 27 S₀ ≥ 7 (Округляем в большую сторону)

Получили значение S₀ = 7, при котором Ваня может выиграть на своём втором ходе в пункте 1). Это пока самый приоритетный кандидат для ответа.

Теперь делаем проверку четырёх чисел, которые отмечены синим цветом. Проверку делаем в порядке возрастания. Если число подойдёт, то сразу записываем его в ответ.

Проверяем значение S₀ = 7

Проверим первую ветку, когда Петя на своём первом ходе делает +1 к куче.

Видим, что значение 7 полностью подходит в первой ветке.

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

Видим, что в этой ветке значение 7 не проходит. Числа 12 и 14 не дают возможность Вани выиграть на своём втором ходе. Значение 40 уже являются выигрышным для Пети.

Проверяем значение S₀ = 12

Видим, что значение 12 проходит в первой ветке. Рассмотрим вторую ветку.

Если Ваня сделает кучу, состоящую из 16 камней, то он сможет выиграть при любой игре Пети в этой ветке.

В этой ветке Ваня может выиграть на своём первом ходе! Число 48 уже является выигрышным.

Таким образом, в ответ пойдёт значение 12.

Ответ: 12

Рассмотрим более классическую задачу из 21 задания ЕГЭ по информатике 2021.

Задача (Демонстрационный вариант ЕГЭ по информатике 2021)

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

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

В начальный момент в первой куче было семь камней, во второй куче –
S камней; 1 ≤ S ≤ 69.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

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

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

Решение:

Обозначим первую кучу за a, вторую кучу за b.

Распишем все комбинации для суммы двух куч для каждого хода:

Блок 1

1. a + 1 + b (Добавляем камень к первой куче)
2. a + b + 1 (Добавляем камень ко второй куче)
3. 2*a + b (Удваиваем первую кучу)
4. a + 2*b (Удваиваем вторую кучу)

S₀ — первоначальное количество камней во второй куче.

a=7, b=S₀ — Первоначальное положение

Петя не должен выиграть на своём первом ходе. Найдём при каких значениях S₀ это возможно.

У нас эти данные должны были остаться после решения 20 задания (см в этой статье). Но распишем ещё раз, чтобы всё выкладки были перед глазами.

Петя может сделать всего 4 действия. Распишем сумму двух кучек для 4-х случаев. Эти суммы должны быть меньше 77.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 8 < 77 S₀ < 69	S₀ + 8 < 77 S₀ < 69	S₀ + 14 < 77 S₀ < 63	2S₀ + 7 < 77 2S₀ < 70 S₀ < 35

Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 35.

S₀ < 35

Рассмотрим все ходы, которые может сделать Петя в начале игры.

1. a=8, b=S₀ — оставил Петя после своего первого хода.

При каких S₀ Ваня может выиграть первым своим ходом ?

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 9 ≥ 77 S₀ ≥ 68	S₀ + 9 ≥ 77 S₀ ≥ 68	S₀ + 16 ≥ 77 S₀ ≥ 61	2S₀ + 8 ≥ 77 2S₀ ≥ 69 S₀ ≥ 35 (Округляем в большую сторону)

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

Может ли Петя выиграть вторым своим ходом ?

а) a=9(8+1), b=S₀ — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 10 < 77 S₀ < 67	S₀ + 10 < 77 S₀ < 67	S₀ + 18 < 77 S₀ < 59	2S₀ + 9 < 77 2S₀ < 68 S₀ < 34

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт a) накладывается дополнительное ограничение S₀ < 34

Рассмотрим, при каких значениях S₀ Ваня сможет выиграть на своём втором ходе в пункте a).

1) a=10, b=S₀ -Петя оставил после своего второго хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 11 ≥ 77 S₀ ≥ 66	S₀ + 11 ≥ 77 S₀ ≥ 66	S₀ + 20 ≥ 77 S₀ ≥ 57	2S₀ + 10 ≥ 77 2S₀ ≥ 67 S₀ ≥ 34 Округляем в большую сторону

Видим, что Ваня не может выиграть на своём втором ходе в пункте a). Значения не проходят ограничение S₀ < 34.

Петя всегда может ходить a=10, b=S₀ и «блокировать» пункт a).

б) a=8, b=S₀+1 — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 10 < 77 S₀ < 67	S₀ + 10 < 77 S₀ < 67	S₀ + 17 < 77 S₀ < 60	2S₀ + 10 < 77 2S₀ < 67 S₀ < 34 (Округляем в большую сторону)

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт б) накладывается дополнительное ограничение S₀ < 34

1) a=9(8+1), b=S₀+1 — Петя оставил после второго хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 11 ≥ 77 S₀ ≥ 66	S₀ + 11 ≥ 77 S₀ ≥ 66	S₀ + 19 ≥ 77 S₀ ≥ 58	2S₀ + 11 ≥ 77 2S₀ ≥ 66 S₀ ≥ 33

Получили значение S₀ = 33, при котором Ваня может выиграть на своём втором ходе в пункте 1). Это первый кандидат для ответа.

Если мы в пунктах 2), 3), 4) получим меньшие значения, то у Пети есть всегда возможность свернуть в пункт 1), и там уже значения меньше, чем 33, подходить не будут. Теоретически Петя в пунктах 2), 3), 4) может создать ситуацию, когда Ваня не сможет выиграть на своём втором ходе («Заблокировать» ветку б). Но мы, перед тем, как записать ответ, сделаем проверку и найдём такую возможность, если она есть.

в) a=16, b=S₀ — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 17 < 77 S₀ < 60	S₀ + 17 < 77 S₀ < 60	S₀ + 32 < 77 S₀ < 45	2S₀ + 16 < 77 2S₀ < 61 S₀ < 31 (Округляем в большую сторону)

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт в) накладывается дополнительное ограничение S₀ < 31

1) a=17(16+1), b=S₀ — Петя оставил после второго хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 18 ≥ 77 S₀ ≥ 59	S₀ + 18 ≥ 77 S₀ ≥ 59	S₀ + 34 ≥ 77 S₀ ≥ 43	2S₀ + 17 ≥ 77 2S₀ ≥ 60 S₀ ≥ 30

Получили значение S₀ = 30. Ещё один кандидат для ответа. Даже более приоритетный, потому что нам нужно найти наименьшее значение S₀, при котором будут выполняться условия задачи.

г) a=8, b=2*S₀ — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
2S₀ + 9 < 77 2S₀ < 68 S₀ < 34	2S₀ + 9 < 77 2S₀ < 68 S₀ < 34	2S₀ + 16 < 77 2S₀ < 61 S₀ < 31 Округляем в большую сторону	4S₀ + 8 < 77 4S₀ < 69 S₀ < 18 Округляем в большую сторону

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт г) накладывается дополнительное ограничение S₀ < 18

1) a=9, b=2*S₀ — Петя оставил после второго хода.

a+1+b	a + b+1	*2a** + b	a + *2b**
2S₀ + 10 ≥ 77 2S₀ ≥ 67 S₀ ≥ 34 (Округляем в большую сторону)	2S₀ + 10 ≥ 77 2S₀ ≥ 67 S₀ ≥ 34 (Округляем в большую сторону)	2S₀ + 18 ≥ 77 2S₀ ≥ 59 S₀≥30 (Округляем в большую сторону)	4S₀ + 9 ≥ 77 4S₀ ≥ 68 S₀ ≥ 17

Получили значение S₀ = 17. Ещё один кандидат на ответ. Это значение самое приоритетное.

Теперь делаем проверку трёх чисел, которые отмечены синим цветом. Проверку делаем в порядке возрастания. Если число подойдёт, то сразу записываем его в ответ.

Первый ход Пети, при котором он прибавляем к первой куче единицу мы уже исследовали. Начинаем со второй возможности Пети прибавить 1 ко второй куче.

Проверяем значение S₀ = 17

Проверим первую ветку, когда Петя прибавляет 1 к первой куче.

Синим цветом показаны кучки, которые оставляет Петя. Зелёным цветом показаны кучки, которые оставляет Ваня.

Мы рассматриваем именно тот пункт г), который и принёс нам значение 17. Видим, что это значение полность подходит в первой ветке.

Проверим вторую ветку.

Красным цветом показаны те ходы Пети, которые не дают Вани выиграть на втором своём ходе.

(9,18), (8,19), (15,18) — эти точки не дают Вани выиграть. (7, 72) — Петя сам выигрывает на своём втором ходе.

Что бы ни делал Ваня, он не может выиграть на втором своём ходе. Значит, значение 17 нам не подходит.

Проверяем значение S₀ = 30

Проверим первую ветку, когда Петя прибавляет 1 к первой куче.

Видим, значение 30 в первой ветке подходит полностью.

Видим, если Ваня пойдёт (14,31), то он сможет выиграть на втором своём ходе при любом втором ходе Пети!

Проверим что будет, если Петя на своём первом ходе увеличит первую кучу в два раза.

Видим, и в этой ветке, если Ваня пойдёт (14,31), то он сможет выиграть на втором своём ходе при любом втором ходе Пети!

Проверим что будет, если Петя на своём первом ходе увеличит вторую кучу в два раза.

Видим, что Ваня в этой ветке может выиграть на первом своём ходе!

Мы пришли к выводу: Значение S₀=30 нас полностью устраивает. Значение S₀=33 проверять не будем, т.к. нас просили найти наименьшее значение.

Ответ: 30

Решим ещё одну задачу 21 задания из тренировочных вариантов ЕГЭ по информатике 2021.

Задача (На закрепление)

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

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

В начальный момент в первой куче было 3 камня, во второй куче — S камней, 1 ≤ S ≤ 57.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

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

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

Решение:

Обозначим первую кучу за a, вторую кучу за b.

Распишем все комбинации для суммы двух куч для каждого хода:

Блок 1

1. a + 1 + b (Добавляем камень к первой куче)
2. a + b + 1 (Добавляем камень ко второй куче)
3. 4*a + b (Увеличиваем первую кучу в 4 раза)
4. a + 4*b (Увеличиваем вторую кучу в 4 раза)

S₀ — первоначальное количество камней во второй куче.

a=3, b=S₀ — Первоначальное положение

Петя не должен выиграть на своём первом ходе. Найдём при каких значениях S₀ это возможно.

Петя может сделать всего 4 действия. Распишем сумму двух кучек для 4-х случаев. Эти суммы должны быть меньше 61.

a+1+b	a + b+1	*4a** + b	a + *4b**
S₀ + 4 < 61 S₀ < 57	S₀ + 4 < 61 S₀ < 57	S₀ + 12 < 61 S₀ < 49	4S₀ + 3 < 61 4S₀ < 58 S₀ < 15 (Округляем в большую сторону)

Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 15.

S₀ < 15

Рассмотрим 1-ый ход, который может сделать Петя в начале игры.

1. a=4(3+1), b=S₀ — оставил Петя после своего первого хода.

При каких S₀ Ваня может выиграть первым своим ходом ?

a+1+b	a + b+1	*4a** + b	a + *4b**
S₀ + 5 ≥ 61 S₀ ≥ 56	S₀ + 5 ≥ 61 S₀ ≥ 56	S₀ + 16 ≥ 61 S₀ ≥ 45	4S₀ + 4 ≥ 61 4S₀ ≥ 57 S₀ ≥ 15 (Округляем в большую сторону)

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

Может ли Петя выиграть вторым своим ходом ?

а) a=5(4+1), b=S₀ — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*4a** + b	a + *4b**
S₀ + 6 < 61 S₀ < 55	S₀ + 6 < 61 S₀ < 55	S₀ + 20 < 61 S₀ < 41	4S₀ + 5 < 61 4S₀ < 56 S₀ < 14

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт a) накладывается дополнительное ограничение S₀ < 14

Рассмотрим, при каких значениях S₀ Ваня сможет выиграть на своём втором ходе в пункте a).

1) a=6(5+1), b=S₀ -Петя оставил после своего второго хода.

a+1+b	a + b+1	*4a** + b	a + *4b**
S₀ + 7 ≥ 61 S₀ ≥ 54	S₀ + 7 ≥ 61 S₀ ≥ 54	S₀ + 24 ≥ 61 S₀ ≥ 37	4S₀ + 6 ≥ 61 4S₀ ≥ 55 S₀ ≥ 14 Округляем в большую сторону

Видим, что Ваня не может выиграть на своём втором ходе в пункте a). Значения не проходят ограничение S₀ < 14.

Петя всегда может ходить a=6, b=S₀ и «блокировать» пункт a).

б) a=4, b=S₀+1 — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*4a** + b	a + *4b**
S₀ + 6 < 61 S₀ < 55	S₀ + 6 < 61 S₀ < 55	S₀ + 17 < 61 S₀ < 44	4S₀ + 8 < 61 4S₀ < 53 S₀ < 14 (Округляем в большую сторону)

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт б) накладывается дополнительное ограничение S₀ < 14

1) a=5(4+1), b=S₀+1 — Петя оставил после второго хода.

a+1+b	a + b+1	*4a** + b	a + *4b**
S₀ + 7 ≥ 61 S₀ ≥ 54	S₀ + 7 ≥ 61 S₀ ≥ 54	S₀ + 21 ≥ 61 S₀ ≥ 40	4S₀ + 9 ≥ 61 4S₀ ≥ 52 S₀ ≥ 13

Получили значение S₀ = 13, при котором Ваня может выиграть на своём втором ходе в пункте 1). Это первый кандидат для ответа.

Если мы в пунктах 2), 3), 4) получим меньшие значения, то у Пети есть всегда возможность свернуть в пункт 1), и там уже значения меньше, чем 13, подходить не будут. Теоретически Петя в пунктах 2), 3), 4) может создать ситуацию, когда Ваня не сможет выиграть на своём втором ходе («Заблокировать» ветку б). Но мы, перед тем, как записать ответ, сделаем проверку и найдём такую возможность, если она есть.

в) a=16, b=S₀ — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*4a** + b	a + *4b**
S₀ + 17 < 61 S₀ < 44	S₀ + 17 < 61 S₀ < 44	S₀ + 64 < 61	—

Видим, что Петя выигрывает в ветке в), если первую кучку умножит на 4.

г) a=4, b=4*S₀ — Ваня оставил после первого своего хода.

a+1+b	a + b+1	*4a** + b	a + *4b**
4S₀ + 5 < 61 4S₀ < 56 S₀ < 14	4S₀ + 5 < 61 4S₀ < 56 S₀ < 14	4S₀ + 16 < 61 4S₀ < 45 S₀ < 12 Округляем в большую сторону	16S₀ + 4 < 61 16S₀ < 57 S₀ < 4 Округляем в большую сторону

Видим, чтобы Петя не выиграл своим вторым ходом, на пункт г) накладывается дополнительное ограничение S₀ < 4

1) a=5, b=4*S₀ — Петя оставил после второго хода.

a+1+b	a + b+1	*4a** + b	a + *4b**
4S₀ + 6 ≥ 61 4S₀ ≥ 55 S₀ ≥ 14 (Округляем в большую сторону)	4S₀ + 6 ≥ 61 4S₀ ≥ 55 S₀ ≥ 14 (Округляем в большую сторону)	4S₀ + 20 ≥ 61 4S₀ ≥ 41 S₀≥11 (Округляем в большую сторону)	16S₀ + 5 ≥ 61 16S₀ ≥ 56 S₀ ≥ 4

Видим, что пункт г) не даёт решений.

В ответ мож

Источник

19-е задание: «Анализ алгоритма логической игры»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 6 минут.

Проверяемые элементы содержания: Умение анализировать алгоритм логической игры

20-е задание: «Поиск выигрышной стратегии»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 6 минут.

Проверяемые элементы содержания: Умение найти выигрышную стратегию игры

21-е задание: «Дерево игры для выигрышной стратегии»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 10 минут.

Проверяемые элементы содержания: Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию

До ЕГЭ 2021 года — эти задания были объединены в задание № 26 ЕГЭ

Плейлист видеоразборов задания на YouTube:

Содержание:

Игра с двумя кучами камней или табличка

Задания для тренировки 19, 20, 21 заданий ЕГЭ (взяты из КИМ и сборников прошлых лет)
- Игра с одной кучей камней
- Игра с набором слов

Игра с двумя кучами камней или табличка

Задание демонстрационного варианта 2022 года ФИПИ

19_8:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 59 или больше камней.
В начальный момент в первой куче было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 53.

Задание 19 ЕГЭ.

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

Задание 20 ЕГЭ.

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

Задание 21 ЕГЭ.
Найдите два значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.

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

✎ Задание 19:

Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 5, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 53. Таблица пригодится для решения заданий 20 и 21:

Для начала найдем все выигрышные позиции для первой строки таблицы, т.е. для первого хода. Обозначим их плюсами (+):

Выигрышные позиции для первой строки ищем по принципу увеличения количества камней S в 2 два раза: 5 + S*2 >=59. Получим S>=27

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

S = 14
1 ход Петя: 14*2 = (5,28)
2 ход Ваня: 28*2 = (5,56), Сумма = 61, Выигрыш!

Проанализируем таблицу, и для каждой строки найдем выигрышные позиции с одного хода. Т.е. которые позволят игроку, оказавшемуся «на них», выиграть за один ход (получить суммарно 59 и более камней):

При заполнении таблицы выигрышными позициями можно проследить закономерность «узора», а заполнять позиции по аналогии.

Найдем проигрышные позиции: те, которые ведут только в выигрышные позиции для соперника (ведут только в плюсы)

Проигрышные позиции: (6,26) (8,25) (10,24) (12,23) (14,22)

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

Наименьшее S = 24

Для решения этого задания найдем выигрышные позиции со второго хода, т.е. которые могут перевести соперника в проигрышную позицию (с минусом):

Чтобы выиграл Ваня, но выиграл не первым ходом, а вторым, необходимо, чтобы Петя находился в такой позиции, которая ведет его только на выигрышные позиции со второго хода:

Ответ: 23 25

19_9:

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

Например, пусть в одной куче 6, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5).

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

Задание 19 ЕГЭ.

Найдите значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети?

Задание 20 ЕГЭ.

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

Задание 21 ЕГЭ.

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

Ответы:
21
22 44
24

Показать решение (Excel):

✎ Задание 19:

В столбце А отложим значения — количество камней в первой куче. Начнем с ячейки А2, в которую внесем начальное количество камней, т.е. 10. Автозаполнением продлим значения вниз до 0:

В строке 1 таблицы (начиная с ячейки B1) отложим значения для второй кучи. Поскольку в задании говорится, что победа будет достигнута при S<=20, и достигнуть этого значения более сильной командой можно уменьшив кол-во камней во второй куче в два раза, начиная с числа 40: 40/20. То есть возьмем значение больше 40, примерно 45. Используем автозаполнение до значения 11:

Из двух команд, которые могут выполнять игроки, выберем наиболее сильную, т.е. благодаря которой можно быстрее достичь выигрышного диапазона и попасть в значения S<=20. Это команда уменьшения количества камней в два раза, т.е. /2.
Для каждой из ячеек полученной таблицы рассчитаем значение, полученное в результате уменьшения в два раза той кучи камней, в которой большее количество камней (так как это даст меньший результат). Например, для ячейки С5, в которой игрок имеет в первой куче 7 камней, а во второй куче 44 камня, мы бы выполнили действие 44/2+7. Т.е. уменьшили вдвое вторую кучу, т.к. в ней больше камней. Еще необходимо обращать внимание на четность и нечетность значений (в Excel это функция ЕНЕЧЁТ — возвращает ИСТИНУ, если значение нечетно).
Чтобы автоматизировать процесс необходимо использовать формулу, в которой найдем максимальное значение из двух вариантов:

Минимальное из
(ЕСЛИ(ЕНЕЧЁТ(1-я куча) то (1-я куча+1)/2+2-я куча, 
иначе 1-я куча/2+2-я куча);
ЕСЛИ(ЕНЕЧЁТ(2-я куча) то (2-я куча+1)/2+1-я куча, 
иначе 2-я куча/2+1-я куча)).

Выразив это в формуле Excel, получим результат, который внесем в ячейку B2:

 = МИН(ЕСЛИ(ЕНЕЧЁТ($A2);($A2+1)/2+B$1;$A2/2+B$1);ЕСЛИ(ЕНЕЧЁТ(B$1);(B$1+1)/2+$A2;B$1/2+$A2))

Здесь знак $ будем использовать для фиксации столбца А и строки 1 при копировании формулы.
Скопируем формулу на всю таблицу.
Выделим всю таблицу и используем Условное форматирование для выделения тех значений, которые попадают в выигрыш (<21):

Выделенные значения — это значения, которые можно получить в сумме двух куч, выполнив ход из данной ячейки. И по сути, это и есть выигрышные позиции с 1 хода.
Далее следуем логике рассуждения: Ваня сможет выиграть своим первым ходом в том случае, если Петя оказывается РЯДОМ с выигрышной позицией, и любой его ход попадает ТОЛЬКО в выигрышные позиции для Вани (в выделенную область). Это позиция при S = 21:

Ответ: 21
✎ Задание 20:

Продолжаем работать с той же таблицей, что и в задании 19. Выделим все проигрышные позиции (из которых можно походить только в выигрышные позиции для соперника, т.е. в выделенные ячейки):

Петя может выиграть свои вторым ходом, если он не может выиграть первым ходом, но может выполнить ход в позицию, проигрышную для соперника (в ячейку, выделенную красным). Такие позиции назовем выигрышные позиции со второго хода. Найдем минимальное и максимальное значение S при таком первом ходе Пети:

При S=44 Пете необходимо уменьшить 2-ю кучу вдвое (44/2 = 22), чтобы оказаться в проигрышной позиции для соперника.

Ответ: 22 44

✎ Задание 21:

Выделим все такие выигрышные позиции со второго хода:

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

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

Ответ: 24

19_7:

Два игрока, Петя и Ваня, играют в следующую игру. На табличке написаны два значения. Оба игрока в свой ход могут заменить одно из значений на сумму обеих (по своему выбору). Первый ход делает Петя. Игра считается законченной когда сумма обеих значений равняется не меньше 56. То есть выигрывает игрок, получивший 56 или более в сумме. Начальное значение (10, S).

Задание 19 ЕГЭ.

Найдите максимальное S при котором Петя не может выиграть первым ходом.

Задание 20 ЕГЭ.

У кого из игроков есть выигрышная стратегия при начальном значении (9, 15).

Задание 21 ЕГЭ.

У кого из игроков есть выигрышная стратегия при начальном значении (3,7)? Опишите эту стратегию и изобразите дерево всех возможных партий

при этой стратегии

Типовые задания для тренировки

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

Задание 19.
Максимальное S при котором Петя НЕ может выиграть своим первым ходом S = 22. Петя проиграет, если в сумме получится 55 и меньше. Первое значение = 10, необходимо найти второе значение, при этом максимальное. Схематично отобразим варианты ходов:

(10,22) - ход Пети - (10+22, 22) - итог суммы обеих значений таблички: 32 + 22 = 54 (<56)

Для того, чтобы сделать сумму большей, Петя заменит первое значение на сумму, так как оно меньше второго значения (10<22)

Задание 20.
В начальной позиции (9, 15) выигрышная стратегия есть у Вани. Для себя отобразим схематично выигрышную партию Вани:

Зеленым цветом выделены выигрышные ходы.

Задание 21.
В начальной позиции (3, 7) выигрышная стратегия есть у Вани. Изобразим дерево всех возможных партий при этой стратегии (раз говорится «при этой стратегии» имеем в виду, выигрышную стратегию Вани):

Дерево для выигрышной стратегии Вани: для Вани отображены только ходы по стратегии, для Пети — все возможные ходы. Зеленым цветом — выигрышный ход, красная обводка — ход по стратегии.

19_6:

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

В начальный момент в первой куче было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 38.

Задание 19.

При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?

Задание 20.

Назовите одно любое значение S, при котором Петя может выиграть своим вторым ходом.

Задание 21.

Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.

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

Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 5, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 38:

Задание 19 а):

Далее будем рассуждать так: Петя может выиграть первым ходом, выполнив команду *2 (увеличить количество камней в куче в два раза), если вместо S (кол-во камней во второй куче), мы будем изменять значение, начиная от 20, до последнего возможного по условию значения 38:

5 + 20*2 = 45 (>44)

* 5 - кол-во камней в первой куче, оно не меняется по условию

Соответственно, все значения большие 20 дадут в результате число большее 44. Укажем это в таблице. + означает выигрышную позицию с первого хода:

Ответ 1 а):

S = [20;38] (На ЕГЭ пояснить ходы, например: (5; 20) -> (Ход Пети)-> (5;40); 40 + 5 = 45)

Задание 19 б):

Поскольку Ваня будет ходить вторым, то необходимо поменять количество камней и в первой куче. Значит рассмотрим ситуации, что Петя мог бы ходить первым ходом в (7;S) и в (10;S). Укажем, будут ли эти позиции выигрышные с одного хода: например (7;19) выигрышная позиция, т.к. игрок выполнит ход в (7;38) и выиграет (7 + 38 = 45). Соответственно, выигрышными являются и все позиции (7;больше 19). Проанализируем таблицу, увеличивая количество камней в первой куче и выполняя поиск выигрышных позиций с одного хода:

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

Находим единственное такое значение — (5; 19). Т.е. S = 19.

Ответ 1 б):

S = 19 (На ЕГЭ пояснить ходы, например: (5; 19) -> (Ходы Пети): (5;21),(5;28);(7;19);(7;28). Везде следующим ходом выиграет Ваня, см. предыдущ. пункт)

Задание 20:

Обратим внимание, что в таблице, все образовавшиеся «уголки» являются проигрышными позициями (с 1-го хода): то есть если игрок, оказывается в такой позиции, то он может выполнить ход только в выигрышные позиции (то есть следующим ходом выиграет соперник):

Логика рассуждений: Петя сможет выиграть своим вторым ходом, когда своим первым ходом он попадет в проигрышную позицию, т.е. переведет соперника в проигрышную ситуацию. Такие значения: S = 16, 17 или 18. Назовем эти позиции выигрышными со второго хода (2+):

Ответ 2:

S = 16, 17 или 18 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)

Задание 21:

Укажем в таблице также позиции, выигрышные с n-го хода: когда игрок может перевести соперника в проигрышную позицию:

Укажем также проигрышные позиции со второго хода: игрок, оказавшийся в такой позиции может выполнить ход только на выигрышные позиции (тогда соперник выиграет):

Логика рассуждений: Ваня сможет выиграть своим первым или вторым ходом, когда Петя своим первым ходом может попасть только либо в позицию выигрышную с первого хода (+), либо в позицию выигрышную со второго хода или n-го хода (2+). Это позиция при S = 14:

Ответ 3: S = 14 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)

📹 Видео

Видеорешение на RuTube здесь

Задания для тренировки 19, 20, 21 заданий ЕГЭ (взяты из КИМ и сборников прошлых лет)

Игра с одной кучей камней

19_3. Демоверсия ЕГЭ 2018 информатика:

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

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

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

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

Задание 21 ЕГЭ
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

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

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

Задание 19.

а) Петя может выиграть, если S = 15, … 28

15, ..., 28 - выигрышные позиции с первого хода

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

S = 14
Петя: 14 + 1 = 15  выигрышная позиция (см. п. а). Выигрывает Ваня
Петя: 14 * 2 = 28   выигрышная позиция (см. п. а). Выигрывает Ваня

14 - проигрышная позиция

Задание 20.

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

S = 7
Петя: 7 * 2 = 14  проигрышная позиция (см. п. 1 б). Выигрывает Петя
S = 13
Петя: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя

7, 13 - выигрышные позиции со второго хода

Задание 21.

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

S = 12
Петя: 12 + 1 = 13  
Ваня: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Ваня вторым ходом!

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

Дерево всех партий, возможных при стратегии Вани:

* красный круг означает выигрыш

19_4: Досрочный егэ по информатике 2018, вариант 1:

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

Задание 19 ЕГЭ.

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

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

Задание 20 ЕГЭ.

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

Задание 21 ЕГЭ.

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

Типовые задания для тренировки

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

19.

а)

S ≥ 14

S ≥ 14 выигрышные позиции

б) S = 13. Паша своим первым ходом может сделать 14, 17 или 65 камней, после этого Вася увеличивает количество в пять раз, получая 70, 85 или 325 камней в куче.

S = 13 
Паша 1 ход: 13 + 1 = 14
Паша 1 ход: 13 + 4 = 17
Паша 1 ход: 13 * 5 = 65

Ваня 1 ход: [14, 17, 65] * 5 = S ≥ 14  Ваня выигрывает

13 - проигрышная позиция

20. S = 9, 12. Для данных случаев Паше необходимо прибавить 4 камня к куче из 9 камней, либо 1 камень к куче из 12, и получить кучу из 13 камней.
После чего игра сводится к стратегии, описанной в пункте 1б.

S = 13 
Паша 1 ход: 9 + 4 = 13  Паша выигрывает
Паша 1 ход: 12 + 1 = 13 Паша выигрывает

9, 12 - выигрышные позиции со второго хода

21. S = 8. Своим первым ходом Паша может сделать количество камней в куче 9, 12 или 40. Если Паша увеличивает кол-во в пять раз, тогда Вася выигрывает своим первым ходом, увеличивая количество камней в пять раз.
Для случая 9 и 12 камней Вася использует стратегию, указанную в п.2.

S = 8 
Паша 1 ход: 8 + 1 = 9   Ваня Выигрывает (см. п.2)
Паша 1 ход: 8 + 4 = 12  Ваня Выигрывает (см. п.2)
Паша 1 ход: 8 * 5 = 40

📹 Видео (аналитическое решение)

Видеорешение на RuTube здесь

19_1:

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче осталось не более 44 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 23 камня, и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1≤ S ≤ 27.

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

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

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

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

а) Паша имеет выигрышную стратегию и может выиграть за один ход, если S = 27: тогда ему достаточно добавить один камень, чтобы игра закончилась при 28 камнях в куче; или если S = 14, 15, 16, 17, 18, 19, 20, 21, 22 (44/2 = 22 и 28/2 = 14, т.е. от 14 до 22): тогда необходимо удвоить кучу.

S=27
Паша: 27 + 1 = 28 - Выигрыш!

27 - выигрышная позиция

б) При S = 26 выигрышная стратегия есть у Вали. Паша делает ход первым, у него есть возможность либо удвоить количество камней в куче, и тогда количество превысит 44, — выигрывает Валя; либо увеличить количество на один камень, станет 27 камней: следующая Валя, — она может положить один камень и выиграть.

S=26
Паша: 26 * 2 = 52   Валя выигрывает! или:
Паша: 26 + 1 = 27
Валя: 27 + 1 = 28 - Выигрыш! 

26 - проигрышная позиция

При S = 25 выигрышная стратегия есть у Паши. Удваивать количество камней нет смысла, т.к. количество превысит 44, значит, Паша добавит один камень, их станет 26, следующая Валя, — она может либо добавить камень (станет 27 камней, следующим ходом выиграет Паша) либо удвоить — и сразу проиграть, т.к. станет более 44 камней.

S=25
Паша: 25 + 1 = 26
Валя: 26 ...  проигрышная позиция (см. выше) Паша выигрывает!

25 - выигрышная позиция

При S = 24 выигрышная стратегия есть у Вали. Паша делает ход первым: удваивать кучу нет смысла, т.к. в ней станет более 44, значит, Паша добавит один камень, их станет 25; следующая — Валя: она может только добавить один камень (станет 26 камней, следующим ходом Паша оказывается в проигрышной позиции, см. пункт при S = 26).

S=24
Паша: 24 + 1 = 25 
Валя: 25 ...  выигрышная позиция (см. выше) Валя выигрывает!
 
24 - проигрышная позиция

При S = 13 или S = 12 выигрышная стратегия есть у Паши. Паша удваивает количество и в куче остается 26 или 24 камня. Это проигрышная позиция для того, кто ходит (см. п. 1 б), а следующий ход за Валей.

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

Дерево возможных партий:

* Для Вали отображены только ходы по стратегии
** красный круг означает выигрыш
*** фиолетовый круг — конец игры (проигрыш)

📹 Видео (аналитическое решение)
Видеорешение на RuTube здесь

Задания с двумя кучами камней или табличка

19_5:

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

Задание 1.

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

Задание 2.

Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию.

Задание 3.

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

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

Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани.
Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети.
Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани.

📹 Видео (аналитическое решение)

Видеорешение на RuTube здесь

Игра с набором слов

19_2:

Петя и Ваня играют в игру: есть набор слов, необходимо последовательно называть буквы этих слов. Побеждает тот игрок, который называет последнюю букву любого слова из набора. Петя ходит первым.

Например, есть набор слов {Волк, Информатика, Страшно}; для заданного набора слов Петя своим первым ходом может назвать букву В, И или С. Если Петя выберет букву В, то победит Ваня (следующие ходы: Петя — В, Ваня — О, Петя — Л, Ваня — К).

Задание 1
А) Даны 2 слова (набора букв) {ИКЛМНИКЛМНХ, НМЛКИНМЛКИ}. Определить выигрышную стратегию.

Б) Даны 2 слова {ТРИТРИТРИ…ТРИ, РИТАРИТАРИТАРИТА…РИТА}. В первом слове 99 букв, во втором 164. Определить выигрышную стратегию.

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

Задание 3
Дан набор слов {Ворона, Волк, Волна, Производная, Прохор, Просо}. У кого из игроков есть выигрышная стратегия? Обосновать ответ и написать дерево всех возможных партий для выигрышной стратегии.

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

А) Для выигрыша Пете достаточно выбрать первую букву слова с нечетным количеством букв, тогда последний ход делает Петя. При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, что своим первым ходом он должен выбрать букву И (слово ИКЛМНИКЛМНХ из 11 букв). Ване придется выбрать букву К. Таким образом, они последовательно будут называть буквы первого слова, пока Петя не выберет последнюю букву Х. На этом игра закончится выигрышем Пети. При данной стратегии возможна только одна партия. Заключением партии будет написано слово ИКЛМНИКЛМНХ.

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

Если поменять местами во втором слове (НМЛКИНМЛКИ) буквы Н и И, то получится следующий набор слов:
```
{ИКЛМНИКЛМНХ, ИМЛКННМЛКИ}
```
Для данного набора выигрышная стратегия есть у Вани. Петя в любом случае должен будет выбрать букву И, а Ваня следующим ходом может перевести игру в проигрышную позицию для Пети, т.е. перейти на второе слово, назвав букву М. Такая стратегия приведет Ваню к выигрышу, так как последнюю букву слова — И — запишет именно он.
Выигрышная стратегия есть у Вани, так как при любом выборе Пети, Ваня может перевести игру в проигрышную позицию для Пети, т.е. «перейти» на слово с четным количеством букв. Такая стратегия позволит Ване написать последнюю букву и тем самым выиграть игру.

Дерево возможных партий:

* Для Вани отображены только ходы по стратегии
** Красный круг означает выигрыш

📹 Видео (аналитическое решение)

Видеорешение на RuTube здесь

Источник

В задание №19_20_21

Тема: Теория игр. Поиск выигрышной стратегии.

Проверяется умение анализировать алгоритм логической игры. Умение найти выигрышную стратегию игры. Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию.

Одна куча — варианты решений
Две кучи — варианты решений
Три кучи — варианты решений

Немного теории:

☆ Все позиции в простых играх делятся на выигрышные и проигрышные

выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку; при этом говорят, что у него есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть
если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сделает его соперник; в этом случае говорят, что у него нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника
выигрышные и проигрышные позиции можно охарактеризовать так:
- позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная;
- позиция, из которой хотя бы один из возможных ходов ведет в проигрышную позицию — выигрышная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию.

Одна куча:

Задание 19

Два игрока, Петя и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

Добавить в кучу один камень или
Добавить в кучу три камня или
Увеличить количество камней в куче в четыре раза.

Например, имея кучу из 20 камней, за одни ход можно получить кучу из 21, 23 или 80 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 78. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 78 или больше камней. В начальный момент в куче было S камней: 1 ≤ S ≤ 77.

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

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

Решение:

Ответ: 5

Задание 20

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

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

Найденные значения запишите в ответе в порядке возрастания.

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

Ответ: 16 18

Задание 21

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Ответ: 15

Задание 19 (самостоятельно)

Добавить в кучу один камень или
Добавить в кучу два камня или
Увеличить количество камней в куче в четыре раза.

Например, имея кучу из 20 камней, за одни ход можно получить кучу из 21, 22 или 79 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 85. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 85 или больше камней. В начальный момент в куче было S камней: 1 ≤ S ≤ 84.

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

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

Задание 20 (самостоятельно)

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

Найденные значения запишите в ответе в порядке возрастания.

Задание 21 (самостоятельно)

Для игры, описанной в задании 19, найдите максимальное значение S, при котором одновременно выполняются два условия:

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

Задание 19_20_22(DEMO) пишем программу Phyton

P-01 (демо-2022). Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

Задание 19.

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

Задание 20.

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

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

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

Найденные значения запишите в ответе в порядке возрастания.

Задание 21

Найдите значение S, при котором одновременно выполняются два условия:

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

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

n = 29
def gameResult(s):
    if s>=n:return 0 
    nYes = [gameResult(s+1), gameResult(s*2)] 
    nNo = [i for i in nYes if i<=0] 
    if nNo:res = -max(nNo) + 1
    else:res = -max(nYes)
    return res

# основная программа
results = [(s,gameResult(s)) for s in range(1,n)]
print( '19:', [s for s, r in results if r == -1] )
print( '20:', [s for s, r in results if r == 2] )
print( '21:', [s for s, r in results if r == -2] )

Задание 19_20_22 (Поляков) пишем программу Phyton

Две кучи — варианты решений

Задание 19 (разбираем задание)

Два игрока, Петя и Вася, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

Добавить в одну из куч (по своему выбору) один камень или
Добавить в одну из куч (по своему выбору) удвоенное число камне из другой кучи.

Например, пусть в одной куче 8 камней, а в другой куче 5 камней. Тогда за один ход можем получить четыре позиции: (9, 5); (18, 5); (8, 6); (8, 21).

Для того что бы играть, у игроков есть неограниченное количество камне.

В начальный момент в первой куче было 9 камней, во второй S камней: 1 ≤ S ≤ 67.

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

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

Можно решить с помощью рассуждений:

Если S = 67, то добавив в любую кучу один камень (67+1+9=77), или добавить удвоенную соседнюю кучу в любую из куч (9+(67+2*9)=94 или ((9+2*67)+67=210), Петя становится победителем.
Если S = 66, добавив удвоенную соседнюю кучу в любую из куч (9+(66+2*9)=93 или ((9+2*66)+66=207), Петя становится победителем.
Если S = 65, добавив удвоенную соседнюю кучу в любую из куч (9+(65+2*9)=92 или ((9+2*65)+65=204), Петя становится победителем.
Обратим внимание, если удваиваем 9 камней и добавляем во вторую кучу, уменьшение ровно на 1, поэтому ускорим процесс 92-77=15, 65 -15 =50, идем дальше
Если S = 50, добавив удвоенную соседнюю кучу в любую из куч (9+(50+2*9)=77 или ((9+2*50)+50=159), Петя становится победителем.
У нас остается только один вариант, ускорим процес, усли удваиваем вторую кучу, уменьшение ровно на три, поэтому ускорим процесс 159-77=82, 82/3=27,333, 50-27=23
Если S = 23, добавив удвоенную соседнюю кучу в эту из куч ((9+2*23)+23=78), Петя становится победителем. СТОП!!!

Получили – S>=23 – это ВЫИГРЫШНАЯ ПОЗИЦИЯ,

S<23 будет ПРОИГРЫШНОЙ ПОЗИЦИЕЙ ДЛЯ ЛЮБОГО ИГРОКА.

Известно, что Вася выиграл своим первым ходом, после НЕУДАЧНОГО первого хода Пети.

Неудачный ход – это значит Петя увеличил количество камне увеличив одну из куч удвоенным количеством соседней кучи. Получаем S+2*9 = 23 => S=5

Можно проверить программой:

# 19-----------------------------------
def f(x, y, p):
    if x + y >=77 and p == 3: return True
    else:
        if x + y < 77 and p == 3:return False
    return f(x+1, y, p+1) or f(x, y+1, p+1) or f(x+2*y, y, p+1) or f(x, y+2*x, p+1)

# начинаем перебор для 19 задания
print('19 ответ -', end=' ')
for i in range(1,50+1):
    if f(9, i, 1):
        print(i)
        break

Ответ: 5

Задание 20 (разбираем задание)

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

Найденные значения запишите в ответе в порядке возрастания.

Ответ: 7 22

Задание 21 (разбираем задание)

Найдите значение S, при котором одновременно выполняются два условия:

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

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

Ответ: 21

Три кучи — варианты решений

Задание 19_20_21 (разбираем задание)

(№ 4725) (И. Осипов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в два раза. Например, пусть в первой куче 10 камней, во второй 7, а в третьей 4 камня; такую позицию в игре будем обозначать (10, 7, 4). Тогда за один ход можно получить любую из шести позиций: (13, 7, 4), (20, 7, 4), (10, 10, 4), (10, 14, 4), (10, 7, 7), (10, 7, 8). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 71. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 71 или больше камней. В начальный момент в первой куче было семь камней, во второй куче пять камней, в третьей куче – S камней; 1 ≤ S ≤ 58.
Ответьте на следующие вопросы:
  Вопрос 1.При некотором значении S Ваня одержал победу свои первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором это возможно.
  Вопрос 2. Найдите минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.
  Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия: а) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; б) у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

# --19----------------
def f(x,y,z,p):
    if x + y + z >=71 and p == 3:return True
    else:
        if x + y + z < 71 and p == 3:return False
    return (f(x+3, y, z, p+1) or f(x*2, y, z, p+1) or f(x, y+3, z, p+1) or
            f(x, y*2, z, p+1) or f(x, y, z+3, p+1) or f(x, y, z*2, p+1))
# ------------------------
print('19 ответ:', end=' ')
for i in range(1,58+1):
    if f(7, 5, i, 1):
        print(i)
        break

Ответ: 15

# --20----------------
def f(x,y,z,p):
    if x + y + z >=71 and p == 4:return True
    else:
        if x + y + z < 71 and p == 4:return False
        else:
            if x + y + z>=71:return False
    if p % 2 == 1:
        return (f(x+3, y, z, p+1) or f(x*2, y, z, p+1) or f(x, y+3, z, p+1) or
        f(x, y*2, z, p+1) or f(x, y, z+3, p+1) or f(x, y, z*2, p+1))
    else:
        return (f(x+3, y, z, p+1) and f(x*2, y, z, p+1) and f(x, y+3, z, p+1)
        and f(x, y*2, z, p+1) and f(x, y, z+3, p+1) and f(x, y, z*2, p+1))
# ------------------------
print('20 ответ:', end=' ')
for i in range(1,58+1):
    if f(7, 5, i, 1):
        print(i, end=' ')

Ответ: 14 27

# --21----------------
print()
def f(x,y,z,p):
    if x + y + z >=71 and (p == 3 or p == 5):return True
    else:
        if x + y + z < 71 and p == 5:return False
        else:
            if x + y + z>=71:return False
    if p % 2 == 0:
        return (f(x+3, y, z, p+1) or f(x*2, y, z, p+1) or f(x, y+3, z, p+1) or
        f(x, y*2, z, p+1) or f(x, y, z+3, p+1) or f(x, y, z*2, p+1))
    else:
        return (f(x+3, y, z, p+1) and f(x*2, y, z, p+1) and f(x, y+3, z, p+1)
        and f(x, y*2, z, p+1) and f(x, y, z+3, p+1) and f(x, y, z*2, p+1))
# ------------------------
print('21 ответ:', end=' ')
for i in range(1,58+1):
    if f(7, 5, i, 1):
        print(i, end=' ')
        break

Ответ: 24

Источник

Выиграшная ситуация за четыре хода

(Разбор задания №21 ЕГЭ информатика)

ЕГЭ в 2021 году по информатике включает три задания на нахождение
выигрышной ситуации при игре с кучами камней. Это задание №19 с использованием
двух вариантов хода, задание №20 с использованием трех вариантов хода и задание
№21 с использованием четырех вариантов хода. В данной статье рассматриваются
один из приемов решения задания №21 с использованием четырех вариантов хода.

Рассмотрим способ выбора из всех возможных стратегий самый
оптимальный согласно условия задачи. Пример из демоверсии 2021:

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

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

В начальный момент в первой куче
было семь камней, во второй куче — S камней;
1 ≤ S ≤ 69.

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

Найдите минимальное значение S,
при котором одновременно выполняются два условия:

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

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

Решение:

Заметим, что S должно быть
большим, чем 29. Иначе, игра может не закончиться четвертым ходом (29+1+1=31).
Удвоние камней в куче S победы Ване не принесет и игра может продолжится или
выигрыет Петя. После первого хода Пети возможны ситупции: (8,S), (7,S+1),
(14,S), (7,2S). После хода Вани возможны варианты: I (9,S), (8,S+1), (16, S),
(7, 2S); II (8,S+1), (7,S+2), (14,S+1), (15,S); III (14,S+1), (28,S), (14,2S),
(15,S); IV (8,2S), (7,2S+1), (14,2S), (7,4S);

Если Ваня выигрывает вторым ходом
при любой игре Пети, то ему надо выбрать один из Петиных самых «коварных»
ходов — (7,S+1), (14,S). В противном случае Ваня или выиграет вторым ходом
(путем удваивания) или проиграет Пете после третьего хода. Это позволит
получит однозначно ход (14,S+1). После такого хода Вани у Пети даже удвоением
не получается выиграть. Найдем это число: 14+2S+2 =76. Отсюда S=30. Это и будет
минимальным значением S, при котором Ваня выиграет при любой игре Пети.

Ответ: S=30

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

Игра завершается в тот момент,
когда количество камней в куче становится более 200. Победителем считается
игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет
201 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 200.

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

Найдите минимальное значение S,
при котором одновременно выполняются два условия:

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

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

Заметим, что S должно быть меньше 39, так
как игра может закончиться на третьем ходе (39+1+1=41), Петя увеличивает число
камней в 5 раз и выигрывает, а при еще меньших S Ваня не сможет выиграть даже
увеличением в 5 раз (10+1+22+1=34). После первого хода Пети возможны ситупции:
(S+1) или (5S). Ситуация (S+1) не должна дать возможность выиграть Пете. Ваня
тоже увеличивает число камней в куче на 1. Получился ход (S+2). Петя даже увеличением
количества камней в 5 раз не достигает заветного 201. Находим S из условия:
5(S+2)=200. Отсюда S=38. Заметим, что увеличение числа камней первым ходом
одним из игроков в 5 раз позволит игру закончить быстрее.

Ответ: S=38.

Источник

Информатика. ЕГЭ

Задания для подготовки

Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников

Задания 19-21. Информатика. 2023-1

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

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

В начальный момент в куче было (S) камней, (1 leqslant S leqslant 228).

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

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

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

Найденные значения запишите в ответе в порядке возрастания.

Для игры, описанной в задании 19, найдите минимальное значение (S), при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Показать решение…

Задания 19-21. Информатика. 2023-2

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

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

В начальный момент в куче было (S) камней, (1 leqslant S leqslant 300).

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

Найденные значения запишите в ответе в порядке возрастания.

Показать решение…

Задания 19-21. Информатика. 2023-3

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

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

В начальный момент в куче было (S) камней, (1 leqslant S leqslant 152).

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

Найденные значения запишите в ответе в порядке возрастания.

Показать решение…

Задания 19-21. Информатика. 2023-4

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

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

В начальный момент в куче было (S) камней, (1 leqslant S leqslant 160).

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

Найденные значения запишите в ответе в порядке возрастания.

Показать решение…

Задания 19-21. Информатика. 2023-5

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

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

В начальный момент в куче было (S) камней, (1 leqslant S leqslant 180).

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

Найденные значения запишите в ответе в порядке возрастания.

Показать решение…

Источник

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

Чтобы избежать сложности в объяснении, первый игрок назван именем, начинающимся на «П», обозначая тот факт, что он ходит всегда первым и его ходы в общем счёте игры нечётные. Соответственно, второй игрок назван именем на букву «В», так как его ход ответный — второй и далее все ходы в общем счёте игры чётные.

В задании (20) Первый игрок может сделать не все возможные ходы, а только те, которые через ход приведут его к победе. Это реализация выигрышной стратегии Первого игрока. Выигрышная стратегия подразумевает, что первый ход Пети (Первого игрока) должен быть таким, что все ответные ходы Второго игрока (Вани) приведут Петю к выигрышу.

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

В начальный момент в куче (S) камней, при этом известно, что (1<=S<46).
Укажи такое значение (S), при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанного значения (S) опиши выигрышную стратегию Пети.

Выполним решение вручную.

Из анализа таблицы полной игры определим выигрышное для Пети количество камней, (11).

Зелёным цветом выделены выигрышные ходы Пети. При его первом ходе (11*2) на все ответные ходы Вани у Пети есть ходы, приводящие его к выигрышу.
В электронных таблицах так же организуется вычисление по формулам для полного дерева игры, но значение (S) не вычисляется, а определяется перебором в интервале (1<=S<46), определённым условием задачи.

Рассмотрим на примере задания из Демоверсии (2023)

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

Игра завершается в тот момент, когда количество камней в куче становится не менее (129). Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу из (129) или больше камней.
В начальный момент в куче (S) камней, при этом известно, что (1<=S<=128).

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

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

Найденные значения запиши в порядке возрастания.

Рассмотрим решение в электронных таблицах.

Сформируем таблицу и впишем в неё формулы.

Рис. (1). Формулы

Определим правила для условного форматирования ячеек (в примере показано правило для столбца (C)). Для столбца (D) и (E) правило останется тем же, рекомендуем поменять цвет выделения. Форматирование проводится для трёх столбцов с вычислениями для того, чтобы, контролируя выигрышную сумму, получаемую первым игроком, не пропустить ситуацию, когда первый игрок на своём первом ходу или второй игрок на своём первом ходу уже получит такую сумму и не даст возможности первому игроку выполнить условие задачи.

Рис. (2). Условное форматирование

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

Выигрышная стратегия Пети выделена в таблице.

Рис. (3). Результат (1)

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

Рис. (4). Результат (2)

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

Источники:

Источник

Проверяем значение S0 = 7

Проверяем значение S0 = 12

Проверяем значение S0 = 17

Проверяем значение S0 = 30

Игра с двумя кучами камней или табличка

Задания для тренировки 19, 20, 21 заданий ЕГЭ (взяты из КИМ и сборников прошлых лет)

Игра с одной кучей камней

Игра с набором слов

Немного теории:

Одна куча:

Задание 19

Решение:

Ответ: 5

Задание 20

Ответ: 16 18

Задание 21

Ответ: 15

Задание 19 (самостоятельно)

Задание 20 (самостоятельно)

Задание 21 (самостоятельно)

Задание 19_20_22(DEMO) пишем программу Phyton

Задание 19_20_22 (Поляков) пишем программу Phyton

Две кучи — варианты решений

Задание 19 (разбираем задание)

Можно решить с помощью рассуждений:

Можно проверить программой:

Ответ: 5

Задание 20 (разбираем задание)

Ответ: 7 22

Задание 21 (разбираем задание)

Ответ: 21

Три кучи — варианты решений

Задание 19_20_21 (разбираем задание)

Ответ: 15

Ответ: 14 27

Ответ: 24

Информатика. ЕГЭ

Задания для подготовки

Задания 19-21. Информатика. 2023-1

Задания 19-21. Информатика. 2023-2

Задания 19-21. Информатика. 2023-3

Задания 19-21. Информатика. 2023-4

Задания 19-21. Информатика. 2023-5

Проверяем значение S₀ = 7

Проверяем значение S₀ = 12

Проверяем значение S₀ = 17

Проверяем значение S₀ = 30