Информатика. 11 класс

Урок 8. Знакомство с теорией игр

ИГРА «КУЧА МОНЕТ»

Два игрока играют в следующую игру: перед игроками лежит куча из 10 монет. Игроки ходят по очереди. За один ход игрок может добавить в кучу 7 или 10 монет. У каждого игрока, чтобы делать ходы, есть неограниченное количество монет. Игра завершается в тот момент, когда количество монет в куче становится не менее 27. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 27 или больше монет. Собери дерево этой игры.

Три игры

Есть три игры «крестики-нолики», игра «Фишка» на поле 3×3 (см. «Построение стратегии») и игра «Куча монет» (см. задание игра «Куча монет»), где начальное количество монеток 5, а положить в кучу можно 3 или 5 монет до достижения 13. Распредели, кто выиграет при безошибочной игре каждого игрока.

Первый игрок
Ничья
Второй игрок
ИГРА «СПИЧКИ ДЕТЯМ НЕ ИГРУШКИ!»

В коробке 60 спичек. За один ход можно взять любое количество спичек от 1 до 5. Проигрывает тот, кто не может сделать ход. Кто из игроков выиграет при правильной игре?

Вставь в текст стратегии правильное количество.

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

Если же количество спичек равно , то игрок, чей ход был до появления этой позиции, свои следующим ходом заканчивает игру. Значит, эта позиция для того, кто ходит.

Аналогично проигрышными являются позиции, когда количество спичек кратно . Значит, и позиция «60 спичек» является  для того, кто будет ходить, то есть для игрока.

5
4
6
7
проигрышна
выигрышна
6
5
проигрышной
выигрышной
первого
второго
ИГРА «ФИШКА»

Фишка стоит в углу шахматной доски размером 4 х 4. Двое игроков по очереди передвигают ее вправо или вниз на 1 клетку. Второй раз ходить на поле, где фишка уже побывала, нельзя. Тот, кому некуда ходить, проигрывает. Проставь в таблице все выигрышные («+») и проигрышные («–») позиции.

+
+
+
+
+
+
+
+
ИГРА «СПИЧКИ ДЕТЯМ НЕ ИГРУШКИ!»-2

В коробке n спичек. За один ход можно взять любое количество спичек от 1 до m. Проигрывает тот, кто не может сделать ход. Распределите различные варианты игры по группам «Выигрывает первый игрок» и «Выигрывает второй игрок». 

Выигрывает первый игрок

Выигрывает второй игрок

n=25, m=4
n=20, m=4
n=10, m=3
n=20, m=3
n=14, m=6
n=15, m=6
ИГРА «ДВЕ КУЧКИ СПИЧЕК»

На столе лежат две кучки спичек: в одной 12, в другой 14 Обозначим количество спичек как (12, 14) Игроки ходят по очереди. За один ход можно взять любое число спичек только из одной из кучек (по выбору игрока). Кто не может сделать ход (спичек не осталось), проигрывает.

Выигрывает первый игрок. Восстановите последовательность игры.

ИГРА «ШОКОЛАДКА»

Шоколадка представляет собой прямоугольник 5×6, разделённый углублениями на 30 квадратиков. Двое по очереди разламывают её на части по углублениям: за один ход можно разломить любой из кусков (больший одного квадратика) на два. Кто не может сделать хода (все куски уже разломаны), проигрывает. Вставьте пропущенные слова в построение стратегии.

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

29
28
1
2
30
31
29
30
нечётные
чётные
чётные
нечётные
первый
второй
ИГРА «ОДНОСТОРОННЯЯ ЛАДЬЯ»
Выигрышная стратегия

Маша с Васей играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй — 3 камня. Игроки ходят по очереди, первый ход делает Маша. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Игра завершается в тот момент, когда количество камней в одной из куч становится не менее 20. Если в момент завершения игры общее число камней в двух кучах не менее 28, то выиграл Вася, в противном случае — Маша. При безошибочной игре обоих игроков выигрывает Вася. Соберите его выигрышную стратегию.

Анализ графов
ИГРА «БАШЕ»

Выберите верный ответ.

Имеется кучка из n камней. За один ход разрешается взять из нее не более k камней. Играют двое, ходы делают по очереди. Проигрывает тот, кто не может сделать ход.

Инвариантом стратегии для произвольной пары (n,k) является условие

* запись a mod b=0 означает, что a нацело делится на b

Инвариант стратегии

Выберите верный ответ.

Двое по очереди ломают шоколадку m*n. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход. Инвариантом стратегии первого игрока является условие .

Выигрышные стратегии

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

Игра завершается в тот момент, когда количество камней в куче становится более 200. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 201 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 200.

а) Если S от до , то Петя может выиграть первым ходом.

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

в) Если S равно , то у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом.

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

Выигрышные стратегии

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

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

Введи, недостающие значения, чтоб утверждения были верными.

а) Если S равно от до , то Петя может выиграть в один ход.

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

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

Предметы

По алфавиту По предметным областям

Классы

1 2 3 4 5 6 7 8 9 10 11
angle-skew-bottom mix-copy next-copy-2 no-copy step-1 step-2 step-3 step-4 step-5 step-6 step-6 angle-skew-bottom mix-copy next-copy-2 no-copy step-1 step-2 step-3 step-4 step-5 step-6 step-6