Задание 20. Теория Игр. Задание 2. ЕГЭ 2024 по информатике
Средний процент выполнения: 51.9%
Ответом к заданию 20 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче два камня.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (10; 7), (7; 7), (5, 9) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 100. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 100. У игроков неограниченное количество камней для ходов.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, для начальной позиции (10; 42) укажите, кто из игроков имеет выигрышную стратегию. Укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. В ответе укажите имя игрока и количество ходов без пробелов и разделителей, например, «Влад3».
Решение
Для начальной позиции (10; 42) выигрывает Паша своим вторым ходом.
Чтобы выиграть, Паша должен после своего хода получить позицию (10; 44). Для этого он должен увеличить на 2 число камней либо во второй куче. Считая позицию (10; 44) начальной, мы приходим к рассмотрению ситуации задания 19.
Как уже было показано ранее, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Паша своим вторым ходом.
Задача 2
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 23. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 23. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 22.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 10 и 9. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу 1 или 2 камня, он может получить кучу из 11 камней. Эта позиция разобрана в 19-ом задании. Если в куче 11 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 3
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 41. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 41. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 40.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два наибольших значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 19 и 18. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу 1 или 2 камня, он может получить кучу из 20 камней. Эта позиция разобрана в 19 задании. Если в куче 20 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 4
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче один камень.
2. Увеличить количество камней в куче в три раза.
Например, если в куче лежит 5 камней, то из этой позиции за один ход можно получить 6 или 15 камней.
Игра завершается, когда количество камней в куче становится не менее 109. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче превысит 108 камней. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 108.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 12 и 35. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу с 35 камнями 1 камень или утроив кучу из 12 камней, он может получить кучу из 36 камней. Эта позиция разобрана в задании 19. Если в куче 36 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 5
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче два камня.
2. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 32. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 32. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 28.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два наименьших значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 12 и 7. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу с 12 камнями 2 камня или удвоив кучу из 7 камней, он может получить кучу из 14 камней. Эта позиция разобрана в задании 19.
Если в куче 14 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 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, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 31 и 34.
Если начальная позиция (7; 31), Паша увеличивает количество камней в первой куче в два раза и получает позицию (14; 31).
Из позиции (14; 31) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (15; 31), (28, 31), (14, 32), (14, 62).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (15; 62), (28, 62), (14, 63), (14, 124).
Если начальная позиция (7; 34), Паша увеличивает количество камней в первой куче на один и получает позицию (8; 34).
Из позиции (8; 34) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (9; 34), (16, 34), (8, 35), (8, 68).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (9; 68), (16, 68), (8, 70), (8, 136).
Ответ: 3134.
Задача 7
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 14 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 84.
Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 84 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 72.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите два таких значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
— Паша не может выиграть за один ход;
— Паша может выиграть своим вторым ходом независимо от того, как будет ходить Валя.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Решение
Решение при помощи программы на С++:
bool comp(int a, int b) {return a < b;};
int main() {
int S[84]; // тут задаётся мин. значение для выигрыша
for (int i = 0; i < 84; ++i)
if (i < 17) // при каком наим. S можно выиграть за один ход? 84/5
S[i] = 0;
else
S[i] = 1; // выигрыш за один ход
for (int z = 0; z < 50; ++z)
for (int i = 0; i < 84; ++i) {
// если ещё не обработана позиция
if (S[i] == 0)
// если любым ходом попадает в выигрышную позицию для второго игрока
if (S[i + 1] > 0 && S[i + 4] > 0 && S[i * 5] > 0)
S[i] = max({S[i + 1], S[i + 4], S[i * 5]}, comp) * -1;
// если одним из ходов может перевести в проигрышную позицию для второго игрока
else if (S[i + 1] < 0 || S[i + 4] < 0 || S[i * 5] < 0)
S[i] = max({abs(S[i + 1]), abs(S[i + 4]), abs(S[i * 5])}, comp) + 1;
}
return 0;
}
Нас интересуют позиции, в которых находится значение 2, что означает: игрок, ходящий первым, выигрывает за 2 хода. Для этого запускаем цикл:
for (int i = 0; i < 84; ++i)
if (S[i] == 2)
cout << i << " ";
Программа выдаст ответ: 12 15
Задача 8
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 24 и 26.
Если начальная позиция (6; 24), Паша увеличивает количество камней в первой куче в два раза и получает позицию (12; 24).
Из позиции (12; 24) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (13; 24), (24, 24), (12, 25), (12, 48).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (13; 48), (24, 48), (12, 50), (12, 96).
Если начальная позиция (6; 26), Паша увеличивает количество камней во второй куче на один и получает позицию (6; 27).
Из позиции (6; 27) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (7; 27), (12, 27), (6, 28), (6, 54).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (7; 54), (12, 54), (6, 56), (6, 108).
Решение при помощи прграммы на С++
int main() {
int S[100][100]; // тут задаётся мин. значение для выигрыша
for (int i = 0; i < 100; ++i)
for (int j = 0; j < 100; ++j)
// при каком наим. S можно выиграть за один ход? 84/5
if (i*2 + j >= 61 || i + j*2 >= 61) // выигрыш за один ход
S[i][j] = 1;
else
S[i][j] = 0;
for (int z = 0; z < 50; ++z)
for (int i = 0; i < 100; ++i)
for (int j = 0; j < 100; ++j) {
// если ещё не обработана позиция
if (S[i][j] == 0)
// если любым ходом попадает в выигрышную позицию для второго игрока
if (S[i + 1][j] > 0 && S[i * 2][j] > 0
&& S[i][j + 1] > 0 && S[i][j * 2] > 0)
S[i][j] = max({S[i + 1][j], S[i * 2][j], S[i][j + 1], S[i][j * 2]}, comp) * -1;
// если одним из ходов может перевести в проигрышную позицию для второго игрока
else if (S[i + 1][j] < 0 || S[i * 2][j] < 0 || S[i][j + 1] < 0 || S[i][j * 2] < 0)
S[i][j] = abs(min({S[i + 1][j], S[i * 2][j], S[i][j + 1], S[i][j * 2]}, comp)) + 1;
}
cout << "№20) ";
for (int i = 1; i < 54; ++i) {
if (S[6][i] == 2)
cout << i << " ";
}
cout << endl << "№21) ";
for (int i = 1; i < 54; ++i) {
if (S[6][i] == -2)
cout << i << " ";
}
return 0;
}
Программа выведет:
№20) 24 26
№21) 23
Ответ: 2426.
Задача 9
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 83. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 83. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 9 камней, а во второй S, где 1 ≤ S ≤ 73.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 32 и 36.
Если начальная позиция (9; 32), Паша увеличивает количество камней в первой куче в два раза и получает позицию (18; 32).
Из позиции (18; 32) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (19; 32), (36, 32), (18, 33), (18, 64).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (19; 64), (36, 64), (18, 66), (18, 128).
Если начальная позиция (9; 36), Паша увеличивает количество камней в первой куче на один и получает позицию (10; 36).
Из позиции (10; 36) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (11; 36), (20, 36), (10, 37), (10, 72).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (11; 72), (20, 72), (10, 74), (10, 144).
Ответ: 3236.