Для игры, описанной в задании 19, найдите наименьшее и наибольшее значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.
В ответе запишите найденные значения в порядке возрастания.
Ответ:
Если игрок получает кучу из 56 камней, то он побеждает, прибавив к куче максимальный делитель 56. Следовательно, игрок получивший кучу из 55 камней не может выиграть, но может выиграть соперник, независимо от хода первого игрока. Тогда максимальная куча, при которой выиграет Петя вторым ходом, независимо от хода Вани - 54 камня. Петя добавляет один камень и, при любом ходе Вани, выигрывает своим вторым ходом.
Для нахождения минимального делителя рассмотрим варианты, при которых мы можем получить 55 камней.
Варианты:
54+1
50+5
44+11
Минимальное значение - 44 камня. Петя добавляет 11 камней, тогда, независимо от хода Вани, Петя выигрывает своим вторым ходом.
Ответ: 44; 54.
Приведем решение Маргариты Фалько на языке Python.
def g(s, p, end):
if s > 111: return p in end
if p > max(end): return False
moves = [g(s + k, p+1, end) for k in range(1, s+1) if s % k == 0]
return any(moves) if ((p+1) % 2) == (end[0] % 2) else all(moves)
print('19', [s for s in range(16, 100) if g(s, 0, [2])])
print('20', [s for s in range(16, 100) if g(s, 0, [3])])
print('21', [s for s in range(16, 100) if g(s, 0, [2, 4]) and not g(s, 0, [2])])