Найдите минимальное значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом
Реши 21
Сверь числа и знаки с фото.
Р-00 (демо-2021). Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче — S камней; \(1 \le S \le 69\).
Задание 21 Найдите минимальное значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ: \(S=30\).
1. Отсекаем \(S\ge 35\)
Если \(S\ge 35\), Петя первым ходом удваивает вторую кучу:
\[ 7+2S\ge 7+70=77, \]
то есть сразу выигрывает. Значит, Ваня может рассчитывать на победу только при
\[ S\le 34. \]
2. Смотрим на ход Пети «добавить камень в первую кучу»
Получается позиция
\[ (8,S). \]
При \(S\le34\) Ваня не может выиграть сразу: даже максимальный вариант \(8+2S\) даёт не больше \(8+68=76\).
Значит, Ваня должен своим первым ходом поставить Петю в такую позицию, из которой Петя ещё не выигрывает, а на любой ход Пети у Вани есть победный ответ. Для этой игры такие «критические» позиции имеют вид
\[ 2x+y=76,\quad x+2y\le76, \]
или
\[ x+2y=76,\quad 2x+y\le76, \]
а также отдельно позиция \((25,25)\).
Из \((8,S)\) Ваня может попасть в нужную позицию только при
\[ S=17,\quad 30,\quad 33. \]
Например:
- при \(S=17\) Ваня удвоением второй кучи получает \((8,34)\), где \(8+2\cdot34=76\);
- при \(S=30\) Ваня удвоением первой кучи получает \((16,30)\), где \(16+2\cdot30=76\);
- при \(S=33\) Ваня добавляет камень во вторую кучу и снова получает \((8,34)\).
Но \(S=17\) не подходит: Петя может сыграть в \((7,18)\), и Ваня не может ни сразу выиграть, ни попасть в нужную критическую позицию.
Следовательно, первое возможное значение — \(S=30\).
3. Проверка для \(S=30\)
Рассмотрим все первые ходы Пети:
| Ход Пети | Ответ Вани |
|---|---|
| добавить в первую: \((8,30)\) | \((16,30)\) |
| добавить во вторую: \((7,31)\) | \((14,31)\) |
| удвоить первую: \((14,30)\) | \((14,31)\) |
| удвоить вторую: \((7,60)\) | Ваня сразу удваивает вторую: \(7+120=127\ge77\) |
В позициях \((16,30)\) и \((14,31)\) у Пети нет победного хода, а после любого его хода Ваня заканчивает игру, например для \((16,30)\):
\[ (17,30)\to 17+60=77, \] \[ (16,31)\to 16+62=78, \] \[ (32,30)\to 64+30=94, \] \[ (16,60)\to 16+120=136. \]
То есть Ваня всегда выигрывает своим первым или вторым ходом.
При этом гарантировать победу именно первым ходом Ваня не может: если Петя сыграет \((8,30)\), максимальная сумма после хода Вани будет
\[ 8+2\cdot30=68<77. \]
Значит, оба условия задания выполнены, и минимальное значение:
\[ \boxed{S=30} \]
