2 Краткая информация о заданиях 19–21

Краткая информация о заданиях 19–21

Задания 19, 20 и 21 — это один блок про теорию игр. Во всех трёх речь про одну и ту же игру: два игрока (обычно Петя и Ваня) по очереди меняют кучу (или две кучи) камней, первым ходит Петя. Игра заканчивается, когда камней становится больше (или меньше) некоторого порога. Побеждает тот, кто сделал последний ход — то есть первым перешагнул границу.

Меняется от задания к заданию только вопрос:

  • 19 — самый простой: найти позицию, где сразу видно, кто выигрывает первым же ходом.

  • 20 — Петя выигрывает не сразу, а своим вторым ходом.

  • 21 — уже Ваня (второй игрок) выигрывает своим вторым ходом.

Хорошая новость: все три вопроса про одну игру решаются одной и той же программой на Python — меняешь буквально одно число в вызове функции. Плохая новость: если не понять логику, легко перепутать any и all и получить неверный ответ. Поэтому разберём и код, и «ручную» логику через дерево игры.

Проверяемые требования

Умение строить и анализировать дерево игры, находить выигрышную стратегию в простой игре двух игроков (по кодификатору ФИПИ — умение анализировать алгоритмы и строить выигрышные стратегии).

Средний процент выполнения по РФ

Год

Задание 19

Задание 20

Задание 21

2024

67 %

57 %

48 %

2025

66 %

50 %

47 %

2026

59,3 %

52,5 %

53,0 %

Проценты — по методическим материалам ФИПИ.

Уровень сложности: 19 — повышенный, 20 и 21 — высокий.

Примерное время выполнения: 19 — около 5 минут, 20 и 21 — по 10 минут. На весь блок закладывай ~25 минут.

💡 Важный момент про способ решения

Задания 19–21 можно решать «руками» (строить дерево игры и таблицу позиций) или на Python. Мы в Профиматике рекомендуем Python.

Почему? Один короткий рекурсивный шаблон из 6 строк решает и 19, и 20, и 21 — причём для любой игры на камнях: одна куча, две кучи, прибавление, умножение, вычитание, деление. Меняешь ходы из условия и число в вызове — готово.

Но логику «на пальцах» знать надо: во-первых, для проверки — если код дал странный ответ, ты поймёшь, где ошибка. Во-вторых, задание 19 часто быстрее решить в уме через «зону финиша», чем писать код. Поэтому дальше показываем оба способа для каждой задачи.