Тип 20 № 76688 
Выигрышная стратегия. Задание 2. Одна куча
i
Решение. Если игрок получает кучу из 46 камней, то он побеждает, прибавив к куче максимальный делитель 46. Следовательно, игрок получивший кучу из 45 камней не может выиграть, но может выиграть соперник, независимо от хода первого игрока. Тогда максимальная куча, при которой выиграет Петя вторым ходом, независимо от хода Вани - 44 камня. Петя добавляет один камень и, при любом ходе Вани, выигрывает своим вторым ходом.
Для нахождения минимального количества камней рассмотрим варианты, при которых мы можем получить 45 камней.
Варианты:
44+1
42+3
40+5
36+9
30+15
Минимальное значение - 30 камней. Петя добавляет 15 камней, тогда, независимо от хода Вани, Петя выигрывает своим вторым ходом.
Ответ: 30; 44.
Приведем решение Маргариты Фалько на языке Python.
def g(s, p, end):
if s > 91: 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])])
Ответ: 30&44
PDF-версии: