informaticsSimilar presentations:
Занятие 3.2 Стратегия
1. Выигрышная стратегия
2. Суть игры
• Это логическое состязание для двух игроков с одной илидвумя кучами камней.
• Соперники ходят по очереди по строгим правилам
(например, «+1 камень» или «умножить на 2»), стараясь
первыми набрать победное число. Поскольку удача
исключена, при безошибочной игре обоих участников
победитель математически известен заранее для любой
стартовой позиции.
3. Синтаксис
• Игроки: Обычно их двое (Петя и Ваня). Петя ходит первым.• Позиция: Сколько камней сейчас в куче (например, «7
камней»).
• Ход: Действие, которое меняет позицию (например, «+1
камень» или «умножить на 2»).
• Условие победы: какое-либо условие связанное с кучей
камней (например, «стало >= 20 камней»). Игрок, после
хода которого оно выполнилось побеждает.
• Игра: Череда ходов до тех пор, пока не наступит Условие
Победы.
4. Выигрышная (W) и проигрышная (L) позиция
Выигрышная позиция - это позиция, из которой можносделать такой ход, чтобы загнать соперника в ловушку (в
проигрышную позицию) или выиграть сразу.
Проигрышная позиция - это позиция, любой ход из которой
ведёт в выигрышную позицию, выиграть за один ход нельзя.
5. Метод «С конца»
Мы никогда не анализируем игру с начала (например, с 1камня). Мы анализируем её с конца (с момента победы).
Если есть ход в L , тогда позиция W (Победа).
Если ВСЕ ходы ведут в W, тогда позиция L (Проигрыш).
Статус текущей позиции зависит исключительно от статуса
следующих позиций.
6. Метод «С конца»
Пример (Цель 5, ход +1):1. Позиция 4: Ход в 5 (Победа), следовательно, 4 это W
2. Позиция 3: Ход в 4 (отдаёшь победу врагу), следовательно,
3 это L
3. Позиция 2: Ход в 3 (кидаешь врага в L), следовательно, 2
это W
4. Позиция 1: Ход в 2 (кидаешь врага в W), следовательно, 1
это L
7. Пример 1
• Два игрока, Петя и Ваня, играют в следующую игру. Передигроками лежит куча камней. Игроки ходят по очереди,
первый ход делает Петя.
• За один ход игрок может
• а) добавить в кучу один камень;
• б) добавить в кучу два камня;
• в) добавить в кучу три камня;
• г) увеличить количество камней в куче в два раза.
• Игра завершается в тот момент, когда количество камней в
куче превышает 33. Победителем считается игрок,
сделавший последний ход, то есть первым получивший
кучу, в которой будет 34 или больше камней. В начальный
момент в куче было S камней, 1 ≤ S ≤ 33.
8. Пример 1
• 19• а) При каких значениях числа S Петя может выиграть в
один ход? Укажите все такие значения и соответствующие
ходы Пети.
• б) Укажите такое значение S, при котором Петя не может
выиграть за один ход, но при любом ходе Пети Ваня
может выиграть своим первым ходом. Опишите
выигрышную стратегию Вани.
9. Пример 1
• 20• Укажите четыре значения S, при которых у Пети есть
выигрышная стратегия, причём Петя не может выиграть
первым ходом, но Петя может выиграть своим вторым
ходом, независимо от того, как будет ходить Ваня. Для
указанных значений S опишите выигрышную стратегию
Пети.
10. Пример 1
• 21• Укажите такое значение S, при котором у Вани есть
выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети, и при
этом у Вани нет стратегии, которая позволит ему
гарантированно выиграть первым ходом. Для указанного
значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой
выигрышной стратегии Вани (в виде рисунка или
таблицы). На рёбрах дерева указывайте, кто делает ход, в
узлах – количество камней в позиции.
11. Ответы
• 19) [17, 33]• 20) 8, 13, 14, 15
• 21) 12
12. Задача 1
• Задание 19• Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками
лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может добавить в кучу один или четыре камня либо
увеличить количество камней в куче в три раза. Для того чтобы делать
ходы, у каждого игрока есть неограниченное количество камней.
• Игра завершается в тот момент, когда количество камней в куче
становится не менее 67.
• Победителем считается игрок, сделавший последний ход, т. е. первым
получивший кучу, состоящую из 67 или более камней.
• В начальный момент в куче было S камней, 1 ≤ S ≤ 66.Будем говорить,
что игрок имеет выигрышную стратегию, если он может выиграть при
любых ходах противника.
• Укажите такое значение S, при котором Петя не может выиграть за
один ход, но при любом ходе Пети Ваня может выиграть своим
первым ходом.
13. Задача 1
Задание 20
• +1 , +4, *3
• >= 67
• Найдите два таких минимальных значения S, при которых у Пети есть
выигрышная стратегия, причём одновременно выполняются два
условия:
• — Петя не может выиграть за один ход;
• — Петя может выиграть своим вторым ходом независимо от того, как
будет ходить Ваня.
• Найденные значения запишите в ответе в порядке возрастания.
14. Задача 1
• Задание 21• +1 , +4, *3
• >= 67
• Найдите минимальное значение S, при котором одновременно
выполняются два условия:
• — у Вани есть выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети;
• — у Вани нет стратегии, которая позволит ему гарантированно
выиграть первым ходом.
• Если найдено несколько значений S, в ответе запишите наименьшее
из них.
15. Ответы
• 19) 22• 20) 18, 21
• 21) 17
16. Задача 2
• Задание 19• Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками
лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
• а) добавить в кучу один камень;
• б) добавить в кучу два камня;
• в) добавить в кучу три камня.
• Игра завершается в тот момент, когда количество камней в куче
превышает 20. Победителем считается игрок, сделавший последний
ход, то есть первым получивший кучу, в которой будет 21 или больше
камней. В начальный момент в куче было S камней, 1<=S<=20.
• Известно, что Ваня может гарантированно выиграть своим первым
ходом. Укажите значение S, с которого началась игра.
17. Задача 2
• Задание 20• Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками
лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
• а) добавить в кучу один камень;
• б) добавить в кучу два камня;
• в) добавить в кучу три камня.
• Игра завершается в тот момент, когда количество камней в куче
превышает 20. Победителем считается игрок, сделавший последний
ход, то есть первым получивший кучу, в которой будет 21 или больше
камней. В начальный момент в куче было S камней, 1<=S<=20.
• Укажите три значения S, при которых у Пети есть выигрышная
стратегия, причём Петя может выиграть своим третьим ходом,
независимо от того, как будет ходить Ваня. В ответе запишите
полученные значения в порядке возрастания.
18. Задача 2
• Задание 21• Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками
лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
• а) добавить в кучу один камень;
• б) добавить в кучу два камня;
• в) добавить в кучу три камня.
• Игра завершается в тот момент, когда количество камней в куче
превышает 20. Победителем считается игрок, сделавший последний
ход, то есть первым получивший кучу, в которой будет 21 или больше
камней. В начальный момент в куче было S камней, 1<=S<=20.
• Найдите количество значений S, при которых у Вани есть выигрышная
стратегия, позволяющая ему выиграть при любой игре Пети.
19. Ответы
• 19) 17• 20) 10, 11, 12
• 21) 5
20. Задача 3
Задание 19
За один ход игрок может добавить в кучу один или четыре камня либо
увеличить количество камней в куче в пять раз.
Игра завершается в тот момент, когда количество камней в куче становится не
менее 68.
В начальный момент в куче было S камней; 1 ≤ S ≤ 67.
Известно, что Ваня выиграл своим первым ходом после неудачного первого
хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
21. Задача 3
• Задание 20• За один ход игрок может добавить в кучу один или четыре камня либо
увеличить количество камней в куче в пять раз.
• Игра завершается в тот момент, когда количество камней в куче
становится не менее 68.
• В начальный момент в куче было S камней; 1 ≤ S ≤ 67.
• Найдите два таких значения S, при которых у Пети есть выигрышная
стратегия, причём одновременно выполняются два условия:
• — Петя не может выиграть за один ход;
• — Петя может выиграть своим вторым ходом независимо от того, как
будет ходить Ваня.
• Найденные значения запишите в ответе в порядке возрастания без
разделительных знаков.
22. Задача 3
• Задание 21• За один ход игрок может добавить в кучу один или четыре камня либо
увеличить количество камней в куче в пять раз.
• Игра завершается в тот момент, когда количество камней в куче
становится не менее 68.
• В начальный момент в куче было S камней; 1 ≤ S ≤ 67.
• Найдите минимальное значение S, при котором одновременно
выполняются два условия:
• — у Вани есть выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети;
• — у Вани нет стратегии, которая позволит ему гарантированно
выиграть первым ходом.
23. Ответы
• 19) 3• 20) 9 12
• 21) 8
24. Задача 4
• Задание 19• Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками
лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
• а) забрать из кучи один камень;
• б) забрать из кучи два камня;
• в) забрать из кучи четыре камня.
• Если камней в куче меньше, чем забирается, то такой ход выполнить
нельзя. Игрок, забравший последний камень выигрывает. В
начальный момент в куче было S камней, 1<=S<=15.
• Известно, что Ваня выиграл своим первым ходом после неудачного
первого хода Пети. Укажите максимальное значение S, когда такая
ситуация возможна.
25. Задача 4
• Задание 20• Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками
лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
• а) забрать из кучи один камень;
• б) забрать из кучи два камня;
• в) забрать из кучи четыре камня.
• Если камней в куче меньше, чем забирается, то такой ход выполнить
нельзя. Игрок, забравший последний камень выигрывает. В
начальный момент в куче было S камней, 1<=S<=15.
• Найдите два наименьших значения S, при которых у Пети есть
выигрышная стратегия, позволяющая ему выиграть вторым или
третьим ходом в зависимости от хода Вани, при этом у него нет
стратегии, которая позволит ему гарантированно выиграть своим
вторым ходом.
26. Задача 4
• Задание 21• Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками
лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может
• а) забрать из кучи один камень;
• б) забрать из кучи два камня;
• в) забрать из кучи четыре камня.
• Если камней в куче меньше, чем забирается, то такой ход выполнить
нельзя. Игрок, забравший последний камень выигрывает. В
начальный момент в куче было S камней, 1<=S<=15.
• Найдите максимальное значение S, при котором Ваня имеет
выигрышную стратегию, при которой он выигрывает при любой игре
Пети.
27. Ответы
• 19) 8• 20) 8, 10
• 21) 15