Поиск выигрышной стратегии. Все позиции игроков делятся на выигрышные и проигрышные. Выигрышная позиция



жүктеу 295.15 Kb.
Дата13.01.2019
өлшемі295.15 Kb.
түріКонспект


Конспект «Решение задач 26»

Учитель информатики Батракова Л.В.


Задачи 26 – это задачи на поиск выигрышной стратегии.

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

Если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сде-

лает его соперник. В этом случае говорят, что у него нет выигрышной стратегии. Таким образом, общая



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

Выигрышные и проигрышные позиции можно охарактеризовать так:

• позиция, из которой все возможные ходы ведут в выигрышные позиции, — проигрышная;

• позиция, из которой хотя бы один из возможных ходов ведет в проигрышную позицию, — выигрыш-



ная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию.
Внимание!

Обратите, пожалуйста, внимание, как надо оформлять ответ. Надо по каждому заданию не только определить выигрышную стратегию, но и обязательно словесно обосновать ее. В задании 3 обязательно нарисовать дерево или таблицу.


1. Задача из демо версии ЕГЭ 2018

Два игрока, Петя и Ваня играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 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



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


Задача 2. Два игрока, Петя и Ваня играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого (выполняется условие Фано). Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Петя. Выигрывает тот, кто первый составит слово из заданного набора.

Пример. Пусть заданы слова {МАК, МЫЛО, РАМА, РАК}. На первом ходу Петя может написать букву М или Р. Пусть он написал букву М. В ответ Ваня может написать А или Ы. В первом случае получается МА, и Петя, дописав букву К, получает слово МАК из заданного набора и выигрывает. Во втором случае получается МЫ, Петя вынужден дописать Л и Ваня выиграет вторым ходом, дописав О и получив слово МЫЛО.

Задание 1.

а) Определите, у кого из игроков есть выигрышная стратегия для набора слов {ВАРЕНЬЕ, КОРОВА}. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

б) Определите, у кого из игроков есть выигрышная стратегия для набора слов {НУБНУБ…НУБ, PUMAPUMA…PUMA}. В первом слове 55 раз повторяется слово НУБ, а во втором – 32 раза повторяется слово PUMA. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 2

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



Задание 3

Дан набор слов {МОРОКА, МОРС, МОРОЗ, ПЛАХА, ПЛАТЬЕ, ПЛОМБА}. У кого из игроков есть выигрышная стратегия? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.



Решение:

Сначала предположим, что в наборе одно слово. Если игроки дописывают каждый раз по одной букве то очевидно, что первый из них (Петя) допишет все нечётные буквы, а второй (Ваня) – все чётные. Таким образом, если в слове нечётное число букв, выиграет Петя, а если чётное – Ваня.

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

Задание 1а. В слове ВАРЕНЬЕ – 7 букв (нечётное количество, выиграет Петя), а в слове КОРОВА – 6 букв (чётное количество, выиграет Ваня). Петя ходит первый и может написать букву В. Поскольку слово КОРОВА начинается с другой буквы, Ваня будет вынужден «идти» по слову ВАРЕНЬЕ и проиграет. Этот вариант – единственный, то есть возможна только одна партия, при которой Петя следует своей стратегии, она заканчивается словом ВАРЕНЬЕ.

Для набора слов {ВАРЕНЬЕ, КОРОВА} выигрышная стратегия есть у Пети.

Выигрышная стратегия Пети состоит в том, чтобы написать первую букву В. Далее остается только одно допустимое слово – ВАРЕНЬЕ, и Петя выиграет, так как в этом слове 7 букв и он допишет последнюю букву, имеющую нечётный номер. При выбранной стратегии возможна только одна партия. В результате этой партии получится слово ВАРЕНЬЕ.

Задание 1б. В первом слове набора 3*55 = 165 букв, нечётное количество. Поэтому если игра «пойдёт» по первому слову, то выиграет Петя. Во втором слове 4*32 = 128 букв, чётное количество. Поэтому если игра пойдёт по второму слову, выиграет Ваня. Слова начинаются с разных букв, поэтому Петя может выбрать, по какому слову пойдёт игра. Если он напишет букву Н, он выиграет.

