Понятие выигрышной стратегии.
Выигрышные и проигрышные позиции
· все позиции в простых играх делятся на выигрышные и проигрышные;
· выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, обязательно выиграет при любых действиях соперника, если не допустит ошибки; при этом говорят, что у данного игрока есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть;
· если игрок, делающий первый ход, находится в проигрышной позиции, то он обязательно проиграет, если ошибку не сделает его оппонент; в этом случае говорят, что у данного игрока нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для оппонента;
· выигрышные и проигрышные позиции характеризуются так:
o позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная;
o позиция, из которой хотя бы один из последующих возможных ходов ведет в проигрышную позицию — выигрышная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для оппонента) позицию.
Задание № 26 направлено на проверку умений построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию.
Типичные ошибки в выполнении задания № 26: - отсутствие у экзаменуемого представления о выигрышной стратегии игры, как наборе правил, в соответствии с которыми выигрывающий игрок должен отвечать на любой допустимый ход противника. Отсюда берутся неверные ответы, представляющие зачастую просто один или несколько вариантов развития игры без требуемого анализа и обоснования; - строятся все возможные варианты игры, а не только выигрышная стратегия, как того требует задание; - при выполнении третьего задания экзаменуемые не строят дерево всех партий выигрышной стратегии, а ссылаются на построения (таблицы, выводы и т.д.), выполненные в заданиях 1 и 2
- невнимательное чтение условия приводит к неверному пониманию задания и его решению, например, решается задача для каждой кучки отдельно
Разбор задания № 26 демонстрационной версии ЕГЭ-2020
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат
две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один
ход игрок может добавить в одну из куч (по своему выбору) один камень
или увеличить количество камней в куче в три раза. Например, пусть в
одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем
обозначать (10, 7). Тогда за один ход можно получить любую из четырёх
позиций:
(11, 7), (30, 7), (10, 8), (10, 21). Для того чтобы делать ходы, у каждого
игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах
становится не менее 68. Победителем считается игрок, сделавший
последний ход, т.е. первым получивший такую позицию, при которой в
кучах будет 68 или больше камней.
В начальный момент в первой куче было 6 камней, во второй куче –
S камней; 1 ≤ S ≤ 61.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может
выиграть за один ход.
б) Известно, что Ваня выиграл своим первым ходом после неудачного
первого хода Пети. Укажите минимальное значение S, когда такая
ситуация возможна.
Задание 2
Укажите такое значение S, при котором у Пети есть выигрышная стратегия,
причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
−Петя может выиграть своим вторым ходом независимо от того, как
будет ходить Ваня.
Для указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно
выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии
Вани (в виде рисунка или таблицы).
В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать
ходы. Дерево не должно содержать партии, невозможные при реализации
выигрывающим игроком своей выигрышной стратегии. Например, полное
дерево игры не является верным ответом на это задание.
Решение:
Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 6, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 61:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
17 |
18 |
19 |
20 |
21.. |
|
60 |
61 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1а) Возможные ходы Пети:
1. (6+1;S) Тогда
7+S<=68 S>=61
2. (6;S+1)
3.
(6*3;S) 18+S<=68 
S>=50
4.
(6;3*S)
6+3*S<=68 S>=21
Значит если во второй куче будет начиная с 21 до 61 камней, то Петя выиграет своим первым ходом умножив количество камней второй кучи на 3. Давайте обозначим в таблице выигрышную позицию буквой «в»(первым ходом).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
17 |
18 |
19 |
20 |
21.. |
|
60 |
61 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
Ответ: 1а) Петя может выиграть при 21<=S<=61
1б) Давайте решим перебором. Возможные варианты ходов Пети и Вани:
Петя Ваня
(6+1,S)
(7+1,S) Тогда 8+S
>=68 S>=60
(6,S+1)
(7*3,S) 21+S>=68 S>=47
(7,3*S) 7+3*S>=68 S>=21
(3*6,S) (18+1,S) 19+S>=68
S>=49
(18*3,S) 54+S>=68 S>=14
(18,3*S) 18+3*S>=68 S>=17
(6,3*S) (6+1,3*S)
7+3*S>=68 S>=21
(6,9*S) 6+9*S>=68 S>=7
(6*3,3*S) 18+3*S>=68 S>=17
Значит Ответ:1б) S=7
Задание 2 Проанализируем таблицу, увеличивая количество камней в первой куче и выполняя поиск выигрышных(в) и проигрышных(п) позиций с одного хода:
|
|
|
|
|
|
|
|
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21.. |
|
60 |
61 |
|
6 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
п |
|
в |
в |
в |
в |
|
7 |
|
|
|
|
|
|
п |
|
п |
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
|
8 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
|
9 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
|
10 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
|
11 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
|
12 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
|
13 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
|
14 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
в |
|
15 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
в |
|
16 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
в |
|
17 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
в |
в |
|
18 |
|
|
|
|
|
|
п |
п |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
|
19 |
|
|
|
|
|
|
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
Обратим внимание, что в таблице, все образовавшиеся «уголки» являются проигрышными позициями (с 1-го хода). то есть если игрок, оказывается в такой позиции, то он может выполнить ход только в выигрышные позиции (то есть следующим ходом выиграет соперник)
Петя сможет выиграть своим вторым ходом, когда своим первым ходом он попадет в проигрышную позицию, т.е. переведет соперника в проигрышную ситуацию(Обозначены зеленым цветом). Из них нам подходят такие значения: 1)S = 20 т.е. (6,20) Первый ход Пети- добавить один камень в первую кучу. После чего Ваня попадает в проигрышную ситуацию.2)S=13 т.е (6,13) Первый ход Пети – Умножить количество камней первой кучи на 3. После чего Ваня также попадает в проигрышную ситуацию.
Ответ: S=20 В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию (7, 20). После хода Вани
может возникнуть одна из четырёх позиций: (8, 20), (21, 20), (7, 21), (7, 60).
В каждой из этих позиций Петя может выиграть одним ходом, утроив
количество камней во второй куче.
S=13 Первый ход Пети: утроить первую кучу (18,13) .После хода Вани
может возникнуть одна из четырёх позиций: (19, 13), (54,13), (18,14), (18,39).
В каждой из этих позиций Петя может выиграть одним ходом, утроив
количество камней во первой куче.
Задание 3 Ваня сможет выиграть своим первым или вторым ходом, когда Петя своим первым ходом может попасть только либо в позицию выигрышную с первого хода, либо в позицию выигрышную со второго хода .
|
|
|
|
|
|
|
|
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21.. |
|
60 |
61 |
|
6 |
|
|
|
|
|
|
п |
п |
п |
п |
п |
п |
п |
|
п |
в |
в |
в |
в |
|
7 |
|
|
|
|
|
|
|
|
|
|
|
п |
п |
п |
п |
в |
в |
в |
в |
|
8 |
|
|
|
|
|
|
|
|
|
|
|
п |
п |
п |
в |
в |
в |
в |
в |
|
9 |
|
|
|
|
|
|
|
|
|
|
|
п |
|
п |
в |
в |
в |
в |
в |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
п |
|
п |
в |
в |
в |
в |
в |
|
11 |
|
|
|
|
|
|
|
|
|
|
|
п |
п |
в |
в |
в |
в |
в |
в |
|
12 |
|
|
|
|
|
|
|
|
|
|
|
п |
п |
в |
в |
в |
в |
в |
в |
|
13 |
|
|
|
|
|
|
|
|
|
|
|
п |
п |
в |
в |
в |
в |
в |
в |
|
14 |
|
|
|
|
|
|
|
|
|
|
|
п |
в |
в |
в |
в |
в |
в |
в |
|
15 |
|
|
|
|
|
|
|
|
|
|
|
п |
в |
в |
в |
в |
в |
в |
в |
|
16 |
|
|
|
|
|
|
|
п |
п |
|
п |
п |
в |
в |
в |
в |
в |
в |
в |
|
17 |
|
|
|
|
|
|
|
п |
п |
п |
п |
в |
в |
в |
в |
в |
в |
в |
в |
|
18 |
|
|
|
|
|
|
п |
п |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
|
19 |
|
|
|
|
|
|
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
в |
Это позиции окрашены в зеленый и синий цвет.
Но так как у Вани нет стратегии, которая позволит ему гарантированно выиграть
первым ходом. То остаются позиции, окрашенные в синий цвет. Из них нам подходит, когда S=19.
После первого хода Пети возможны позиции:
(7, 19), (18, 19), (6, 20), (6, 57). В позициях (18, 19) и (6, 57) Ваня может
выиграть первым ходом, утроив количество камней во второй куче.
Из позиций (7, 19) и (6, 20) Ваня может получить позицию (7, 20). Эта
позиция разобрана в п. 2. Игрок, который её получил (теперь это Ваня),
выигрывает своим вторым ходом.
Давайте построим таблицу выигрышной стратегии:
|
|
Петя(I ход) Всевозможные ходы |
Ваня(I ход) Только ход выигрышной стратегии |
Петя(II ход) Всевозможные ходы |
Ваня(II ход) Только ход выигрышной стратегии |
|
(6,19) 25 |
(6+1,19) 26 |
(7,19+1) 27 |
(7+1,20) 28 |
(8,20*3) 68>=68 |
|
(7*3,20) 41 |
(21,20*3) 81>=68 |
|||
|
(7,20+1) 28 |
(7,21*3) 70>=68 |
|||
|
(7,20*3) 67 |
(7,60*3) 187>=68 |
|||
|
(6,19+1) 26 |
(6+1,20) 27 |
(7+1,20) 28 |
(8,20*3) 68>=68 |
|
|
(7*3,20) 41 |
(21,20*3) 81>=68 |
|||
|
(7,20+1) 28 |
(7,21*3) 70>=68 |
|||
|
(7,20*3) 67 |
(7,60*3) 187>=68 |
|||
|
(6*3,19) 37 |
(18,19*3) 75>=68 |
|
|
|
|
(6,19*3) 63 |
(6,57*3) 177>=68 |
|
|
Два игрока, Петя и Ваня, играют в
следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди,
первый ход делает Петя. За один ход игрок может добавить в одну из куч (по
своему выбору) два камня или увеличить количество камней в куче
в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное
количество камней. Игра завершается в тот момент, когда суммарное количество
камней в кучах становится не менее 44.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший
такую позицию, что в кучах всего будет 44 или больше камней.
В начальный момент в первой куче
было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 38.
Задание 1.
При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня
выигрывает первым ходом?
Задание 2.
Назовите одно любое значение S, при котором Петя может выиграть своим
вторым ходом.
Задание 3.
Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.
Рабочие листы
к вашим урокам
Скачать
6 665 104 материала в базе
«Информатика (базовый уровень)», Семакин И.Г., Хеннер Е.К., Шеина Т.Ю.
§ 9. Обработка информации и алгоритмы
Больше материалов по этой теме
Настоящий материал опубликован пользователем Базаржапов Булат Солбонович. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
300/600 ч.
Курс профессиональной переподготовки
300 ч. — 1200 ч.
Курс профессиональной переподготовки
500/1000 ч.
Мини-курс
2 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.