Задание 21. Теория Игр. Задание 3. ЕГЭ 2024 по информатике
Средний процент выполнения: 67.8%
Ответом к заданию 21 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S во второй кучке, если в первой 6 камней. При котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 23.
Если начальная позиция (6; 23), Паша может получить одну из четырёх позиций: (7; 23), (12, 23), (6, 24), (6, 46).
Из позиции (6; 46) Влад побеждает за один ход, получив позицию (6; 92).
Из позиций (7; 23), (12, 23), (6, 24) Влад делает позиции (14; 23), (12, 24), (12, 24), соответственно.
Из позиции (14, 23) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 23), (28, 23), (14, 24), (14, 46).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 46), (28, 46), (14, 48), (14, 92).
Из позиции (12, 24) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (13, 24), (24, 24), (12, 25), (12, 48).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (13, 48), (24, 48), (12, 50), (12, 96).
Ответ: 23.
Задача 2
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 23. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 23. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 22.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение S: 8. После первого хода Паши в куче будет или 9, или 10, или 16 камней. Если в куче станет 16 камней, Влад удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 10 или 9 камней, разобрана в 20-ом задании. В этой ситуации игрок, который будет ходить (теперь это Влад), выигрывает своим вторым ходом. В таблице изображено дерево возможных партий при описанной стратегии Влада. Заключительные позиции (в них выигрывает Влад) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Паши (разобраны все ходы) | 1-й ход Влада (только ход по стратегии) | 2-й ход Паши (разобраны все ходы) | 2-й ход Влада (только ход по стратегии) | |
| 8 | 8+1=9 | 9 + 2 = 11 | 11 + 1 = 12 | 12 · 2 = 24 |
| 11 + 2 = 13 | 13 · 2 = 26 | |||
| 11 · 2 = 22 | 22 · 2 = 44 | |||
| 8 + 2 = 10 | 10 + 1 = 11 | 11 + 1 = 12 | 12 · 2 = 24 | |
| 11 + 2 = 13 | 13 · 2 = 26 | |||
| 11 · 2 = 22 | 22 · 2 = 44 | |||
| 8 · 2 = 16 | 16 · 2 = 32 | |||
Задача 3
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 41. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 41. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 40.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение S: 17. После первого хода Паши камней в куче будет или 18, или 19, или 34. Если в куче станет 34 камня, Влад удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 18 или 19 камней, разобрана в 20 задании. В этой ситуации игрок, который будет ходить (теперь это Влад), выигрывает своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Влада. Заключительные позиции (в них выигрывает Влад) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Паши (разобраны все ходы) | 1-й ход Влада (только ход по стратегии) | 2-й ход Паши (разобраны все ходы) | 2-й ход Влада (только ход по стратегии) | |
| 17 | 17 + 1 = 18 | 18 + 2 = 20 | 20 + 1 = 21 | 21 · 2 = 42 |
| 20 + 2 = 22 | 22 · 2 = 44 | |||
| 20 · 2 = 40 | 40 · 2 = 80 | |||
| 17 + 2 = 19 | 19 + 1 = 20 | 20 + 1 = 21 | 21 · 2 = 42 | |
| 20 + 2 = 22 | 22 · 2 = 44 | |||
| 20 · 2 = 40 | 40 · 2 = 80 | |||
| 17 · 2 = 34 | 34 · 2 = 68 | |||
Задача 4
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче один камень.
2. Увеличить количество камней в куче в три раза.
Например, если в куче лежит 5 камней, то из этой позиции за один ход можно получить 6 или 15 камней.
Игра завершается, когда количество камней в куче становится не менее 109. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче превысит 108 камней. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 108.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее число — 34.
При таком начальном значении Паша может получить 35 или 102. Из 102 Влад выиграет первым ходом, а значение 35, можно свести в значение 36.
Паша может получить 37 или 108. Из этих двух значений выиграет Влад.
Задача 5
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче два камня.
2. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 32. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 32. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 28.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение S: 10. После первого хода Паши камней в куче будет или 12, или 20. Если в куче станет 20 камней, Влад удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 12 камней, разобрана в 20 задании. В этой ситуации игрок, который будет ходить (теперь это Влад), выигрывает своим вторым ходом.
Задача 6
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 77. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 77. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 7 камней, а во второй S, где 1 ≤ S ≤ 69.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 30.
Если начальная позиция (7; 30), Паша может получить одну из четырёх позиций: (8; 30), (14, 30), (7, 31), (7, 60).
Из позиции (7; 60) Влад побеждает за один ход, получив позицию (7; 120).
Из позиций (8; 30), (14, 30), (7, 31) Влад делает позиции (16; 30), (14, 31), соответственно.
Из позиции (16, 30) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (17, 30), (32, 30), (16, 31), (16, 60).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (17, 60), (64, 60), (16, 62), (16, 120).
Из позиции (14, 31) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 31), (28, 31), (14, 32), (14, 62).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 62), (28, 62), (14, 64), (14, 124).
Ответ: 30.
Задача 7
Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежит набор слов, составленных из букв русского алфавита, при этом одно слово не является началом другого слова. Под словом подразумевается просто набор букв русского языка. Игра состоит в том, что игроки составляют слово из набора, приписывая по очереди буквы к концу составляемого слова, т.е. справа. При этом каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получит одно из заданных слов целиком. Первый ход делает Петя, т.е. Петя пишет первую букву составляемого слова.
Пример. Заданный набор слов: {АНАКОНДА, АПЕЛЬСИН, БОБ, БАКЛАЖАН, БАР}.
Первым ходом Петя пишет Б (он мог написать Б или А).
Ваня в ответ дописывает А и получает БА (он мог ещё получить БО).
Вторым ходом Петя получает БАР и выигрывает.
Одну букву поменяйте местами с другой буквой в более коротком слове так, чтобы теперь выигрышная стратегия была у другого игрока {КУХГНКУХГНХ, НГХУКНГХУН, КУХГНКУХГНЮЖ}. В ответе укажите изменённое слово
Решение
Самое короткое слово НГХУКНГХУН, нужно поменять местами первую букву с буквой К, тогда получим слово: КГХУННГХУН
Задача 8
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит несколько фишек. Игроки ходят по очереди, первый ход делает Петя и он просто кладёт фишку на игровое поле. За любой следующий один ход игрок может положить фишку на игровое поле справа от уже лежавшей на нём, при этом последняя цифра числа на фишке, которая уже лежит на столе, должна совпадать с первой цифрой числа фишки, которую собираются положить. Фишки нельзя поворачивать. Игра завершается в тот момент, когда нельзя будет положить фишку на игровое поле. Победителем считается игрок, сделавший последний ход.
Например, имея фишки 11, 14, 22, 23, 24 и 42, может быть следующая игра:
Петя кидает число 11, тогда Ваня выложит фишку 14, тогда Петя может положить фишку 42, а Ваня выложит 23 или 24 и выиграет, т.к. больше нет фишек, которые начинаются с 3 или 4.
Дан набор фишек: 11, 12, 13, 21, 22, 23, 31, 33
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Сколько существует фишек, начиная с которых выигрывает Петя?
Решение
Из фишки 33 выигрывает Петя.
Из 13 Ваня.
Если в начале игры Петя выложит 11, то у Вани есть ходы 12 и 13. Число 12 Петя сведёт в 21 и выиграет через 1 ход. А 13 в 31 и тоже выиграет через 1 ход.
Мы нашли 2 фишки. 11 и 33.
Если в начале игры Петя выложил 12, то у Вани есть ходы: 21, 22, 23. Ваня походит 22, то Петя пойдёт 21 или 23, тогда Ваня сведёт всё к 11 или 33 и выиграет через 1 ход.
Если в начале Петя выложит 21, то Ваня сможет походить в 11, 12 или 13. Но Ваня сведёт игру в число 11 и выиграет через 3 хода.
Если Петя выложит 22, то у Вани есть ходы 21 и 23. 21 Петя сводит в 12, тогда Ваня пойдёт 23, а Петя 33. У Вани останется только ход 31 и Петя выиграет ходом 13.
23 Петя сводит в 33, тогда у Вани есть только ход 31, и Петя выиграет числом 13.
Мы нашли уже 3 фишки: 11, 22 и 33.
Проверим 23. Но тут выиграет Ваня. Как и с числом 13. 23 — 33 — 31 — 13
Задача 9
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 69. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 69. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 62.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 27.
Если начальная позиция (6; 27), Паша может получить одну из четырёх позиций: (7; 27), (12, 27), (6, 28), (6, 54).
Из позиции (6; 54) Влад побеждает за один ход, получив позицию (6; 108).
Из позиций (7; 27), (12, 27), (6, 28) Влад делает позиции (14; 27), (12, 28), (12, 28), соответственно.
Из позиции (14, 27) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 27), (28, 27), (14, 28), (14, 54).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 54), (28, 54), (14, 56), (14, 108).
Из позиции (12, 28) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (13, 28), (24, 28), (12, 29), (12, 56).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (13, 56), (24, 56), (12, 58), (12, 112).
Ответ: 27.