19. Выигрышная стратегия: часть 1: Игра завершается в тот момент, когда суммарное количество камней…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение $S$, при котором такая ситуация возможна.
Первый способ – математическое решение
Чтобы получить минимальное $S$, Петя и Ваня должны максимально увеличивать вторую кучу — умножать её на $2$: $(13;S)\rightarrow(13;2S)\rightarrow(13;4S)$.
Для победы Вани:
$13+4S\geq135$,
$4S\geq122$,
$S\geq30{,}5$.
Минимальное целое значение $S=31$.
Проверка: после хода Пети $(13;62)$ сумма равна $75<135$, а после хода Вани $(13;124)$ сумма равна $137\geq135$.
Второй способ – решение с помощью Python
def moves(a, b):
return [(a + 3, b), (a, b + 3),
(a * 2, b), (a, b * 2)]
for S in range(1, 122):
if any(
a + b < 135 and
any(x + y >= 135 for x, y in moves(a, b))
for a, b in moves(13, S)
):
print(S)
break
Программа перебирает значения $S$ и проверяет, существует ли такой неудачный ход Пети, после которого Ваня может сразу выиграть.
Программа выведет: $31$.