Для заданного набора слов выигрышная стратегия есть у Пети. Выигрышная стратегия Пети состоит в том, чтобы написать первую букву Н. Далее остается только одно допустимое слово – НУБНУБ…НУБ, и Петя выиграет, так как в этом слове нечётное количество букв (165) и он допишет последнюю букву, имеющую нечётный номер. При выбранной стратегии возможна только одна партия. В результате этой партии получится слово НУБНУБ…НУБ.



Задание 2. В наборе слов {ВАРЕНЬЕ, КОРОВА} первое слово имеет нечётное количество букв, а второе – чётное. Чтобы Ваня мог выиграть, он должен получить возможность «перескочить» на второе слово. Для этого при любом ходе Пети у Вани должен остаться выбор. Это возможно только в том случае, когда оба слова начинаются с одной и той же буквы. Поскольку разрешается переставлять буквы только в одном слове, мы не можем сделать, чтобы оба слова начинались с буквы К – в первом слове её нет. Но можно сделать так, чтобы оба слова начинались с буквы В, переставив буквы К и В в слове КОРОВА. Получается набор {ВАРЕНЬЕ, ВОРОКА}, и Ваня выигрывает, своим первым ходом дописав букву О к букве В, которую (обязательно!) напишет Петя.

Для того, чтобы Ваня мог выиграть, во втором слове нужно поменять местами буквы К и В. Так как оба слова начинаются с буквы В, Петя обязательно напишет букву В. Выигрышная стратегия Вани состоит в том, чтобы своим ходом дописать букву О. После этого игра «идёт» по слову ВОРОКА, в нём чётное количество букв и выигрывает Ваня, который допишет последнюю букву. При выбранной стратегии возможна только одна партия. В результате этой партии будет получено слово ВОРОКА.



Задание 3. Расположим слова в столбики по начальным буквам, на каждом шаге вниз стараясь сохранить наибольшую общую часть (маркером выделена часть слова, которая совпадает с предыдущим словом в том же столбике):

МОРОКА + ПЛАХА

+ МОРОЗ ПЛАТЬЕ

МОРС ПЛОМБА

Знаком «плюс» отмечены слова, имеющие нечётное количество букв – это выигрышные варианты для Пети.

Если Петя первой напишет букву М, для выигрыша ему нужно перейти на слово МОРОЗ, но как только он составит слово МОР, Ваня тут же допишет С и выиграет, получив слово МОРС.

Если Петя напишет букву П, Ваня вынужден написать Л (это вторая буква всех оставшихся допустимых слов). Теперь Петя может написать А или О. В обоих случаях Ваня может перевести игру на слова с чётным количество букв (ПЛАТЬЕ, ПЛОМБА) и выиграть. Таким образом, при этом наборе слов выигрышную стратегию имеет Ваня.

Для набора слов {МОРОКА, МОРС, МОРОЗ, ПЛАХА, ПЛАТЬЕ, ПЛОМБА} выигрышная стратегия есть у Вани. Дерево всех возможных партий приводится на рисунке. Для Пети мы рассматриваем все возможные ходы, для Вани – только выигрышный вариант на каждом шаге. Буквами над схемой обозначены игроки (П – ход Пети, В – ход Вани).


Вместо рисунка можно использовать таблицу (зелёным цветом отмечен выигрыш Вани):


Начальная позиция

П

В

П

В

П

В



М

МО

МОР

МОРС







П

ПЛ

ПЛА

ПЛАТ

ПЛАТЬ

ПЛАТЬЕ



Задача 3.Два игрока, Петя и Ваня играют в игру с цепочками символов. Игра начинается со слова, которое состоит из n букв Ю и m букв Я. Такое слово будем обозначать как (n, m). Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

1) добавить в слово одну букву, Ю или Я

2) удвоить количество букв Ю

3) удвоить количество букв Я

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



