Подтема 6 из 6 · дополнительный урок
Третий ход и позиция шире числа
Победа третьим ходом, запрет повторять ход, игра без ограничения числа ходов и вопросы обо всех позициях сразу.
Третий ход
Это дополнительный урок: такие задачи редки, на экзамене их почти не было. Как ответить на вопрос о третьем ходе — «Петя не может выиграть за один и за два хода, но выигрывает своим третьим ходом»?
Продолжить разбор от конца ещё на шаг: В3 — есть ход в П2, П3 — все ходы ведут в В1, В2 или В3. В функции g появляются две строки, а проверка П2 становится строже: теперь среди ответов бывает и 3.
from functools import cache def moves(s): return [s + 1, s * 2] def finished(s): return s >= 21 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(0 < x <= 2 for x in r): return -2 # П2 if -2 in r: return 3 # В3 if all(x > 0 for x in r): return -3 # П3 return 0 starts = range(1, 21)print([s for s in starts if g(s) == 3])print([s for s in starts if g(s) == -3])Из 4 Петя удваивает кучу и отдаёт Ване 8 — это П2: что бы Ваня ни делал, Петя выиграет не позже третьего хода. Из 6 оба хода плохи: в 7 (В3 Вани) и в 12 (В1 Вани), поэтому 6 — П3.
Без 0 < x <= 2 позиция с ходами в В1 и В3 попала бы в П2, хотя соперник выигрывает только третьим ходом.
Запрет повтора
Что, если нельзя повторять ход, который только что сделал соперник?
Тогда числа камней мало: в позицию добавляют прошлый ход — пару (s, last). Ходы зависят не только от кучи, но и от того, как в неё пришли. Игра: +1, +2 или ×2, нельзя повторять ход соперника, победа при s ≥ 21. У начальной позиции прошлого хода нет — пустая строка:
from functools import cache def moves(p): s, last = p result = [] if last != "+1": result.append((s + 1, "+1")) if last != "+2": result.append((s + 2, "+2")) if last != "×2": result.append((s * 2, "×2")) return result def finished(p): return p[0] >= 21 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 print(moves((5, "+2")))starts = [(s, "") for s in range(1, 21)]print([p[0] for p in starts if g(p) == -1])print([p[0] for p in starts if g(p) == 2])print([p[0] for p in starts if g(p) == -2])Функция g не изменилась — она видит позицию только через moves и finished. А группы изменились: без запрета В2 были 5, 8 и 9, теперь к ним добавились 6 и 7 — запрет мешает Ване уйти от ловушки.
Если нельзя повторять свой собственный прошлый ход, хранят оба: (s, мой прошлый, чужой прошлый), и после хода последние два элемента меняются местами.
Игра до конца
Иногда спрашивают без номера хода: «у Вани есть выигрышная стратегия при любой игре Пети». Как это проверить?
Играть до конца: позиция выигрышная, если есть ход, который кончает игру или отдаёт сопернику проигрышную позицию. Номер хода не нужен, хватает одной функции:
from functools import cache def moves(s): return [s + 1, s * 2] def finished(s): return s >= 21 @cachedef win(s): return any(finished(q) or not win(q) for q in moves(s)) print([s for s in range(1, 21) if not win(s)])Здесь есть знакомые 10 (П1) и 8 (П2), а 2 и 6 — позиции, где Ваня выигрывает позже. Рекурсия кончается, потому что куча всё время растёт. В играх, где можно вернуться в прежнюю позицию, так делать нельзя: вызовы пойдут по кругу.
Все позиции сразу
«Известно, что Петя выиграл первым ходом. Какое наименьшее число камней могло быть в двух кучах вместе?» Начального S тут нет — как решать?
Перебрать все позиции (a, b) двумя циклами и взять наименьшую сумму среди тех, где есть победный ход. Игра: +1 или ×2 в одну кучу, победа при сумме не менее 20:
def moves(p): a, b = p return [(a + 1, b), (a * 2, b), (a, b + 1), (a, b * 2)] def finished(p): return p[0] + p[1] >= 20 best = Nonefor a in range(1, 20): for b in range(1, 20): p = (a, b) wins = any(finished(q) for q in moves(p)) if not finished(p) and wins: if best is None or a + b < best: best = a + bprint(best)Например, (1, 10): удвоение второй кучи даёт сумму 21. А при сумме 10 не хватает даже лучшего хода: из (1, 9) получится 19. Выгоднее всего, когда почти все камни в одной куче, — её и удваивают.
Итого
- В3есть ход в П2
- П3все ходы в В1–В3; П2 тогда —
0 < x <= 2 - Запрет повторапозиция (s, last)
- Без номера хода
win: победный ход или ход в проигрыш соперника - Все позициидва цикла по a и b
Проверьте себя
Ответь сначала сам, потом открой ответ.
r = [3, 1]. Какая это группа и почему её нельзя считать П2?ОтветСкрыть ответ
ОтветСкрыть ответ
win(10) в игре +1 или ×2 до 21 и почему?ОтветСкрыть ответ
False: оба хода — в 11 и в 20 — не кончают игру и отдают сопернику выигрышную позицию.ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Победа третьим ходом
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Игра завершается, когда суммарное количество камней в кучах становится не менее 100. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 10 камней, во второй — S камней, 1 ≤ S ≤ 89. Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: Петя не может выиграть за один и за два хода; Петя может выиграть своим третьим ходом независимо от ходов Вани.
Введите два числа через пробел в порядке возрастания.
Подсказка
Добавь в g группы В3 и П3 и отбери g(p) == 3.
Решение
35 и 36: подходят 35, 36 и 40.
from functools import cache def moves(p): a, b = p return [(a + 2, b), (a * 2, b), (a, b + 2), (a, b * 2)] def finished(p): a, b = p return a + b >= 100 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(0 < x <= 2 for x in r): return -2 # П2 if -2 in r: return 3 # В3 if all(x > 0 for x in r): return -3 # П3 return 0 starts = [(10, s) for s in range(1, 90)]print(*[p[1] for p in starts if g(p) == 3][:2])Ответ: 35 36
Ваня: вторым или третьим ходом
Игра та же: две кучи, за ход можно добавить в одну из куч два камня или удвоить одну кучу; игра завершается, когда в двух кучах вместе не менее 100 камней; в первой куче 10 камней, во второй — S, 1 ≤ S ≤ 89. Найдите наименьшее значение S, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым или третьим ходом при любой игре Пети; у Вани нет стратегии, которая позволит ему гарантированно выиграть вторым ходом.
Введите число.
Подсказка
Нужна П3: g(p) == -3.
Решение
34 — наименьшая П3 среди (10, S).
from functools import cache def moves(p): a, b = p return [(a + 2, b), (a * 2, b), (a, b + 2), (a, b * 2)] def finished(p): a, b = p return a + b >= 100 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(0 < x <= 2 for x in r): return -2 # П2 if -2 in r: return 3 # В3 if all(x > 0 for x in r): return -3 # П3 return 0 starts = [(10, s) for s in range(1, 90)]print(min(p[1] for p in starts if g(p) == -3))Ответ: 34
Нельзя повторить ход: задание 19
Два игрока, Петя и Ваня, играют в игру с кучей камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок. Игра завершается, когда количество камней в куче становится не менее 30. В начальный момент в куче было S камней, 1 ≤ S ≤ 29. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Введите число.
Подсказка
Позиция — пара: число камней и прошлый ход. Нужна П1.
Решение
14 — единственная П1 среди начальных позиций (S, '').
from functools import cache def moves(p): s, last = p result = [] if last != '+1': result.append((s + 1, '+1')) if last != '+2': result.append((s + 2, '+2')) if last != '×2': result.append((s * 2, '×2')) return result def finished(p): return p[0] >= 30 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 starts = [(s, '') for s in range(1, 30)]print(*[p[0] for p in starts if g(p) == -1])Ответ: 14
Нельзя повторить ход: задание 20
Игра та же: можно добавить в кучу один или два камня или удвоить её, но нельзя повторять ход, который только что сделал соперник; игра завершается, когда в куче не менее 30 камней; 1 ≤ S ≤ 29. Найдите наименьшее и наибольшее значения S, при которых Петя не может выиграть первым ходом, но может выиграть своим вторым ходом при любой игре Вани.
Введите два числа через пробел: наименьшее, затем наибольшее.
Подсказка
Та же позиция-пара, отбор g(p) == 2.
Решение
7 и 13 — наименьшая и наибольшая В2.
from functools import cache def moves(p): s, last = p result = [] if last != '+1': result.append((s + 1, '+1')) if last != '+2': result.append((s + 2, '+2')) if last != '×2': result.append((s * 2, '×2')) return result def finished(p): return p[0] >= 30 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 found = [s for s in range(1, 30) if g((s, '')) == 2]print(min(found), max(found))Ответ: 7 13
Взять 1, 2 или 3 камня
Игра: из кучи можно взять 1, 2 или 3 камня, выигрывает взявший последний камень. При каких S от 1 до 14 первый игрок проигрывает при правильной игре соперника?
Введите значения S через пробел в порядке возрастания.
Подсказка
Игра до конца: позиция проигрышная, если любой ход отдаёт сопернику выигрышную.
Решение
4, 8, 12: из них любой ход оставляет сопернику 1–3 камня сверх кратного четырём, и он возвращает кратное четырём.
Решение программой
from functools import cache @cachedef win(s): return any(s - k == 0 or not win(s - k) for k in (1, 2, 3) if k <= s) print(*[s for s in range(1, 15) if not win(s)])Ответ: 4 8 12
Стратегия Вани без ограничения ходов
Две кучи, ход — добавить в одну из куч один камень или удвоить одну кучу. Игра завершается, когда суммарное количество камней не менее 60. В первой куче 6 камней, во второй — S, 1 ≤ S ≤ 53. Найдите максимальное значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть при любой игре Пети.
Введите число.
Подсказка
Игра до конца: у Вани стратегия, если начальная позиция проигрышная для Пети.
Решение
игра до конца даёт для Вани S = 2, 6, 8, 11, 15, 18, 21, 25.
Решение программой
from functools import cache def moves(p): a, b = p return [(a + 1, b), (a * 2, b), (a, b + 1), (a, b * 2)] def finished(p): return p[0] + p[1] >= 60 @cachedef win(p): return any(finished(q) or not win(q) for q in moves(p)) print(max(s for s in range(1, 54) if not win((6, s))))Ответ: 25
Наименьшая сумма для победы сразу
Две кучи, ход — добавить камень в одну кучу или утроить одну кучу, победа при сумме не менее 50. Какое наименьшее суммарное число камней в позиции, из которой можно выиграть первым ходом?
Введите число.
Подсказка
Перебирай пары куч, а не начальное S.
Решение
например, (1, 17) — утроение даёт 1 + 51 = 52; при сумме 17 лучший ход даёт не больше 49.
Решение программой
def moves(p): a, b = p return [(a + 1, b), (a * 3, b), (a, b + 1), (a, b * 3)] def finished(p): return p[0] + p[1] >= 50 best = Nonefor a in range(1, 50): for b in range(1, 50): p = (a, b) wins = any(finished(q) for q in moves(p)) if not finished(p) and wins: if best is None or a + b < best: best = a + bprint(best)Ответ: 18