ЕГЭ по информатике 2021 - Задание 21 (Игроки в игре!)

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

+1	+3	*2
2*S0 + 4 ≥ 33 2*S0 ≥ 29 S0 ≥ 15	2*S0 + 6 ≥ 33 2*S0 ≥ 27 S0 ≥ 14 (Округляем в большую сторону)	4*S0 + 6 ≥ 33 4*S0 ≥ 27 S0 ≥ 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a+1+b	a + b+1	2*a + b	a + 2*b
2*S0 + 10 ≥ 77 2*S0 ≥ 67 S0 ≥ 34 (Округляем в большую сторону)	2*S0 + 10 ≥ 77 2*S0 ≥ 67 S0 ≥ 34 (Округляем в большую сторону)	2*S0 + 18 ≥ 77 2*S0 ≥ 59 S0≥30 (Округляем в большую сторону)	4*S0 + 9 ≥ 77 4*S0 ≥ 68 S0 ≥ 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