. Петя и Ваня решили поиграть. Перед ними лежат две кучи камней. Ребята ходят по очереди, первый ход делает Петя. З а один ход игрок может убрать из любой кучи два камня или уменьшить количество камней в большей куче в два раза (с округлением в большую сторону). Н апример, пусть в одной куче 8 , а в другой 11 камней; эту позицию мы будем обозначать так: ( 8 , 11). З а один ход из позиции ( 8 , 11) можно получить любую из трёх позиций: ( 6 , 11), ( 8 , 9 ), ( 8 , 6 ). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 33. Победителем считается игрок, который сделал последний ход, то есть первым получил позицию, в которой в кучах будет 33 камня или меньше. В начале игры в первой куче было 2 3 камня, во второй — S камней, S>10. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. У кажите максимальное значение S , при котором такая ситуация возм

Кратко постановка задачи - Игра начинается с позиций (8, S), где первая куча содержит 8 камней, вторая — S камней, S > 10. - За один ход можно: вытащить 2 камня из любой кучи, или заменить большую кучу её половиной (с округлением вверх). - Игра заканчивается, когда суммарно камней становится не более 33; победитель – тот, кто сделал последний ход. - Известно, что Ваня выиграл своим первым ходом после того, как Петя сделал неудачный первый ход. Нужно найти максимальное S, при котором такая ситуация возможна. Разбор ходов. Пусть начальная позиция A = (8, S). 1) Первый ход Пети: - A1: убрать 2 камня из первой кучи: Пете переходит в B1 = (6, S). Сумма становится S + 6. - A2: убрать 2 камня из второй кучи: Пете переходит в B2 = (8, S − 2). Сумма становится S + 6. - A3: уменьшить большую кучу вдвое: так как S > 10, большая куча — вторая. Пете переходит в B3 = (8, ceil(S/2)). Сумма становится 8 + ceil(S/2). Условие неудачного хода: после первого хода сумма должна быть больше 33 (иначе Петя выиграл бы сразу). Значит: - для A1 и A2 требуется S > 27 (поскольку S + 6 > 33 → S > 27). - для A3 требуется 8 + ceil(S/2) > 33. Это эквивалентно ceil(S/2) > 25, т.е. S ≥ 51. 2) Ход Вани после неудачного хода Пети: Из каждой полученной позиции проверяем, может ли Ваня сделать один ход и получить суммарно ≤ 33 (то есть победить на своем первом ходе). - Из B1 = (6, S): - Удалить 2 из первой кучи: сумма станет 4 + S ≤ 33 при S ≤ 29. - Удалить 2 из второй кучи: сумма станет S + 4 ≤ 33 при S ≤ 29. - Уменьшить большую кучу вдвое (большая — S): сумма станет 6 + ceil(S/2) ≤ 33 при S ≤ 54. Следовательно, при S ≤ 29 Ваня может победить удалением, при S ≤ 54 —_HALВИРОВАНИЕМ_ большой кучи. Для S > 54 ни один ход не даёт победы за один ход. - Из B2 = (8, S − 2): Аналогично: большая куча снова S − 2 (поскольку S > 10). Ваня может победить удалением при S ≤ 29 или уменьшением вдвое большей кучи при S ≤ 52 (8 + ceil((S − 2)/2) ≤ 33 даёт S ≤ 52). - Из B3 = (8, ceil(S/2)): Здесь большая куча — ceil(S/2) (для S ≥ 51 это действительно так). - Удалить 2 из большего: сумма станет 8 + ceil(S/2) − 2 = 6 + ceil(S/2) ≤ 33 при ceil(S/2) ≤ 27, т.е. S ≤ 54. - Уменьшить большую вдвое: новая вторая куча становится ceil(ceil(S/2)/2) = ceil(S/4). Итоговая сумма 8 + ceil(S/4) ≤ 33 при S ≤ 100. Вариантов больше нет. Итого: - Если Петя chooses A1 или A2, ситуация даёт победу Ване при S ≤ 54 (через halve) или при S ≤ 29 (через remove). - Если Петя chooses A3, ситуация даёт победу Ване при S ≤ 100 (через halve); для S ≥ 51 A3 сам по себе не выиграет Пете, а Ваня сможет победить за один ход при любом S ≤ 100. 3) Максимальное S, при котором такая ситуация возможна - Чтобы Петя мог сделать неудачный первый ход и при этом у Вани была возможность выиграть за один ход, достаточно существования хоть одного из вариантов Пети, после которого Ваня может победить в один ход. - По анализу, наибольший S, для которого существует такой сценарий, равен 100. Пример: - Пусть S = 100. Первый ход Пети: уменьшить большую кучу вдвое → (8, ceil(100/2)) = (8, 50). Сумма 58 > 33 → не победа Пети. - Ход Вани: уменьшить большую кучу вдвое → (8, ceil(50/2)) = (8, 25). Сумма 8 + 25 = 33 → Ваня выигрывает на своем первом ходе. Аргумент против значений S > 100 - Если S ≥ 101, рассмотрим все три варианта Пети: - A1/A2: после хода Ваня может победить лишь если S ≤ 29 или S ≤ 54 соответственно — не выполняется. - A3: после хода Вани победа возможна только если S ≤ 100 (через halve); для S ≥ 101 это не выполняется. - Следовательно, при S ≥ 101 ни один ход Пети не оставляет Ване возможность выиграть за один ход. Вывод - Максимальное значение S, при котором Ваня может выиграть своим первым ходом после неудачного первого хода Пети, равно 100. Итог: S_max = 100. Пример для S = 100: - Начало: (8, 100) - Ход Пети: (8, 100) → (8, 50) (разделить большую пополам) - Ход Вани: (8, 50) → (8, 25) (разделить большую пополам) - Сумма стала 33, значит Ваня выиграл на своем первом ходе.