Выигрышная стратегия

Простыми словами

Стратегия — это не один удачный ход, а готовый ответ на любой ход соперника. Как в крестиках-ноликах: знаешь, что делать, как бы ни сыграл другой. Задание 20 спрашивает, при каких $S$ у Пети есть такая стратегия, приводящая к победе вторым ходом.

Игра та же, что в задании 19. Пример: ходы +1 и ×2, порог $29$, $1\le S\le 28$. Уже известно: W1 — $S$ от 15 до 28 (победа одним ходом), L1 — $S=14$ (любой ход отдаёт победу).

Слои позиций

Слово «каждый» — ключевое: достаточно одного спасительного ответа соперника, и стратегия разрушена.

Разбор: два наименьших S

Найдите два наименьших значения $S$, при которых у Пети есть стратегия выиграть вторым ходом, но нет стратегии выиграть первым.

1. Ищем ходы в L1 = {14}: $S+1=14\Rightarrow S=13$; $2S=14\Rightarrow S=7$.
2. Проверяем, что это не W1: из 7 и 13 одним ходом до 29 не дойти ✓
3. Проверяем стратегию для $S=13$: Петя — 14; Ваня — 15 или 28; Петя удваивает: $30$ или $56$, оба $\ge 29$ ✓
4. Ответ: 7 13 (в порядке возрастания, через пробел).

Программа и ловушки

N = 29
def moves(s): return [s + 1, s * 2]
W1 = {s for s in range(1, N) if any(m >= N for m in moves(s))}
L1 = {s for s in range(1, N) if s not in W1 and all(m in W1 for m in moves(s))}
W2 = [s for s in range(1, N) if s not in W1 and any(m in L1 for m in moves(s))]
print(W2)   # [7, 13]