Задание 1. Для каждой из начальных позиций (6, 29), (8, 28) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию. Объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (6, 28), (7, 28), (8, 27) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию. Объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (5, 28) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию. Объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Решение:

Задание 1. Рассмотрим все возможные ходы из позиции (6, 29). Если среди них найдётся хотя бы одна проигрышная, то эта позиция будет выигрышной. Итак:

(6, 29)  (7,29)  (7,59)

 (6,30)  (6,60)

 (12,29)  (12,58)

 (6,58)  (6,116)

Все ходы ведут в выигрышные позиции, из которых второй первым же ходом выигрывает (эти позиции выделены жёлтым маркером). Поэтому позиция (6, 29) – проигрышная. Аналогично рассматриваем все ходы из позиции (8, 28):

(8, 28)  (9,28)  (9,56)

 (8,29)  (8,58)

 (16,28)  (16,56)

 (8,56)  (8,112)

Эта позиция тоже проигрышная.

В каждой из начальных позиций (6, 29), (8, 28) выигрышную стратегию имеет Ваня. При любом ходе Пети ему нужно удвоить количество букв Б. Во всех случаях он выигрывает своим первым ходом, так как в результате его хода получается слово длиной не менее 65 символов.



Задание 2. В каждой из начальных позиций (6, 28), (7, 28), (8, 27) выигрышную стратегию имеет Петя. Своим первым ходом ему нужно перевести игру в позицию (6, 29) в первом случае или (8, 28) во втором и третьем случаях. Выше было доказано, что это позиции проигрышные для Вани.

Задание 3. Теперь рассмотрим позицию (5, 28). Из этой позиции есть ходы в позиции (6, 28), (5, 29), (10, 28) и (5, 56). Сразу видим, что позиции (10, 28) и (5, 56) – выигрышные, потому что в каждой из них удвоение второго значения даёт сумму больше 65. Позиция (6, 28), как мы доказали ранее, тоже выигрышная. Осталось разобраться с позицией (5, 29). Из неё есть ход в проигрышную позицию (6, 29) – см. результат выполнения задания 1, поэтому это выигрышная позиция. Таким образом, все ходы из позиции (5, 28) ведут в выигрышные позиции, то есть эта позиция проигрышная, и при правильной игре выиграет Ваня.

Остается нарисовать неполное дерево игры. Для выигрывающего игрока на каждом ходу выбираем только один вариант, который ведёт к выигрышу, а для проигрывающего (Пети) рассматриваем все возможные ходы, чтобы доказать, что ему не уйти от проигрыша:



То же решение в виде таблицы:


Начало

Петя

Ваня

Петя

Ваня

(5,28)

(6,28)

(6,29)

(7,29)

(7,58)

(6,30)

(6,60)

(5,29)

(12,29)

(12,58)

(6,58)

(10,28)

(10,56)




(5,56)



Из позиции (5, 28) все возможные ходы ведут в выигрышные позиции (6,28), (5,29), (10,28) и (5,56), поэтому эта позиция проигрышная, и при правильной игре выиграет Ваня. Последовательность ходов, которая приводит к победе при любых ходах Пети, показана на рисунке.


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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 41.

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

В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 40.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.



За­да­ние 1.

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

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

За­да­ние 2.

Ука­жи­те два таких зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём од­но­вре­мен­но вы­пол­ня­ют­ся два усло­вия:

- Петя не может вы­иг­рать за один ход;

- Петя может вы­иг­рать своим вто­рым ходом, не­за­ви­си­мо от того, как будет хо­дить Ваня.

Для каж­до­го ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

За­да­ние 3.

Ука­жи­те зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два усло­вия:

- у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети;

- у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.


Решение:

За­да­ние 1.

а) Петя может вы­иг­рать, если S = 14, …, 40. Чтобы по­лу­чить кучу, со­дер­жа­щую не менее 41 камня, до­ста­точ­но утро­ить ис­ход­ное ко­ли­че­ство кам­ней. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить кучу, в ко­то­рой не менее 41 камня.



