19. Выигрышная стратегия: часть 1: Тогда за один ход можно получить любую из четырёх позиций: (24…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение $S$, при котором такая ситуация возможна.
Первый способ – математическое решение
Чтобы получить минимальное $S$, Петя и Ваня должны максимально увеличивать вторую кучу — умножать её на $2$: $(17;S)\rightarrow(17;2S)\rightarrow(17;4S)$.
Для победы Вани:
$17+4S\geq133$,
$4S\geq116$,
$S\geq29$.
Проверка: после хода Пети $(17;58)$ сумма равна $75<133$, а после хода Вани $(17;116)$ сумма равна $133$.
Второй способ – решение с помощью Python
def moves(a, b):
return [(a + 4, b), (a, b + 4),
(a * 2, b), (a, b * 2)]
for S in range(1, 116):
if any(
a + b < 133 and
any(x + y >= 133 for x, y in moves(a, b))
for a, b in moves(17, S)
):
print(S)
break
Программа перебирает значения $S$ и проверяет, существует ли такой неудачный ход Пети, после которого Ваня может сразу выиграть.
Программа выведет: $29$.