Материал: Теория игр. Поиск выигрышной стратегии

Задание 19. Известно, что Дед Мороз выиграл своим первым ходом после неудачного первого хода Снегурочки. Укажите минимальное значение S, когда такая ситуация возможна.Задание 20.Укажите минимальное S, при котором одновременно выполняются два условия:– у Снегурочки есть выигрышная стратегия, позволяющая ей выиграть своим вторым ходом при любой игре Деда Мороза;– у Снегурочки нет стратегии, которая позволит её гарантированно выиграть первым ходом.Задание 21Найдите максимальное и минимальное значения S, при которых – у Деда Мороза есть выигрышная стратегия, позволяющая ему выиграть, по крайней мере, своим третьим ходом при любой игре Снегурочки;– у Деда Мороза нет стратегии, которая позволит ему гарантированно выиграть первым или вторым ходом.Найденные значения запишите в ответе в порядке возрастания.

111. 
     (Е. Джобс) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
     

а) добавить в кучу 10 камней;б) увеличить количество камней в куче в два раза.Игра завершается в тот момент, когда количество камней в куче становится не менее 82. Игрок, сделавший ход, который привел к значению 82 или более, считается проигравшим. В начальный момент в куче было S камней, 1 ≤ S ≤ 81.Задание 19. Известно, что Петя одержал победу, совершив один ход за игру. Найдите минимальное значение S, при котором Петя гарантированно одерживает победу.Задание 20.Найдите все значения S такие, при которых Ваня совершает не более одного хода и выигрывает. При этом у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть, не совершив ни одного хода. В качестве ответа приведите минимальное и максимальное значения S.Задание 21Известно, что Петя выигрывает, сделав не более двух ходов. Укажите минимальное значение S, если известно, что Петя не может гарантированно выиграть, сделав один ход.

112. 
     (А. Богданов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может изменить количество камней в куче на 1, 3 или 7, но обязательно в сторону числа 42: если в куче больше 42 камней, то он забирает камни из кучи, а если меньше 42, то добавляет камни. Игра завершается в тот момент, когда количество камней в куче становится ровно 42. Игрок, первым получивший кучу из 42 камней, считается победителем.
     

Задание 19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.Задание 20.Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.Найденные значения запишите в ответе в порядке возрастания.Задание 21Найдите максимальное значение S, при котором одновременно выполняются два условия:– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

113. 
     (А. Богданов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один или три камня. Изменять количество камней в большей куче не разрешается. Игра завершается, когда количество камней в кучах становится равным. Победителем считается игрок, сделавший последний ход, то есть первым сравнявшим количество камней в двух кучах. Игроки играют рационально, т.е. без ошибок. В начальный момент в первой куче было 13 камней, а во второй – S камней, 1 ≤ S ≤ 23.
     

Задание 19. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.Задание 20.Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.Найденные значения запишите в ответе в порядке возрастания.Задание 21Найдите два значения S, при которых одновременно выполняются три условия:

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

114. 
     (Д. Статный) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два или четыре камня; увеличить количество камней в два раза. Игра завершается в тот момент, когда количество камней куче становится не менее 100. Игрок, который получил 100 и более камней, считается проигравшим. В начальный момент в первой куче было S камней; 1 ≤ S ≤ 99.
     

Задание 19. Укажите минимальное значение S, при котором Петя выигрывает, совершив всего лишь один ход и не используя умножение.Задание 20.Найдите два значения S, при которых у Вани есть выигрышная стратегия, причём одновременно выполняются два условия:— Ваня не может выиграть, совершив один ход;— Ваня может выиграть, совершив не более двух ходов, независимо от того, как будет ходить Петя.Найденные значения запишите в ответе в порядке возрастания.Задание 21Найдите минимальное и максимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть, совершив один ход;— Петя может выиграть, совершив не более двух ходов, независимо от того, как будет ходить Ваня.Найденные значения запишите в ответе в порядке возрастания.

115. 
     (PRO100 ЕГЭ) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или три камня или одиннадцать камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
     

Игра завершается в тот момент, когда количество камней в куче становится числом, оканчивающимся на ноль. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, количество камней в которой оканчивается на ноль. К примеру, игра заканчивается, когда в куче стало 10, 200, 6800 камней. В начальный момент в куче было S камней, где S –

двузначное число, не оканчивающиеся на ноль.Задание 19. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.Задание 20.Найдите количество значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:– Петя не может выиграть за один ход;– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.Задание 21Найдите минимальное и максимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.