Найдите максимальное из таких значений S, при которых у Вани есть
Условие
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче 5 камней, а во второй — 8 камней, будем обозначать такую позицию (5, 8). Петя первым ходом должен добавлять камни в первую кучу, он может получить позиции (6, 8), (7,
-
и (10, 8). Если Петя получает позиции (6,
-
и (7, 8), Ваня следующим ходом тоже должен добавлять камни в первую кучу, а если Петя получает позицию (10, 8), Ваня должен добавлять камни во вторую кучу, так как теперь она стала меньшей.
Игра завершается, когда общее количество камней в двух кучах становится более 60. Победителем считается игрок, сделавший последний ход, то есть первым получивший 61 или больше камней в двух кучах.В начальный момент в первой куче было 8 камней, а во второй — S камней, 1 ≤ S ≤ 52.Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите максимальное из таких значений S, при которых у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Разбор задачи целиком открывается после входа.
Осталось ещё 5 шагов
При S = 38 Петя своим первым ходом может…
и (16, 38). В позиции (16…
Ваня выигрывает первым ходом увеличив…
Ваня делает позицию (11, 38), добавив в…
Приведём решение Михаила Глинского на языке…
Бесплатно · займёт минуту