"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить…
"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить один камень в одну из куч и два камня в другую или же увеличить количество камней в любой куче в два раза. Например, пусть в одной куче 6 камней, а в другой 8 камней; такую позицию мы будем обозначать (6, 8). За один ход из позиции (6, 8) можно получить любую из четырёх позиций: (7, 10), (8, 9), (12, 8), (6, 16). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 47. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 47 или больше камней. В начальный момент в первой куче было 10 камней, во второй куче — S камней, 1 ≤ S ≤ 36. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, то есть не гарантируют выигрыш независимо от игры противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна."
Привет! Давай разбираться по шагам и понять, почему минимальное S равно 7.
- Что за игра и что значит выигрыш в одну партию
- Ходы: за ход можно либо увеличить одну кучу вдвое, либо добавить 1 к одной куче и 2 к другой (в любом порядке). Примеры из условия подтверждают это.
- Игра заканчивается, когда сумма камней в двух кучах стала не менее 47. Выигрывает тот, кто сделал последний ход (то есть довёл сумму до 47 и более).
- Начальные позиции: (10, S), где S от 1 до 36.
- Что значит “Ваня выиграл своим первым ходом после неудачного первого хода Пети”
- После первого хода Пети Ваня должен иметь возможность победить сразу своим ходом. То есть из полученной позиции он должен суметь сделать ход, после которого сумма станет >= 47.
- За один ход Ваня может:
- удвоить одну кучку: 2a + b или a + 2b;
- или сделать прибавку 1 к одной куче и 2 к другой: сумма увеличится на 3 (то есть a + b + 3).
- Как понять минимальное S
- Пусть после первого хода Пети новая позиция будет (a, b). Чтобы Ваня мог выиграть в свой ход, его ход должен привести к сумме >= 47:
- либо 2a + b >= 47,
- либо a + 2b >= 47,
- либо a + b + 3 >= 47.
- Это дает очень конкретные условия на сумму и величины после первого хода.
- Проверка S = 7 (почему именно так)
- Изначально (10, 7).
- Пусть Петя делает “неудачный” первый ход, например удвоит первую кучу: (20, 7).
- Тогда у Вани есть выигрышный ход: удвоить первую кучу снова и получить (40, 7), суммарно 47. Так как он сделал последний ход (добив сумму до 47), он выигрывает.
- Значит, для S = 7 существует такой первый ход Пети, после которого Ваня может выиграть сразу же своим ходом.
- Почему для S < 7 такой ситуации нет
- Рассмотрим все четыре возможных первых хода Пети от начального (10, S) при S ≤ 6 и посмотрим, может ли Ваня выиграть в один ход:
- Удвоение первой кучи: становится (20, S). Максимальная сумма после одного хода Вани тогда либо 2a' + b' = 40 + S ≤ 46, либо a' + 2b' = 20 + 2S ≤ 32, либо a' + b' + 3 ≤ 23 + S ≤ 29. Ни одна из этих величин не достигает 47, когда S ≤ 6.
- Удвоение второй кучи: становится (10, 2S). Максимум после одного хода: 2a' + b' = 20 + 2S ≤ 32, или a' + 2b' = 10 + 4S ≤ 34, или a' + b' + 3 ≤ 25. Тоже меньше 47.
- Добавление 1 к одной и 2 к другой: например (11, S+2) или (12, S+1). Их суммы после одного хода и дальнейшие удвоения не достигают 47: максимум около S+13, а потом плюс 3 — все меньше 47 для S ≤ 6.
- Следовательно, для S ≤ 6 никакой первый ход Пети не может оставить позицию, из которой Ваня смог бы выиграть в один ход.
- Вывод
- Минимальное значение S, при котором такая ситуация возможна, равно 7.
- Краткое резюме: S = 7 позволяет Петя сделать ход вроде удвоения первой кучи, и тогда Ваня может выиграть сразу же своим ходом (удвоить первую кучу до 40,7 → сумма 47). Для меньших S такая «один ход до победы» для Вани невозможна.
Если хочешь, могу разобрать решение ещё детальнее, показать таблицу выигрышных позиций или рассмотреть другие начальные S. Но сейчас ответ на задачу: S = 7.
Пожалуйста, оцени мой ответ лайком или дизлайком.
