Решение задач информатика 11 класс

1) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Если при этом в куче оказалось не более 89 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник.
В начальный момент в куче было S камней, 1 ≤ S ≤ 32.
Описывая выигрышную стратегию, на рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции.
Задание 1.
а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.
б) У кого из игроков есть выигрышная стратегия при S = 29, 30, 31? Опишите выигрышные стратегии для этих случаев.
Задание 2.
У кого из игроков есть выигрышная стратегия при S = 9, 10? Опишите соответствующие выигрышные стратегии.
Задание 3.
У кого из игроков есть выигрышная стратегия при S = 8?


2) Два игрока, Паша и Валя играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Паша. Выигрывает тот, кто первый составит слово из заданного набора.
Задание 1.
а) Определите, у кого из игроков есть выигрышная стратегия для набора слов {ЛОКОН, ЛОКОМОТИВ, ЛОКАУТ}.
б) Определите, у кого из игроков есть выигрышная стратегия для набора слов {МЭРС… МЭРС, МЭРИЯ… МЭРИЯ}. В первом слове 155 раз повторяется слово МЭРС, а во втором – 97 раз повторяется слово МЭРИЯ.
Задание 2.
В наборе слов, приведённом в задании 1а, поменяйте местами две соседние буквы в любом слове так, чтобы выигрышная стратегия была у другого игрока.
Задание 3.
Дан набор слов {МОЛОКО, НАКЛОН, НАКАТ, МОЛЛЮСК, МОШКА, ЛОНДОН, МОСКВА}. У кого из игроков есть выигрышная стра
тегия?



3) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня, добавить в кучу три камня или увеличить количество камней в куче в два раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 30 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 29.
Задание 1.
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 2.
Укажите четыре таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: а) Петя не может выиграть за один ход; б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Задание 3.
Укажите два значения S, при котором:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию В
ани.