Бесплатный интенсив по информатике
3 огненных вебинара, домашние задания, беседа курса, личный кабинет, связь с преподавателем и
многое другое.
Курс стартует 25 марта.
Подробнее об интенсиве
Задание 19. Теория Игр. Задание 1. ЕГЭ 2024 по информатике
Средний процент выполнения: 38.6%
Ответом к заданию 19 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Укажите минимальное значение S, при котором Влад может выиграть своим первым ходом после неудачного хода Паши.
Решение
Чтобы найти минимальное значение, будет делать ходы, увеличивающие количество камней в кучах в как можно большее количество раз. Самый подходящий ход для этих целей - "Умножить на 2".
Для начальной позиции (6;S) возможны два варианта: S < 6, тогда выгоднее умножать шестёрку (происходит более быстрый рост), и S ≥ 6, тогда выгоднее умножать S. Рассмотрим первый вариант:
Неудачный ход Паши: (6;S) -> (12;S).
Ход Влада: (12;S) -> (24;S) - здесь Влад должен победить, значит 24+S ≥ 61.
S ≥ 37. Наименьшее значение - 37, что противоречит условию S < 6.
Рассмотрим второй вариант:
Неудачный ход Паши: (6; S) -> (6; 2S)
Ход Влада: (6; 2S) -> (6; 4S) - здесь Влад должен победить, значит 6+4S ≥ 61
S ≥ 13.75. Наименьшее значение - 14.
Ответ: 14.
Задача 2
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 23. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 23. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 22.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Укажите такое значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Влад может выиграть своим первым ходом.
Решение
Влад может выиграть первым ходом (как бы ни играл Паша), если исходно в куче будет S = 11 камней. Тогда после первого хода Паши в куче будет или 12 камней, или 13 камней, или 22 камня. В любом случае Владу достаточно удвоить количество камней и выиграть своим первым ходом.
Задача 3
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 41. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 41. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 40.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Укажите такое значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Влад может выиграть своим первым ходом.
Решение
Влад может выиграть первым ходом (как бы ни играл Паша), если исходно в куче будет S = 20 камней. Тогда после первого хода Паши в куче будет или 21 камень, или 22 камня, или 40 камней. В любом случае Владу достаточно удвоить количество камней и выиграть своим первым ходом.
Задача 4
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче два камня.
2. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 32. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 32. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 28.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Укажите такое наименьшее значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Влад может выиграть своим первым ходом.
Решение
Влад может выиграть первым ходом (как бы ни играл Паша), если исходно в куче будет S = 14 камней. Тогда после первого хода Паши в куче будет или 16 камней, или 28 камней. В любом случае Владу достаточно удвоить количество камней и выиграть своим первым ходом.
Ответ: 14.
Задача 5
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит несколько фишек. Игроки ходят по очереди, первый ход делает Петя и он просто кладёт фишку на игровое поле. За любой следующий один ход игрок может положить фишку на игровое поле справа от уже лежавшей на нём, при этом последняя цифра числа на фишке, которая уже лежит на столе, должна совпадать с первой цифрой числа фишки, которую собираются положить. Фишки нельзя поворачивать. Игра завершается в тот момент, когда нельзя будет положить фишку на игровое поле. Победителем считается игрок, сделавший последний ход.
Например, имея фишки 11, 14, 22, 23, 24 и 42, может быть следующая игра:
Петя кидает число 11, тогда Ваня выложит фишку 14, тогда Петя может положить фишку 42, а Ваня выложит 23 или 24 и выиграет, т.к. больше нет фишек, которые начинаются с 3 или 4.
Дан набор фишек: 11, 12, 13, 21, 22, 23, 31, 33
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Для набора фишек, указанных в условии. Укажите начальное значение фишки, при котором Петя выиграет своим втором ходом.
Решение
Если Петя выкинет 33, то Ваня сможет выложить только 31. Тогда Пете достаточно выложить число 13 и выиграть, т.к. больше нет фишек, которые начинаются с 3.
Задача 6
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 14 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 84.
Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 84 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 72.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Известно, что Валя выиграл своим первым ходом после неудачного первого хода Паши. Укажите минимальное значение S, когда такая ситуация возможна.
Решение
Проще решить руками. Неудачный ход Паши = он поддался Вале своим первым ходом, то есть перевёл игру в одну из позиций, из которой игрок сможет выиграть за 1 ход - это позиции S=17..72 и игроку останется только увеличить количество камней в куче в 5 раз, чтобы выиграть. Минимальная такая позиция = 17 / 5 = 3.4 округляем до 4.
Задача 7
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Укажите минимальное значение S, при котором Влад может выиграть своим первым ходом после неудачного хода Паши.
Решение
Чтобы найти минимальное значение, будет делать ходы, увеличивающие количество камней в кучах в как можно большее количество раз. Самый подходящий ход для этих целей - "Умножить на 2".
Для начальной позиции (6;S) возможны два варианта: S < 6, тогда выгоднее умножать шестёрку (происходит более быстрый рост), и S ≥ 6, тогда выгоднее умножать S. Рассмотрим первый вариант:
Неудачный ход Паши: (6;S) -> (12;S).
Ход Влада: (12;S) -> (24;S) - здесь Влад должен победить, значит 24+S ≥ 61.
S ≥ 37. Наименьшее значение - 37, что противоречит условию S < 6.
Рассмотрим второй вариант:
Неудачный ход Паши: (6; S) -> (6; 2S)
Ход Влада: (6; 2S) -> (6; 4S) - здесь Влад должен победить, значит 6+4S ≥ 61
S ≥ 13.75. Наименьшее значение - 14.
Ответ: 14.
Задача 8
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 57. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 57. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 5 камней, а во второй S, где 1 ≤ S ≤ 51.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Укажите минимальное значение S, при котором Влад может выиграть своим первым ходом после неудачного хода Паши.
Решение
Чтобы найти минимальное значение, будем делать ходы, увеличивающие количество камней в кучах в как можно большее количество раз. Самый подходящий ход для этих целей - "Умножить на 2".
Для начальной позиции (5;S) возможны два варианта: S < 5, тогда выгоднее умножать пятёрку (происходит более быстрый рост), и S ≥ 5, тогда выгоднее умножать S. Рассмотрим первый вариант:
Неудачный ход Паши: (5;S) -> (10;S).
Ход Влада: (10;S) -> (20;S) - здесь Влад должен победить, значит 20+S ≥ 57.
S ≥ 37. Наименьшее значение - 37, что противоречит условию S < 5.
Рассмотрим второй вариант:
Неудачный ход Паши: (5; S) -> (5; 2S)
Ход Влада: (5; 2S) -> (5; 4S) - здесь Влад должен победить, значит 5+4S ≥ 57
S ≥ 13. Наименьшее значение - 13.
Ответ: 13.
