09074E — Игры и выигрышные стратегии: ответ и решение

Дайте развернутый ответ.

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 60.

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

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

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

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

Задание 1

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

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

Задание 2

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

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

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

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

Задание 3

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

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

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

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

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

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

СВОЙСТВА ЗАДАНИЯ

КЭС:

2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа)

2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира

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

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

3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве

3.11 Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива

3.12 Словари (ассоциативные массивы, отображения). Хэш-таблицы. Построение алфавитно-частотного словаря для заданного текста

3.13 Стеки. Анализ правильности скобочного выражения. Вычисление арифметического выражения, записанного в постфиксной форме. Очереди. Использование очереди для временного хранения данных

3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры

3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева

Тип ответа:

Развернутый ответ

Номер: 09074E

Статус задания: НЕ РЕШЕНО Изменить статус

Решение задания EGEINF09074E

Ответ: 1а) 30–59; 1б) 28; 2) 14, 25, 26, 27; 3) 23

Решение.
Позиция задаётся числом камней или упорядоченной парой чисел. Первый ход делает Петя; затем игроки чередуются. Игра заканчивается сразу после достижения порога 60.
Разрешено прибавить 2, 3 к одной куче или умножить число камней в ней на 2. Порог проверяется по суммарному числу камней.
Для анализа идём от завершённых позиций назад. Позиция выигрышная, если есть хотя бы один ход в проигрышную для соперника. Позиция проигрышная, если все её ходы ведут в выигрышные. Все числа при ходе увеличиваются, поэтому такой обратный разбор заканчивается.
В1 означает победу текущего игрока одним ходом. П1 — отсутствие немедленной победы, причём каждый ход отдаёт сопернику В1. В2 — отсутствие выигрыша одним ходом, но есть переход в П1. П2 — каждый ход отдаёт В1 или В2, при этом хотя бы один отдаёт В2.
Разрешённая область: 1 ≤ S ≤ 59. Начальная позиция — куча из S камней.
Задание 1а. Немедленная победа возможна при S = 30–59. Для каждого из этих значений достаточно умножить число камней на 2.
На предыдущей границе S = 29 результаты всех команд: 31, 32, 58; каждый меньше 60. При меньших S результаты ещё меньше. На границе S = 30 умножение даёт 60 ≥ 60, а при больших S результат не уменьшается.
Обратная классификация всех начальных позиций даёт П1: 28, 29; В2: 14, 25, 26, 27; П2: 23, 24.
Задание 1б. Возьмём S = 28.
Из позиции 28 выигрывает Ваня.
Таблица содержит все партии при выбранной стратегии. В столбце указаны игрок и номер его собственного хода, в клетке — позиция после этого хода. После конечной позиции игра прекращается; прочерк означает, что следующего хода уже нет.

№	Начало	Петя 1	Ваня 1
1	28	30	60
2	28	31	62
3	28	56	112

В выигрышных вершинах оставлен один выбранный ход, в вершинах соперника перечислены все допустимые продолжения. Поэтому это дерево стратегии, охватывающее любую игру соперника.
Задание 2. Выберем S = 14, 25, 26, 27.
Из позиции 14 выигрывает Петя.
Таблица содержит все партии при выбранной стратегии. В столбце указаны игрок и номер его собственного хода, в клетке — позиция после этого хода. После конечной позиции игра прекращается; прочерк означает, что следующего хода уже нет.

№	Начало	Петя 1	Ваня 1	Петя 2
1	14	28	30	60
2	14	28	31	62
3	14	28	56	112

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

№	Начало	Петя 1	Ваня 1	Петя 2
1	25	28	30	60
2	25	28	31	62
3	25	28	56	112

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

№	Начало	Петя 1	Ваня 1	Петя 2
1	26	28	30	60
2	26	28	31	62
3	26	28	56	112

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

№	Начало	Петя 1	Ваня 1	Петя 2
1	27	29	31	62
2	27	29	32	64
3	27	29	58	60

В выигрышных вершинах оставлен один выбранный ход, в вершинах соперника перечислены все допустимые продолжения. Поэтому это дерево стратегии, охватывающее любую игру соперника.
Задание 3. Выберем S = 23.
Из позиции 23 выигрывает Ваня.
Таблица содержит все партии при выбранной стратегии. В столбце указаны игрок и номер его собственного хода, в клетке — позиция после этого хода. После конечной позиции игра прекращается; прочерк означает, что следующего хода уже нет.

№	Начало	Петя 1	Ваня 1	Петя 2	Ваня 2
1	23	25	28	30	60
2	23	25	28	31	62
3	23	25	28	56	112
4	23	26	28	30	60
5	23	26	28	31	62
6	23	26	28	56	112
7	23	46	92	—	—

В выигрышных вершинах оставлен один выбранный ход, в вершинах соперника перечислены все допустимые продолжения. Поэтому это дерево стратегии, охватывающее любую игру соперника.
В деревьях задания 2 Петя завершает игру своим вторым ходом. В задании 3 Ваня завершает любую партию первым или вторым своим ходом; хотя бы одна ветвь требует второго хода. По классификации П2 гарантированной победы Вани первым ходом нет.
Проверка: все переходы в перечисленных партиях являются разрешёнными командами, промежуточные позиции не заканчивают игру, а каждый лист достигает требуемого порога. Чётность последнего хода совпадает с указанным победителем. Все ответы соперника включены, поэтому стратегия гарантирует результат.
Ответ: 1а) 30–59; 1б) 28; 2) 14, 25, 26, 27; 3) 23.

Задание EGEINF09074E: Игры и выигрышные стратегии

Решение задания EGEINF09074E

Помочь улучшить сайт

Комментарии к решению

№	Начало	Петя 1	Ваня 1	Петя 2	Ваня 2
1	23	25	28	30	60
2	23	25	28	31	62
3	23	25	28	56	112
4	23	26	28	30	60
5	23	26	28	31	62
6	23	26	28	56	112
7	23	46	92	—	—

№	Начало	Петя 1	Ваня 1	Петя 2	Ваня 2
1	23	25	28	30	60
2	23	25	28	31	62
3	23	25	28	56	112
4	23	26	28	30	60
5	23	26	28	31	62
6	23	26	28	56	112
7	23	46	92	—	—

№	Начало	Петя 1	Ваня 1	Петя 2	Ваня 2
1	23	25	28	30	60
2	23	25	28	31	62
3	23	25	28	56	112
4	23	26	28	30	60
5	23	26	28	31	62
6	23	26	28	56	112
7	23	46	92	—	—