Для игры, описанной в задании 19, найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.
Из 20 задачи найдено минимальное значение кучи камней для победы вторым ходом-44. Тогда, для победы Вани, ему необходимо получить кучу из 44 камней или больше, при любой игре Пети. Минимальная куча в таком случае-43 камня. Петя может добавить или 1 или 43 камня. Если Петя добавит 41 камень, Ваня выиграет первым ходом. Если Петя добавляет один камень, тогда Ваня делает кучу 45 камней и выигрывает своим вторым ходом.
Ответ: 43.
Приведем решение Маргариты Фалько на языке 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]) and not g(s, 0, [1])])
print('21', [s for s in range(16, 100) if g(s, 0, [2, 4]) and not g(s, 0, [2])])