При­ме­ча­ние. При куче, на­при­мер, из 40 кам­ней Ваня может вы­иг­рать и дру­гим ходом — до­ба­вив в кучу 1 или 4 камня. Но в усло­вии не тре­бу­ет­ся ука­зы­вать все вы­иг­рыш­ные стра­те­гии.

б) Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 13 кам­ней. Тогда после пер­во­го хода Пети в куче будет 14 (13+1+14), 17 (13+4=17) или 39 (13 · 3=39) кам­ней. Во всех слу­ча­ях Ваня утра­и­ва­ет ко­ли­че­ство кам­ней и вы­иг­ры­ва­ет в один ход.



За­да­ние 2.

Воз­мож­ные зна­че­ния S: 9, 12. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 13 кам­ней (12+1=13, 9+4=13). Эта по­зи­ция разо­бра­на в п. 1б. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.



За­да­ние 3.

Воз­мож­ные зна­че­ния S: 8, 11.

На­при­мер, для S = 8 после пер­во­го хода Пети в куче будет 9 кам­ней (8+1=9), 12 кам­ней (8+4=12) или 24 камня (8 · 3=24). Если в куче ста­нет 24 камня, Ваня утро­ит ко­ли­че­ство кам­ней и вы­иг­ра­ет пер­вым ходом. Си­ту­а­ция, когда в куче 9 или 12 кам­ней, разо­бра­на в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

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

 

 

 

Де­ре­во всех пар­тий, воз­мож­ных при Ва­ни­ной стра­те­гии.

Зна­ком >> обо­зна­че­ны по­зи­ции, в ко­то­рых пар­тия за­кан­чи­ва­ет­ся.
За­да­ча 5. Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может:

        до­ба­вить в кучу один ка­мень (дей­ствие А) или

        утро­ить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи 2 камня (дей­ствие Б).

На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11 или 28 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в куче было S кам­ней, 2 ≤ S ≤ 30.

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

 Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

1.

        а) При каких зна­че­ни­ях числа S Петя может вы­иг­рать пер­вым ходом? Ука­жи­те все такие зна­че­ния и вы­иг­ры­ва­ю­щий ход Пети.



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

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

Для ука­зан­ных зна­че­ний S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

3. Ука­жи­те такое зна­че­ние S, при ко­то­ром

        – у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и при этом

        – у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

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


Решение:

Задание 1. а) Петя может вы­иг­рать, если S =11, …, 30. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить кучу, в ко­то­рой не менее 31 камня. Пете до­ста­точ­но уве­ли­чить ко­ли­че­ство кам­ней в 3 раза и от­нять два камня (дей­ствие Б).

б) Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 10 кам­ней. Тогда после пер­во­го хода Пети в куче будет 11 кам­ней или 28 кам­ней. В обоих слу­ча­ях Ваня вы­пол­ня­ет дей­ствие Б и вы­иг­ры­ва­ет в один ход.



Задание 2. Воз­мож­ные зна­че­ния S: 4, 9. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 10 кам­ней (при S = 4 он вы­пол­ня­ет дей­ствие Б; при S = 9 – до­бав­ля­ет 1 ка­мень т. к. вы­пол­ня­ет дей­ствие А). Эта по­зи­ция разо­бра­на в п. 1 б. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.

Задание 3. Воз­мож­ное зна­че­ние S: 8. После пер­во­го хода Пети в куче будет 9 кам­ней или 22 камня. Если в куче ста­нет 22 камня, Ваня вы­пол­нит дей­ствие Б и вы­иг­ра­ет своим пер­вым ходом. Си­ту­а­ция, когда в куче 9 кам­ней, разо­бра­на в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

В таб­ли­це изоб­ра­же­но де­ре­во воз­мож­ных пар­тий при опи­сан­ной стра­те­гии Вани. За­клю­чи­тель­ные по­зи­ции (в них вы­иг­ры­ва­ет Ваня) подчёрк­ну­ты. На ри­сун­ке это же де­ре­во изоб­ра­же­но в гра­фи­че­ском виде (оба спо­со­ба изоб­ра­же­ния де­ре­ва до­пу­сти­мы).

 





