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

Ответ: максимальное S равно 100. Разбор и шаги 1) Обозначения и начальные условия - Изначальная позиция: (8, S), где S > 10, и чтобы игра вообще началась (было место для хода), сумма камней должна быть больше 33: 8 + S > 33, то есть S > 25. Так как задача требует наличие первого хода Пети, который НЕ заканчивает игру, будем учитывать S ≥ 28 (поскольку для S ≤ 27 любые ходы Петя сделали бы победными по сумме ≤ 33). - В ход игрок может либо убрать 2 камня из любой кучи, либо уменьшить большую кучу вдвое, то есть заменить ее на ceil(большая/2). 2) Когда первый ход Пети НЕ победный - При S ≥ 28 у Пети есть как минимум не-wин-путь: убрать 2 камня из одной из куч даёт сумму S + 6, что уже > 33. - Рассмотрим три варианта первого хода Пети и посмотрим, может ли Ваня выиграть на следующем ходу. 3) Варианты первого хода Пети и возможность мгновенной победы Вани A) Первый ход Пети: убрать 2 камня из большей кучи - Новая позиция: (8, S − 2). Сумма S1 = 8 + (S − 2) = S + 6. - Ваня может победить, если после его хода сумма станет ≤ 33. - Удаление 2 камней (с любой кучи): сумма станет S1 − 2 = S + 4 ≤ 33 при S ≤ 29. - Деление большей кучи пополам: новая сумма S2 = 8 + ceil((S − 2)/2) ≤ 33 даёт условие S ≤ 52. - Итого: для S ∈ [28, 29] Ваня выигрывает удалением 2; для S ∈ [30, 52] — делением большой кучи. Для S ≥ 53 победа Вани одной ходом уже невозможна в этом варианте. B) Первый ход Пети: убрать 2 камня из меньшей кучи - Новая позиция: (6, S). Сумма S1 = 6 + S = S + 6 (та же сумма, но другие кучки). - Ваня может победить: - Удаление 2 камней: S1 − 2 = S + 4 ≤ 33 при S ≤ 29. - Деление большей кучи пополам: 6 + ceil(S/2) ≤ 33 даёт S ≤ 54. - Итого: для S ∈ [28, 29] выиграет удаление 2; для S ∈ [30, 54] — деление большой кучи. Для S ≥ 55 здесь не победить одним ходом. C) Первый ход Пети: уменьшить большую кучу в две половины (то есть заменить на ceil(S/2)) - Новая позиция: (8, ceil(S/2)). Пусть t = ceil(S/2). Сумма S1 = 8 + t. - Условие, чтобы ход Пети был непобедным: S1 > 33, то есть t > 25, значит S > 50. - Возможности Вани: - Удаление 2 камней: S1 − 2 = t + 6 ≤ 33 даёт t ≤ 27, то есть S ≤ 54. - Деление большей кучи пополам: 8 + ceil(t/2) ≤ 33 даёт t ≤ 50, то есть S ≤ 100. - Итого: для S ∈ [51, 54] Вана может выиграть удалением 2; для S ∈ [51, 100] — делением большей на две; для S ≥ 101 победа одним ходом невозможна в этом варианте. 4) Вывод по максимуму S - Из всех вариантов наибольший диапазон возможностей дает вариант C (первый ход Пети — уменьшить большую кучу пополам). - При S ≤ 100 Ваня может выиграть за один ход (например, при S = 100: Пети можно сделать (8,50) — сумма 58; Ваня делает halving большей кучи: (8,25) — сумма 33, победа). - При S > 100 этот вариант не даёт победы Ване за один ход: после хода Пети сумма уже примерно 8 + ceil(S/2) ≥ 8 + 51 = 59, а последующие ходы (убрать 2 или поделить пополам) не приводят к сумме ≤ 33. - Следовательно, максимальное S, при котором существует ход Пети, после которого Ваня может выиграть на своем первом ходу, равно 100. Пример при S = 100 - Петя делает ход: уменьшает большую кучу пополам. Позиция становится (8, 50) (сумма 58). - Ваня делает ход: уменьшает большую кучу пополам. Позиция становится (8, 25) (сумма 33). Ваня wins на этом ходу. Итог - Максимальное значение S: 100.