Урок 29
Использование графов
§ 18. Игровые стратегии

Содержание урока

Выигрышные и проигрышные позиции

Дерево перебора вариантов

Решение без дерева

Исследование игры

Выводы

Вопросы и задания

Исследование игры

Исследуйте самостоятельно следующую игру.

В игре участвуют два игрока, назовём их Петя (он ходит первый) и Ваня (второй). Вначале перед игроками лежит куча из некоторого количества камней (обозначим его S). За один ход игрок может добавить в кучу один камень (ход «+1») или увеличить количество камней в куче в два раза (ход «*2»). Например, имея кучу из 5 камней, за один ход можно получить кучу из 6 или 10 камней. У каждого игрока есть неограниченное количество камней. Победителем считается игрок, первым получивший кучу, в которой 14 камней или больше.

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

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

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

г) Постройте неполное дерево игры с доказательством стратегии выигрывающего игрока при S = 4.

Следующая страница Выводы

Cкачать материалы урока