По­ло­же­ния после оче­ред­ных ходов

Исх.

полож.


1‐й ход Пети

(разо­бра­ны все

ходы)


1‐й ход

Вани


(толь­ко

ход по


стра­те­гии)

2‐й ход Пети

(разо­бра­ны все

ходы)


2‐й ход Вани

(толь­ко ход по

стра­те­гии)


8

8+1 =9

9+1=10

10+1=11

3*11–2=31

3*10–2=28

3*28–2=82

3*8–2=22

3*22–2=64







 



Задача 6. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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



Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Решение:

Задание 1. В на­чаль­ных по­зи­ци­ях (6, 33), (8, 32) вы­иг­рыш­ная стра­те­гия есть у Вани. При на­чаль­ной по­зи­ции (6, 33) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (7, 33), (12, 33), (6, 34), (6, 66). Каж­дая из этих по­зи­ций со­дер­жит менее 73 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 73 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Для по­зи­ции (8, 32) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (9, 32), (16, 32), (8, 33), (8, 64). Каж­дая из этих по­зи­ций со­дер­жит менее 73 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 73 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Таким об­ра­зом, Ваня при любом ходе Пети вы­иг­ры­ва­ет своим пер­вым ходом.

Задание 2. В на­чаль­ных по­зи­ци­ях (6, 32), (7, 32) и (8, 31) вы­иг­рыш­ная стра­те­гия есть у Пети. При на­чаль­ной по­зи­ции (6, 32) он дол­жен пер­вым ходом по­лу­чить по­зи­цию (6, 33), из на­чаль­ных по­зи­ций (7, 32) и (8, 31) Петя после пер­во­го хода дол­жен по­лу­чить по­зи­цию (8, 32). По­зи­ции (6, 33) и (8, 32) рас­смот­ре­ны при раз­бо­ре за­да­ния 1. В этих по­зи­ци­ях вы­иг­рыш­ная стра­те­гия есть у иг­ро­ка, ко­то­рый будет хо­дить вто­рым (те­перь это Петя). Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 1. Таким об­ра­зом, Петя при любой игре Вани вы­иг­ры­ва­ет своим вто­рым ходом.

Задание 3. В на­чаль­ной по­зи­ции (7, 31) вы­иг­рыш­ная стра­те­гия есть у Вани. После пер­во­го хода Пети может воз­ник­нуть одна из четырёх по­зи­ций: (8, 31), (14, 31), (7, 32) и (7, 62). В по­зи­ци­ях (7, 62) и (14,31) Ваня может вы­иг­рать одним ходом, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. По­зи­ции (8, 31) и (6, 32) были рас­смот­ре­ны при раз­бо­ре за­да­ния 2. В этих по­зи­ци­ях у иг­ро­ка, ко­то­рый дол­жен сде­лать ход (те­перь это Ваня), есть вы­иг­рыш­ная стра­те­гия. Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 2. Таким об­ра­зом, в за­ви­си­мо­сти от игры Пети Ваня вы­иг­ры­ва­ет на пер­вом или вто­ром ходу. При­ме­ча­ние для экс­пер­та. По­след­няя фраза в при­ведённом ре­ше­нии из­бы­точ­на. Не будет ошиб­кой, если эк­за­ме­ну­е­мый про­сто на­пи­шет, на­при­мер: «При вы­бран­ной стра­те­гии пар­тия длит­ся не более двух ходов».
Дерево возможных партий:

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



То же решение в виде таблицы



Начало

Петя

Ваня

Петя

Ваня

(7,31)

(8,31)

(8,32)

(9,32)

(9,64)

(8,33)

(8,66)

(7,32)

(16,32)

(16,64)

(8,64)

(14,31)

(14,62)




(7,62)






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

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

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.



Задание 1.

а) При каких зна­че­ни­ях числа S Петя может вы­иг­рать в один ход? Ука­жи­те все такие зна­че­ния.

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

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

