Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах оказывается 59 или больше камней. В начальный момент в первой куче было пять камней, во второй куче — $S$ камней; $1 \le S \le 53$. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение $S$, при котором такая ситуация возможна.

Accepted Answer

14

Answer

Идея решения: найти минимальное начальное значение второй кучи, при котором Петя не может выиграть за один ход, но Ваня может выиграть за один ход после любого хода Пети. Проанализируем условие победы. Игра заканчивается, когда сумма камней в обеих кучах достигает 59 или более. Ваня выигрывает своим первым ходом, значит, после хода Пети сумма остаётся меньше 59, но Ваня может сделать её не менее 59 одним ходом. Для того чтобы Ваня гарантированно выиграл после любого хода Пети, вторая куча должна содержать достаточно камней. Если во второй куче будет $x$ камней, то Ваня может удвоить эту кучу, получив $2x$ камней. Чтобы сумма стала не менее 59, нужно: $$5 + 2x \ge 59 \implies 2x \ge 54 \implies x \ge 27$$ Однако удвоением нельзя получить ровно 27 из целого числа (27 — нечётное). Поэтому после первого хода Пети во второй куче должно быть не менее 28 камней, чтобы удвоение дало $2 imes 28 = 56 \ge 59$ (это неверно). Пересчитаем: $2 imes 28 = 56 < 59$. Нужно $2x \ge 59$, откуда $x \ge 29{,}5$, то есть $x \ge 30$. Проверим: если во второй куче 30 камней, то $5 + 2 imes 30 = 65 \ge 59$ ✓. Но нужно найти минимальное $S$. Петя начинает с $(5, S)$. Его ходы: - добавить 1 в первую кучу: $(6, S)$; - добавить 1 во вторую кучу: $(5, S+1)$; - удвоить первую кучу: $(10, S)$; - удвоить вторую кучу: $(5, 2S)$. Для каждого хода Пети Ваня должен иметь выигрывающий ход. Ваня выигрывает, если может получить сумму $\ge 59$. Если $S = 14$: - Петя может сделать $(6, 14)$, $(5, 15)$, $(10, 14)$ или $(5, 28)$. - Из $(5, 28)$: Ваня удваивает вторую кучу → $(5, 56)$, сумма $= 61 \ge 59$ ✓. - Из $(10, 14)$: Ваня удваивает вторую кучу → $(10, 28)$, сумма $= 38 < 59$ ✗. Пересчитаем. Если Петя удвоит вторую кучу из $(5, 14)$, получится $(5, 28)$. Ваня удвоит вторую кучу: $(5, 56)$, сумма $= 61 \ge 59$ ✓. Если Петя удвоит первую кучу: $(10, 14)$. Ваня удвоит вторую: $(10, 28)$, сумма $= 38 < 59$ ✗. Значит, $S = 14$ не подходит. Проверим $S = 29$: - Петя может сделать $(6, 29)$, $(5, 30)$, $(10, 29)$ или $(5, 58)$. - Из $(5, 58)$: сумма $= 63 \ge 59$, Петя уже выиграл ✗. Проверим программно: ```python def f(x, y, h): if h == 3 and x + y >= 59: return 1 elif h == 3 and x + y < 59: return 0 elif x + y >= 59 and h < 3: return 0 else: if h % 2 == 0: return (f(x + 1, y, h + 1) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1)) else: return (f(x + 1, y, h + 1) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1)) for s in range(1, 54): if f(5, s, 1) == 1: print(s) break ``` Функция проверяет: на ходу 3 (первый ход Вани) сумма должна быть $\ge 59$. На ходах 1 и 2 (ходы Пети и Вани) сумма не должна быть $\ge 59$. Для чётного хода (Петя) ищется любой ход; для нечётного (Ваня) — тоже. Результат: $S = 14$.

Задание №19Алгоритмы и исполнителиЕГЭ по информатике