№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора ФИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Задания
Задание 26 № 13753

Два игрока, Петя и Ваня играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 23, нельзя сделать фишку, на которой написано 32. Первый ход делает Петя, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.

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

 

Пример партии.

Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.

Пусть первый ход Пети 12.

Ваня может поставить 21, 22 или 23. Предположим, он ставит 21. Получим цепочку 12-21.

Петя может поставить 11 или 13. Предположим, он ставит 11. Получим цепочку 12-21-11.

Ваня может поставить только фишку со значением 13. Получим цепочку 12-21-11-13.

Перед Петей в кучке остались только фишки 22 и 23, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Ваня выиграл.

 

Выполните следующие три задания при исходном наборе фишек в кучке {12, 14, 21, 22, 24, 41, 42, 44}.

Задание 1.

а) Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.

б) Пусть Петя первым ходом пошел 42. У кого из игроков есть выигрышная стратегия в этой ситуации? Укажите первый ход, который должен сделать выигрывающий игрок, играющий по этой стратегии. Приведите пример одной из партий, возможных при реализации выигрывающим игроком этой стратегии.

Задание 2. Пусть Петя первым ходом пошел 44. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвертым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.

Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.

Решение.

Задание 1.

a) Все кратчайшие партии: 12-21-14-41, 14-41-12-21.

Экзаменуемому достаточно указать одну из них.

б) Выигрышная стратегия есть у Вани.

Своим первым ходом он ставит фишку 22. И далее исход игры не зависит от выбора игроков.

Возможная партия: 42-22-21-12-24-41-14-44

Существенный элемент выигрышной стратегии Вани — поставить после фишки 42 фишку 22, а не 21 или 24.

Примечание для проверяющего Стратегию также можно описать при помощи дерева или таблицы.

Существует 8 вариантов возможных партий, экзаменуемому достаточно привести одну из них.

42-22-21-12-24-41-14-44

42-22-21-12-24-44-41-14

 

42-22-21-14-41-12-24-44

42-22-21-14-44-41-12-24

 

42-22-24-41-12-21-14-44

42-22-24-41-14-44

 

42-22-24-44-41-12-21-14

42-22-24-44-41-14

 

Задание 2.

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

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

 

 

Таблица 1. Дерево всех партий при выигрышной стратегии Пети, позволяющей ему выиграть своим четвертым ходом. Над пунктирной чертой указаны ходы игроков. Завершающие игру ходы подчеркнуты. Под пунктирной чертой в скобках приведены цепочки фишек после очередного хода.

 

 

Рисунок 1. Дерево всех партий при выигрышной стратегии Пети, позволяющей ему выиграть своим четвертым ходом. В заключительных цепочках подчеркнут последний ход. Примечание для проверяющего. И для таблицы, и для рисунка допускается сокращенная форма записи, когда указываются только ходы или только получающиеся цепочки фишек.

 

Задание 3.

Нужно убрать фишки 22 и 44. Пример партии для сокращенного набора:

 

 

Примечание для проверяющего. Ученик может описать последовательность ходов в любой форме, главное, чтобы для приведенной им в качестве примера партии все ходы были указаны явно и в правильной последовательности.

Если убраны фишки 22 и 44, то игроками при любом развитии игры будут выставлены или 4 или 6 фишек. Поскольку 4 и 6 – чётные числа, то последнюю фишку всегда поставит второй игрок – Ваня. Возможны 24 различных партии в зависимости от первого хода Пети:

 

12-21-14-41

12-21-14-42-24-41-14

12-24-41-14-42-21

12-24-42-21-14-41

21-12-24-41-14-42

21-12-24-42

21-14-41-12-24-42

21-14-42-24-41-12

 

Остальные партии формируются аналогично. Ученик может не писать такого подробного комментария и привести пример только одной партии.

· ·