Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок можетдобавить один камень в одну из куч и два камня в другуюили жеувеличить количество камней в любой кучев два раза. Например, пусть в одной куче 6 камней, а в другой 8 камней; такую позицию мы будем обозначать (6,8). За один ход из позиции (6,8) можно получить любую из четырёх позиций: (7,10), (8,9), (12,8), (6,16). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 47. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 47 или больше камней. В начальный момент в первой куче было 10 камней, во второй кучеSкамней, 1 S 36. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, то есть не гарантируют выигрыш независимо от игры противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значениеS, когда такая ситуация возможна.

Привет! Давай разбираться. Задача в информатике на стратегию — это всегда интересно.

Итак, начальная ситуация такова: у Пети (10, S камней), где S — это число, которое нам и нужно найти. Чтобы Ваня выиграл первым же своим ходом после хода Пети, Петя должен сделать такой ход, чтобы Ваня мог на следующем ходу сделать суммарное количество камней не менее 47.

Твой ответ 79 не подходит под начальные условия задачи, так как S должно быть от 1 до 36.

Если Петя удвоит количество камней в первой куче, то у него получится (20, S). Для Вани нужно добиться за один ход, чтобы сумма камней была минимум 47. Если Ваня удвоит количество камней в любой из куч, то получится или (40, S), или (20, 2S). В первом случае сумма камней будет минимум 40 + 1 = 41, что меньше 47 и не приведет к победе Вани. Но если S = 7, то при удвоении второй кучи Ваня получит (20, 14), а потом, если он решит добавить 1 камень в первую кучу и 2 камня во вторую, сумма камней станет 20 + 1 + 14 + 2 = 37, что тоже не даст ему выигрыша.

Всё дело в последовательности ходов — Ваня должен сначала добавить камни, а затем удвоить. То есть, если у Вани будет S = 7 и Петя выберет удвоение первой кучи, получив (20, S), то Ваня может сначала сделать ход (20, 7) -> (21, 9), а затем удвоить первую кучу, получив (42, 9), что в сумме даст ему 51 камень и победу.

Таким образом, минимальное значение S, при котором Ваня может выиграть своим первым ходом, если Петя удвоит первую кучу, это 7.

Надеюсь, мой ответ помог разобраться в решении. Поставишь лайк, если всё было понятно? Или дизлайк, если что-то ещё нужно уточнить.