Задание 3. Ука­жи­те зна­че­ние S, при ко­то­ром у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, од­на­ко у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом. Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На рёбрах де­ре­ва ука­зы­вай­те, кто де­ла­ет ход, в узлах — ко­ли­че­ство кам­ней в по­зи­ции.
За­да­ча 2. Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может:

        до­ба­вить в кучу один ка­мень (дей­ствие А) или

        утро­ить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи 2 камня (дей­ствие Б).

На­при­мер, имея кучу из 20 кам­ней, за один ход можно по­лу­чить кучу из 21 камня или из 58 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в куче было S кам­ней, 2 ≤ S ≤ 39.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.



Задание 1.

        а) При каких зна­че­ни­ях числа S Петя может вы­иг­рать пер­вым ходом? Ука­жи­те все такие зна­че­ния и вы­иг­ры­ва­ю­щий ход Пети.

       б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за

один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.



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

Для ука­зан­ных зна­че­ний S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.



Задание 3. Ука­жи­те такое зна­че­ние S, при ко­то­ром

        – у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и при этом

        – у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На реб­рах де­ре­ва ука­зы­вай­те, кто де­ла­ет ход, в узлах – ко­ли­че­ство кам­ней в по­зи­ции.
За­да­ча 3. Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 20 кам­ней, а в дру­гой 7 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (20, 7). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (21, 7), (40, 7), (20, 8), (20, 14). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка - зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка. На­при­мер, при на­чаль­ных по­зи­ци­ях (10, 44), (11, 43) вы­иг­рыш­ная стра­те­гия есть у Пети. Чтобы вы­иг­рать, ему до­ста­точ­но удво­ить ко­ли­че­ство кам­ней во вто­рой куче.

За­да­ние 1. Для каж­дой из на­чаль­ных по­зи­ций (10, 43), (12, 42) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

За­да­ние 2. Для каж­дой из на­чаль­ных по­зи­ций (10, 42), (11, 42), (12, 41) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

За­да­ние 3. Для на­чаль­ной по­зи­ции (11, 41) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. Опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при ука­зан­ной Вами вы­иг­рыш­ной стра­те­гии. Пред­ставь­те де­ре­во в виде ри­сун­ка или таб­ли­цы.
Задача 4. Два игрока, Петя и Ваня по очереди стирают буквы из слова или фразы. Первым ходит Петя. За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрёт последнюю букву.

Задание 1. Укажите все слова из списка ниже, начиная с которых выигрывает Петя.

ДА, АГА, СТО, МАМА, СССР, ОГОГО, ТАРТАР, ТОРТ, РОКОКО, РЕННЕР, АВАТАР, КАРАКУРТ, КАСКАД, АНАТАНА, НЯННЯН, НАГАН.



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

Задание 3. Дана фраза: ИНФОРМАТИКА ЭТО НАУКА. Кто выиграет в этой игре, и какой будет выигрышная стратегия этого игрока? По­строй­те де­ре­во всех пар­тий, воз­мож­ных при ука­зан­ной Вами вы­иг­рыш­ной стра­те­гии. Пред­ставь­те де­ре­во в виде ри­сун­ка или таб­ли­цы.
Задача 5. Два игрока, Петя и Ваня играют в игру с цепочками символов. Игра начинается со слова, которое состоит из n букв Х, m букв Y, и k букв Z. Такое слово будем обозначать как (n, m, k). Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

1) добавить в слово одну букву из набора {Х, Y, Z}

2) удвоить количество букв Х

3) удвоить количество букв Y

4) удвоить количество букв Z

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



Задание 1. Для каждой из начальных позиций (4, 5, 15), (4, 7, 14), (6, 7, 13) укажите, кто из игроков имеет выигрышную стратегию.

Задание 2. Для каждой из начальных позиций (4, 4, 15), (4, 7, 7), (5, 7, 13) укажите, кто из игроков имеет выигрышную стратегию.

Задание 3. Для начальной позиции (5, 7, 12) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной выигрышной стратегии.


Ссылки:

http://kpolyakov.narod.ru/

http://www.inf1.info

http://www.fipi.ru/

http://inf.reshuege.ru/?redir=1






Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет