Теоретические основы информатики · 3 задания · 3 балла

Теория игр

Задания 19–21 · одна и две кучи

Три вопроса одной игры: выигрышная позиция, стратегия и минимальное число ходов.

Теория 19 — число; 20 — два числа; 21 — число 19 · 20 · 21

19–21

Страницы 19, 20 и 21 объединены: это одна игра с тремя вопросами. Ниже — теория, способы решения и форматы ответа для всех трёх номеров.

Что проверяет

Дискретные игры двух игроков с полной информацией: дерево перебора, выигрышные и проигрышные позиции, стратегии и счёт ходов.

Основание: проект спецификации и кодификатора КИМ 2027. Открыть документы

Одна игра — три задания

Что спрашивают в 19, 20 и 21

Это одна игра с тремя вопросами. Правила в каждом варианте свои, но рассуждение общее: строим позиции, размечаем выигрышные и проигрышные и считаем ходы.

Задание 19

Найдите позицию

Обычно нужно найти одно значение S, при котором первый игрок не выигрывает сразу, а второй выигрывает своим первым ходом. Реже — наоборот.

Ответодно число

Задание 20

Найдите два значения

Нужно найти два значения S для второго вопроса: например, Петя не выигрывает первым, но выигрывает вторым; в других вариантах — Ваня выигрывает сразу после любого хода Пети.

Ответдва числа

Задание 21

Опишите стратегию

Нужно найти значение S, при котором у игрока есть стратегия победы не позже второго своего хода, но нет гарантированной победы первым ходом. Роли игроков зависят от условия.

Ответодно число или пара

Теория

Что нужно знать

Задания 19–21 проверяют одну и ту же идею — умение играть в дискретную игру без случайности и просчитывать стратегию на несколько ходов. Сначала читаем правила, затем строим дерево или рекурсию, и только потом отвечаем на конкретный вопрос.

Минимум для заданий 19–21

читать правила и находить условие окончания
определять, кто делает первый ход
выписывать все ходы из позиции
размечать выигрышные и проигрышные позиции
считать ходы по уровням
понимать any/all в рекурсии
различать «первым ходом» и «не позже»
перебирать все S из диапазона
проверять оба значения для задания 20
записывать ответ в нужном формате

Три задания — одна игра

Формально это три независимых задания, но в каждом варианте они опираются на одну игровую конструкцию. Меняется только вопрос: в 19 ищут позицию, в 20 — два значения, в 21 — стратегию и число ходов.

19: частый вариант — «Петя не может выиграть первым ходом, но Ваня выигрывает своим первым».
20: частый вариант — «Петя не выигрывает первым, но выигрывает вторым при любых ходах Вани».
21: «у игрока есть стратегия на первый или второй ход, но нет гарантии победы первым».
Формулировки меняются местами: роли Петя/Ваня и номера 19/20/21 могут отличаться от привычной схемы.
Главное — не номер задания, а вопрос: кто, каким ходом и при каких условиях выигрывает.

19: одна позиция или одно значение S20: два значения S21: стратегия и число ходов

Позиция и терминальное состояние

Позиция — это всё, что нужно знать об игре в данный момент. У одной кучи это число S, у двух куч — пара (a, b), у трёх — тройка (a, b, c). Терминальное состояние задаётся условием окончания.

Порог: S ≥ N, S ≤ N, a + b ≥ N, a · b ≥ N, |a − b| ≥ N.
Свойство: простое число, палиндром, диапазон 666–999.
Ход может менять одну кучу, обе кучи или все три.
Если после перебора (например, больше 999) игрок проигрывает, terminal состоит из двух зон.
Терминальную проверку всегда делайте до проверки m == 0.

нормальная игра: кто первым достиг терминала, тот выигралmisère: кто первым достиг терминала, тот проиграл

Выигрышные и проигрышные позиции

Разметка строится с конца. Терминальная позиция считается проигрышной для того, чей ход: ходов больше нет. Дальше двигаемся назад по дереву.

Проигрышная (L): все ходы ведут в выигрышные позиции.
Выигрышная (W): есть хотя бы один ход в проигрышную.
Стратегия — на каждом своём ходу переводить игру в L.
Если позиция W, соперник не может изменить исход при правильной игре.
В задачах 19–21 чаще нужна не сама разметка, а позиция на нужном уровне дерева.

W = существует ход в LL = все ходы ведут в W

Дерево и счёт ходов

Уровни дерева чередуются: Петя, Ваня, Петя, Ваня. Номер хода — это номер полухода, а не номер игрока. Поэтому «второй ход Пети» — это третий полуход.

Петя: 1-й, 3-й, 5-й ход; Ваня: 2-й, 4-й, 6-й.
«Петя первым ходом» — m = 1; «Ваня своим первым» — m = 2.
«Петя вторым» — m = 3; «Ваня вторым» — m = 4.
«Не позже второго хода» — проверяйте и первый, и второй ход.
«За два хода» может означать два хода каждого — читайте формулировку буквально.

m = 1 — Петя, m = 2 — Ваня, m = 3 — Петя, m = 4 — Ванянечётное m — победа Пети, чётное m — победа Вани

Одна куча

Состояние — одно число S. Ходы могут прибавлять, умножать, вычитать, делить или менять число по особому правилу. Порог может быть фиксированным или зависеть от начального S.

Типовые ходы: +k, +m, ×k, −k, //k, x², добавить сумму цифр.
Если ход зависит от чётности или делимости, перебирайте только разрешённые ходы.
Порог может быть фиксированным (N) или зависеть от S (например, 4S).
Стартовое S часто от 1 до N − 1; не включайте терминальные значения.
Для убывающих игр проверяйте, что ход не уводит в отрицательные значения.

f(s, m): s ≥ N → m % 2 == 0f(s, m): s ≤ N → m % 2 == 0

Две кучи

Состояние — пара (a, b). Ход может менять одну кучу или обе; это даёт два или четыре варианта. Фиксированная первая куча превращает задачу в перебор по S.

Выписывайте все ходы: (a + k, b), (a, b + k), (ka, b), (a, kb).
Если первая куча фиксирована, считайте f(11, s, m), f(13, s, m) и т. п.
Симметричные ходы (a + 2, b) и (a, b + 2) — разные позиции.
Терминал может быть по сумме, произведению, разности, максимуму или равенству.
Если кучи равны и правило особое, добавьте условие в генератор ходов.

f(a, b, m): терминал по a + b, a · b или |a − b|ходы: (a + k, b), (a, b + k), (ka, b), (a, kb)

Нестандартные правила

В базе Kompege много вариантов с тремя кучами, табличкой, числом, запретом повторять ход и бонусными ходами. Все они решаются тем же шаблоном — меняется только генератор ходов и terminal.

Три кучи и табличка: состояние — кортеж; ход может менять все компоненты.
Ход зависит от числа: чётность, кратность, остаток, сумма цифр, система счисления.
Нельзя повторять последний ход: передавайте last_move в рекурсию.
Бонусный ход один раз: добавьте флаг used_bonus.
Диапазон выигрыша: 666–999 — победа, больше 999 — поражение.
Убывающая игра с проигрышем за terminal: инвертируйте условие победы.
Три игрока: ходы циклические, победа определяется на своём уровне.

состояние может быть числом, парой, тройкой или кортежемсначала terminal, потом генерация ходов

Шаблон f(pos, m)

Почти все программные решения из базы используют одну рекурсию. m — число полуходов, за которые проверяется победа. Чётность m задаёт игрока, а any/all — характер требования.

Сначала проверьте terminal — до проверки m == 0.
Terminal возвращает m % 2 == 0: на чётном m победа у Вани, на нечётном у Пети.
Если m == 0 и terminal не достигнут, текущий игрок не успел — возвращаем 0.
Сгенерируйте все ходы и вызовите f(child, m − 1).
Для нечётного m (Петя) — any; для чётного (Ваня) — all.
Для больших диапазонов добавьте lru_cache.

if terminal: return m % 2 == 0if m == 0: return 0m % 2 == 1 → any(...), m % 2 == 0 → all(...)

Почему any и all чередуются

На нечётном уровне ходит Петя: ему достаточно одного хорошего хода, поэтому any. На чётном уровне ходит Ваня: Петя должен быть готов к любому ответу, поэтому all.

Нечётный уровень — выбор Пети, поэтому any.
Чётный уровень — гарантия Вани при любом ходе Пети, поэтому all.
Если перепутать any и all, роли игроков и ответы 19/20/21 поменяются.
В задачах «Ваня выиграл после неудачного хода Пети» на первом уровне тоже any: Пете не нужно выбирать лучший ход.
В решениях из базы иногда меняют all на any для № 19 — это то же правило, записанное иначе.

19: f(s, 2) или not f(s, 1) and f(s, 2)20: not f(s, 1) and f(s, 3)21: not f(s, 2) and f(s, 4)

Границы, перебор и проверка

Большая часть ошибок — не в рекурсии, а в границах и в неполном переборе. Определите диапазон S по условию и проверьте, что игра вообще завершается.

Верхняя граница перебора — по условию; не берите N вместо N − 1 без причины.
Если ход умножает, terminal должен срабатывать раньше, чем рекурсия уйдёт в бесконечность.
Для убывающих игр ограничьте снизу; не допускайте отрицательных куч.
Для больших S используйте lru_cache и не храните лишние состояния.
Проверьте найденное S вручную по дереву хотя бы на 2–3 хода.
Если ответ — два числа, проверьте оба и их порядок.

диапазон: range(1, N) или range(lo, hi + 1)ответ: min, max, sorted(...)[:2], sum или len

Формат ответа

Ответы 19–21 короткие, но именно в них чаще всего теряют балл: не тот порядок, лишнее число или сумма вместо количества.

19: чаще одно число — минимум, максимум, сумма или количество.
20: два числа; почти всегда «два наименьших» или «два наибольших».
21: одно число или пара; читайте, что именно просят.
Если просят сумму или количество — не записывайте сами значения.
Разделяйте числа пробелом, без запятых и единиц измерения.
Не добавляйте пояснения в поле ответа.

одно число — без пробеловдва числа — через пробел в порядке условия

План решения на экзамене

В заданиях 19–21 ценится не скорость перебора, а аккуратная модель. Сначала правило и terminal, потом маленький пример, и только затем код и перебор S.

Прочитайте, кто ходит первым и что считается победой.
Выпишите все ходы и условие окончания.
Разберите маленький пример вручную на 2–3 хода.
Напишите f(pos, m) и проверьте её на этом примере.
Переберите S и примените фильтр нужного задания.
Проверьте один ответ по дереву и запишите его без пояснений.

правило → terminal → пример → рекурсия → перебор → проверка

Разбор примера

Учебный пример: одна куча, +1 или ×2

Куча S, ход +1 или ×2, игра заканчивается, когда камней становится не менее 10. Петя ходит первым. Найдите ответы для 19, 20 и 21.

Значения f(S, m): 1 — победа игрока, который делает ход на уровне m; 0 — победы нет.
S	m=1 Петя 1-м	m=2 Ваня 1-м	m=3 Петя 2-м	m=4 Ваня 2-м
1	0	0	0	1
2	0	0	1	0
3	0	0	1	0
4	0	1	0	1
5	1	0	1	0
6	1	0	1	0
7	1	0	1	0
8	1	0	1	0
9	1	0	1	0

Терминал: S ≥ 10. При m = 1 Петя может сразу закончить игру, поэтому у S = 5…9 стоит 1.
При m = 2 Ваня выигрывает своим первым ходом только из S = 4: из 5 он делает 10, из 8 — 16.
Для задания 19 берём минимальное S с f(S, 2) = 1: это 4.
Для задания 20 нужны S, где f(S, 1) = 0 и f(S, 3) = 1: это 2 и 3.
Для задания 21 нужно S, где f(S, 2) = 0 и f(S, 4) = 1: это 1.
Проверка для S = 4: Петя делает 4 → 5 или 4 → 8; в обоих случаях у Вани есть ход до 10 или 16.

Ответ19: 4; 20: 2 и 3; 21: 1.

Способы решения

Выберите метод под формулировку

Методы собраны по решениям заданий 19–21 из базы Kompege. Начните с того, что именно нужно найти в условии.

когда позиций немного

Дерево игры вручную

Когда использовать: Правило простое, S небольшое, нужно понять, кто и на каком ходе выигрывает.

Выпишите стартовую позицию и все ходы из неё.
Нарисуйте уровни: Петя, Ваня, Петя, Ваня.
Отметьте терминальные позиции и того, кто в них выигрывает.
Снизу вверх: позиция выигрышная, если есть ход в проигрышную.
Отметьте, на каком уровне находится победа: 1 — Петя первым, 2 — Ваня первым и т. д.
Проверьте все ходы, а не только очевидный.

Пример

Куча S, ход +1 или ×2, игра до S ≥ 10. Разберём S = 4.

4 (Петя)
├─ +1 → 5 (Ваня) ── ×2 → 10  ✔ Ваня
└─ ×2 → 8 (Ваня)
   ├─ +1 → 9 (Петя) ── +1 → 10  ✘ Ваня проигрывает
   └─ ×2 → 16  ✔ Ваня

ОтветПетя не может выиграть первым ходом, а Ваня выигрывает своим первым: S = 4.

По мотивам решений задач № 10128, 21156 и 31035; пример переработан в учебный.

стандартная рекурсия

Одна куча: шаблон f(s, m)

Когда использовать: Одна куча, фиксированный порог, 2–3 хода, нужно перебрать все S.

Определите терминал и диапазон S по условию.
Напишите f(s, m): сначала terminal, затем m == 0.
Сгенерируйте все ходы из s.
Верните any для нечётного m и all для чётного.
Посчитайте f(s, 1), f(s, 2), f(s, 3) и f(s, 4) для всех S.
Отфильтруйте значения по формулировке 19, 20 или 21.

Пример

S от 1 до 247, ходы +1, +2 или ×3, игра до S ≥ 248 (задача № 10128).

def f(s, m):
    if s >= 248:
        return m % 2 == 0
    if m == 0:
        return 0
    moves = (s + 1, s + 2, s * 3)
    h = [f(x, m - 1) for x in moves]
    return any(h) if m % 2 else all(h)

print(min(s for s in range(1, 248) if f(s, 2)))              # 19 → 82
print(*[s for s in range(1, 248)
        if not f(s, 1) and f(s, 3)][:2])                      # 20 → 80 81
print(min(s for s in range(1, 248)
          if not f(s, 2) and f(s, 4)))                        # 21 → 79

Ответ19: 82; 20: 80, 81; 21: 79.

По мотивам задач № 10128, 11279, 31035 и 21156 (база Kompege).

фиксированная первая куча

Две кучи: состояние (a, b)

Когда использовать: Перед игроками две кучи; ход меняет одну из них, а вторая куча часто фиксирована.

Запишите состояние как пару (a, b).
Выпишите все ходы: изменить первую, изменить вторую.
Определите терминал по сумме, произведению или другому выражению.
Для фиксированной первой кучи считайте f(11, s, m) или f(13, s, m).
Переберите S и примените фильтр нужного задания.
Проверьте, что оба хода из пары учтены.

Пример

Первая куча 11, вторая S, ходы +2 или ×2, игра до суммы 131 (задача № 11275).

def f(a, b, m):
    if a + b >= 131:
        return m % 2 == 0
    if m == 0:
        return 0
    moves = ((a + 2, b), (a * 2, b), (a, b + 2), (a, b * 2))
    h = [f(x, y, m - 1) for x, y in moves]
    return any(h) if m % 2 else all(h)

print(min(s for s in range(1, 123) if f(11, s, 2)))          # 19 → 64
print(*[s for s in range(1, 123)
        if not f(11, s, 1) and f(11, s, 3)][:2])             # 20 → 32 62
print(min(s for s in range(1, 123)
          if not f(11, s, 2) and f(11, s, 4)))               # 21 → 60

Ответ19: 64; 20: 32 и 62; 21: 60.

По мотивам задач № 11275, 11278, 16883 и 31481; у № 11275 есть видеоразбор.

состояние-кортеж

Три кучи и табличка

Когда использовать: Куч три, есть табличка с парой чисел или ход меняет сразу несколько компонентов.

Запишите состояние как кортеж: (a, b, c) или (x, y).
Сгенерируйте ходы, которые меняют одну или все компоненты.
Проверьте terminal по максимуму, сумме или отдельному числу.
Не забывайте про ограничения на каждую компоненту.
Переберите S и примените фильтр 19/20/21.
Проверьте один ответ вручную по дереву.

Пример

Три кучки 2, 3 и S; ход — удвоить одну кучу или добавить по 2 во все; terminal — max ≥ 20 или сумма ≥ 25 (задача № 14954).

def f(p, m):
    a, b, c = p
    if max(a, b, c) >= 20 or a + b + c >= 25:
        return m % 2 == 0
    if m == 0:
        return 0
    moves = ((2*a, b, c), (a, 2*b, c), (a, b, 2*c),
             (a + 2, b + 2, c + 2))
    h = [f(q, m - 1) for q in moves]
    return any(h) if m % 2 else all(h)

print(min(s for s in range(1, 20) if f((2, 3, s), 2)))       # 19 → 9
print([s for s in range(1, 20)
       if not f((2, 3, s), 1) and f((2, 3, s), 3)])          # 20 → 2, 3, ...
print(min(s for s in range(1, 20)
          if not f((2, 3, s), 2) and f((2, 3, s), 4)))       # 21 → 6

Ответ19: 9; 20: 2 и 3 (два наименьших); 21: 6.

По мотивам задачи № 14954 (условие и видеоразбор) и № 9166 (табличка с парой чисел).

игра «на вычитание»

Уменьшение и деление

Когда использовать: Игроки убирают камни или делят кучу; игра заканчивается при s ≤ N.

Запишите terminal: s ≤ N; победитель — тот, кто сделал последний ход.
Для деления используйте //, а при округлении вверх — (x + 1) // 2.
Проверьте, что ход не уводит в отрицательные значения.
Если terminal приносит поражение (misère), инвертируйте условие победы.
Для запрета повторять ход передавайте last_move в рекурсию.
Переберите S от N + 1 до разумной верхней границы.

Пример

Куча S, ходы −2, −6 или //4, игра до S ≤ 18 (задача № 29588).

def f(s, m):
    if s <= 18:
        return m % 2 == 0
    if m == 0:
        return 0
    moves = (s - 2, s - 6, s // 4)
    h = [f(x, m - 1) for x in moves]
    return any(h) if m % 2 else all(h)

print(max(s for s in range(19, 1000) if f(s, 2)))            # 19 → 77
print(*[s for s in range(19, 1000)
        if not f(s, 1) and f(s, 3)][:2])                     # 20 → 78 79
print(min(s for s in range(19, 1000)
          if not f(s, 2) and f(s, 4)))                       # 21 → 80

Ответ19: 77 (наибольшее S); 20: 78 и 79; 21: 80.

По мотивам задач № 29588, 13912, 31227 и 16266; у № 16266 есть видеоразбор.

сумма, произведение, разность, простое число

Нестандартное условие окончания

Когда использовать: Игра заканчивается не по порогу одной кучи, а по сумме, произведению, разности или свойству числа.

Выпишите terminal как единое условие.
Если условий несколько, используйте or.
Для произведения и разности проверяйте порядок чисел.
Для простого числа напишите is_prime и проверяйте его до ходов.
Для диапазона 666–999 добавьте вторую зону: больше 999 — поражение.
Проверьте, что terminal не пересекается с допустимыми ходами.

Пример

Две кучи, первая 3, вторая S; ходы +2 или ×2; игра до произведения ≥ 123 (задача № 9374).

def f(a, b, m):
    if a * b >= 123:
        return m % 2 == 0
    if m == 0:
        return 0
    moves = ((a + 2, b), (a * 2, b), (a, b + 2), (a, b * 2))
    h = [f(x, y, m - 1) for x, y in moves]
    return any(h) if m % 2 else all(h)

print(min(s for s in range(1, 41) if f(3, s, 2)))            # 19 → 19
print(*[s for s in range(1, 41)
        if not f(3, s, 1) and f(3, s, 3)][:2])               # 20 → 9 10
print(min(s for s in range(1, 41)
          if not f(3, s, 2) and f(3, s, 4)))                  # 21 → 15

Ответ19: 19; 20: 9 и 10; 21: 15.

По мотивам задач № 9374, 31480, 31481, 28431, 28875 и 23336.

главный навык заданий 19–21

Формулировка → фильтр

Когда использовать: Рекурсия уже написана; осталось правильно прочитать, какой именно ход и какая гарантия нужны.

«Ваня выиграл первым после неудачного хода Пети» → f(s, 2).
«Петя не может первым, но выигрывает вторым» → not f(s, 1) and f(s, 3).
«Ваня выигрывает первым или вторым, но не гарантирует первым» → not f(s, 2) and f(s, 4).
«Петя выигрывает не позже второго хода» → f(s, 1) or f(s, 3).
«Ровно вторым ходом» → not f(s, 1) and f(s, 3).
«Найдите два наименьших» → sorted(a)[:2]; «два наибольших» → sorted(a)[-2:].

Пример

Универсальные фильтры для одной и той же функции f(s, m).

a19 = [s for s in range(1, N) if f(s, 2)]
a20 = [s for s in range(1, N) if not f(s, 1) and f(s, 3)]
a21 = [s for s in range(1, N) if not f(s, 2) and f(s, 4)]

print(min(a19))            # минимальное S для 19
print(*sorted(a20)[:2])    # два наименьших для 20
print(min(a21))            # минимальное S для 21

ОтветДля задачи № 10128: 82; 80 и 81; 79.

По мотивам задач № 10128, 11276, 21156 и 31433.

чтобы не потерять балл

Проверка и оформление ответа

Когда использовать: Ответ уже найден; нужно проверить его и записать в нужном формате.

Убедитесь, что перебраны все S из диапазона.
Проверьте один ответ вручную по дереву на 2–3 хода.
Примените агрегат: min, max, sorted, sum или len.
Проверьте, что в 20 именно два значения, а не одно.
Проверьте порядок чисел, если он важен.
Запишите ответ без пояснений и единиц.

«Сумма найденных» → sum(a), а не сами значения.
«Количество» → len(a), а не сумма.
«Два наименьших» → sorted(a)[:2]; «два наибольших» → sorted(a)[-2:].
«Минимальное» → min(a); «максимальное» → max(a).
Если ответ — пара, сначала число, которое просят первым.
Не добавляйте пробелы внутри числа и запятые между числами.

Пример

Оформление ответов для трёх заданий.

print("19:", min(a19))
print("20:", *sorted(a20)[:2])
print("21:", min(a21))

# если просят сумму или количество:
# print(sum(a20))
# print(len(a20))

ОтветТри строки ответа: 19 — одно число, 20 — два числа, 21 — одно число.

По мотивам решений задач № 10128, 11275, 21156, 29588 и 31482.

Шпаргалка: формулировка → метод

В условии	Что делать
«Петя не может первым, Ваня выигрывает первым»	f(s, 2)
«Петя выигрывает вторым, но не первым»	not f(s, 1) and f(s, 3)
«Ваня выигрывает первым или вторым»	f(s, 2) or f(s, 4)
«...но не гарантирует победу первым»	not f(s, 2) and f(s, 4)
«два наименьших S»	sorted(a)[:2]
«два наибольших S»	sorted(a)[-2:]
«сумма найденных S»	sum(a)
«количество значений S»	len(a)
«одна куча»	f(s, m) и список ходов
«две кучи»	f(a, b, m) и четыре хода
«три кучи»	f((a, b, c), m)
«убрать или уменьшить»	terminal s ≤ N, победитель — последний ход
«нельзя повторять ход»	передавать last_move в рекурсию
«бонус один раз»	флаг used_bonus
«666–999 победа, >999 поражение»	две terminal-зоны
«ответ — два числа»	записать через пробел в порядке условия

Видеоразборы по теме

Видеоразборы открытого курса КомпЕГЭ; для заданий 8–12 и 27 — дополнительные разборы демоверсии 2027.

По базе Kompege: 835 задач по теме «теория игр» (в базе вся тема отмечена номером 19, поэтому статистика общая для 19–21), 62 решения (58 программных и 4 текстовых) и 239 видеоразборов (163 YouTube, 45 VK, 31 Rutube). Страницы 19, 20 и 21 объединены, потому что это одна игра с тремя вопросами. При подготовке методов использованы решения задач № 10128, 11275, 11276, 11279, 11280, 11282, 11284, 11285, 11287, 11627, 11720, 12750, 14316, 15196, 16266, 16306, 16587, 16707, 16883, 17099, 17808, 17986, 19750, 20427, 21156, 21856, 22477, 23329, 23451, 23592, 25863, 27456, 28431, 28875, 29588, 30016, 31035, 31433, 31480, 31481, 31482 и 31483; дополнительно использованы условия и видеоразборы задач № 7091, 4110, 3581, 14954, 13912, 9374, 9166, 10721, 31227, 13960, 22437 и 20528; примеры переработаны в учебные.

Разборы из видео

Задачи, которые разбирают в курсе

Условия и код показаны в кадре в конце соответствующего фрагмента. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие.

Задание 19

разбор из видео · 2024

Одна куча: +1 и ×3

Петя и Ваня играют с одной кучей камней; ходы +1 и ×3; побеждает тот, после чьего хода в куче не менее 30 камней. S от 1 до 29. Найдите S, при котором Петя не выигрывает первым ходом, а Ваня выигрывает своим первым ходом при любом ходе Пети.

Ответ9

Смотреть с 51:55

Задание 20

разбор из видео · 2024

Победа Пети вторым ходом

Та же игра: одна куча, ходы +1 и ×3, победа при 30 камнях. Найдите S, при котором Петя не выигрывает первым ходом, но выигрывает вторым при любом ходе Вани.

Ответ3 или 8

Смотреть с 51:55

Задание 21

разбор из видео · 2024

Стратегия Вани не позже второго хода

Та же игра. Найдите S, при котором у Вани есть стратегия победы не позже второго хода, но нет гарантированной победы первым ходом.

Ответ7

Смотреть с 51:55

Полный архив

Все фрагменты видеоразборов

По одному пункту на каждую главу: условие или код из кадра, ответ и ссылка. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие; номер берётся из кадра. Текст с экрана распознан автоматически, служебные строки и артефакты удалены; если текст нечитаем, остаются название, таймкод и ссылка.

Показать все фрагменты (38)

2024 · 00:00 Приветствие

Определите минимальное 1 максимальное значения S, при которых у Пети есть вышшрышная стратегия, причём одновременно выполняются ва условия: — Петя не может выиграть за один xox, — Петя может выпграть своим вторым ходом независимо от того, как будет ходить Ваня. "найденные значения запишите в ответе в порядке возрастания. Найдите значение $, при котором одновременно выполняются два условия: — У Вани есть выигрышная стратегия, позволяющая ему вышграть первым или вторым ходом при любой pe Пети; — У Вани нет стратегии, которая позволит ему гарантированно выиграть первым холом.

Смотреть с 00:00

2024 · 01:50 Что разбираем, прогноз 2022

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 01:50

2024 · 04:30 Выигрышные и проигрышные позиции

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 04:30

2024 · 24:10 Поиск необходимых значений

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 24:10

2024 · 51:55 Анализ игры пример 1

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 51:55

2024 · 1:07:10 Анализ игры пример 2

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:07:10

2024 · 1:16:55 Анализ игры пример 3

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:16:55

2024 · 1:23:30 РЕКЛАМА

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:23:30

2024 · 1:27:50 Ограничение на победу

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:27:50

2024 · 1:46:20 Анализ игры пример 5

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:46:20

2024 · 1:58:40 Игра c конфетами

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:58:40

2024 · 2:09:45 Вариативные ходы

Определите, минимальное и максимальное значения S, при которых у Пети есть выпгрышная стратегия, причём одновременно выполняются вл условпя: — Петя не может вышграть 3a один ход; "Найденные значения запишите в ответе в порялке возрастания. Найдите минимальное значение $, при котором одновременно выполняются лва условия: — у Вани есть вышгрышная стратегия, позволяющая ему вышграть первым или вторым ходом при люб ": которая позволит ему гарантированио выпграть первым ходом.

Смотреть с 2:09:45

2024 · 2:27:10 Двоичные числа

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 2:27:10

2024 · 2:33:20 Игра со строками

Для игры, описанной в 19 задании, определите, сколько букв содержит самое: при записи которого, выигрывает Ваня, независимо от того, как будет Из букв А и Бо составляются две символьные последовательности (два "слова). Первое слово длиною 3 символа, второе длиною 6 символов. "Для игры, описанной в задании 19, определите, какое количество различных пар "слов можно составить, чтобы всегда выигрывал Ваня, независимо от того, как будет 'Например, для пары слов АБА и АААААА выигрывает Ваня. Его выигрышная стратегия заключается в том, чтобы первым ходомиаписать букву А

Смотреть с 2:33:20

2024 · 2:51:10 Окончание и напутствия

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 2:51:10

2024 · 00:00 Приветствие

Смотреть с 00:00

2024 · 03:35 Про обновление функции

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 03:35

2024 · 11:00 Как работает функция наглядно

ходом при любой urpe Пети. причём одновременно выполняются два условия: — Петя может выиграть свопы вторым ходом независимо от того, как будет ходить Ваня. Найдите два значения S, при которых одновременно выполняются лез условия: — У Вани есть вышгрышная стратегия, позволяющая ему вышграть первым или вторым ходом при —у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. "Найденные значения запишите в ответе в поряке возрастания.

Смотреть с 11:00

2024 · 32:00 Одна куча камней

Найдите минимальное значение $. при котором Ваня выигрывает своим первым. ходом при любой игре Пети, Сколько сушествует значений $, при которых y Пети есть вышгрышная стратеги, причём одновременно выполняются два условия: — Петя может вышграть своим вторым ходом независимо OF того, как будет ходить Ваня. Найдите минимальное п максимальное значения S, при которых одновременно — у Вани есть выпгрышная стратеги, позволяющая ему выиграть первым или вторым ходом при — Вани нет стратегии, которая позволит ему гарантированно вышграть первым ходом. Наденные значения запишите в ответе в порялке возрастания.

Смотреть с 32:00

2024 · 43:00 Одна куча камней (с проигрышем)

Найдите sa таких значения $. при которых у Пети есть вышгрышная стратегия, причём Петя не может вышграть первым ходом, но может вышграть своим вторым ходом независимо от Toro, как будет ходить Ваня. Найденные значения запишите в ответе в порядке Вопрос 3. Укажите такое значение S, при котором у Вани есть вышгрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно вышграть первым ходом.

Смотреть с 43:00

2024 · 49:10 Две кучи камней

Найдите значение S, при котором Ваня вышгрывает своим первым холом при любой Найдите минимальное п максимальное значение S, при котором у Пети есть вышгрышная стратегия, причём одновременно выполняются два условия: — Петя не может вышграть за один ход: — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. "Найденные значения запишите в ответе в порядке возрастания. Найдите значение S, при котором одновременно выполняются лва условия: —y Вани есть вышгрышная стратегия, позволяюшая ему выпграть первым или вторым ходом при" = ь —y Вани нет стратегии, которая позволит ему гарантированно выпграть первым ходом.

Смотреть с 49:10

2024 · 57:15 Две кучи камней (с уменьшением)

Ответьте на следующие вопросьг Найдите значение S, при котором Ваня вышгрывает своим первым холом при любой Найдите минимальное п максимальное значение S, при котором у Пети есть вышгрышная стратегия, причём одновременно выполняются два условия: — Петя не может вышграть за один ход: — Петя может выиграть своим вторым ходом независимо OT того, как будет ходить Ваня. Найдите значение S, при котором одновременно выполняются лва условия: — у Вани есть вышгрышная стратегия, позволяюшая ему вышграть первым или вторым ходом при —y Вани нет стратегии, которая позволит ему гарантированно выпграть первым холом.

return any(h) if (m-1)%2=20 else all(h)
print('19)',[s for s in range(11,1000) if f(10,s,2)])

Смотреть с 57:15

2024 · 1:03:02 Две кучи камней

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно — Петя He может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо OT того, как будет ходить Ваня. найденные значения запишите в ответ в порядке возрастания. Для игры, описанной в задании 19, найдите два значения S, при котором одновременно выполняются три условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом; = Ваня может выиграть первым ходом после одного из ходов Пети.

Смотреть с 1:03:02

2024 · 1:10:45 Проверка ходов II

‚Для игры, описанной в задании 19, найдите два наименьших значения $, при которых у Пети есть выигрышная стратегия, причём одновременно — Петя не может выиграть за один ход: = Петя может выиграть своим вторым ходом независимо OT того,как будет ходить Ваня в n Ans игры, описанной в задании 19, найдите два значения S, при котором одновременно выполняются три условия (1,3 ) (13, 5) — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети р — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходо! = Ваня может выигроть первым ходом после одного из ходов Пети.

Смотреть с 1:10:45

2024 · 1:29:00 Проверка ходов II

Найдите минимальное п максимальное значения 5. при которых Петя выигрывает вторым ходом при любом ходе Вани. Найдите значение S, при котором одновременно выполняются лва условия: а) у Вани есть выпгрышная стратегия. позволяющая ему выиграть первым или вторым ходом при любой игре Пети: которая позволит ему гарантированно выиграть первым ходом.

Смотреть с 1:29:00

2024 · 1:41:20 Перебор двух куч

Найдите минимальное п максимальное значения S, при которых Петя выпгрывает вторым ходом при любом ходе Вани.

Смотреть с 1:41:20

2024 · 1:51:50 Три кучи камней

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

if m return @
return any(h) if (m-1)%2==0 else all(h)

Смотреть с 1:51:50

2024 · 1:56:15 Окончание и напутствия

Найдите минимальное и максимальное значения $, при которых Петя вышгрывает вторым холом при любом ходе Вани. Найлите значение $, при котором одновременно выполняются два условия: а) у Вани есть выпгрышная стратегия, позволяющая ему выиграть первым или вторым холом при любой игре Пети; 6) у Вани нет стратегии, которая позволит ему гарантированно выштрать первым ходом.

Смотреть с 1:56:15

2024 · 00:00 Приветствие

Смотреть с 00:00

2024 · 02:30 Нельзя повторять ход противника

h+=[f(s+2,m-1, °+2°)]
return any(h) if m%2!=@ else all(h)

Смотреть с 02:30

2024 · 18:35 Нельзя повторять свой пред ход

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 18:35

2024 · 39:50 Ограничение ходов по камням I

стратегия, причём Петя не может выпграть первым ходом. но может вышрать своим в ответе в порядке возрастания. — стратеги, позволяющая ему выиграть вторым ходом при любой игре Пети.

Смотреть с 39:50

2024 · 48:00 Ограничение ходов по камням II

"Найденные значения запишите в ответе в порялке возрастания. — Вани есть вышгрышная стратеги, позволяющая ему выиграть первым или вторым ходом при любой пгре Пети: — y Вани нет стратепит которая позволит ему гарантированно выиграть первым ходом: — Петя может выбирать, каким ходом выиграет Ваня.

Смотреть с 48:00

2024 · 59:40 Ограничение ходов по камням III

Известно, что в первой куче 25 камней, а во второй — $ камней (1 5$ < 77), Найдите наименьшее и напбольшее значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть 3a один ход: — Петя может выиграть своим вторым ходом независимо OT того, как будет ходить Ваня. запишите в ответе сначала наименьшее значение, потом — наибольшее. Известно, что в первой куче 69 камней, а во второй — $ камней (1 =$ < 77), Найдите значение $. при котором одновременно выполняются два условия: — у Вани есть вышгрышная стратегия, позволяющая ему выпграть первым или вторым холом при любой игре Пети — У Вани н

Смотреть с 59:40

2024 · 1:12:25 Ограничение ходов по камням IV

Назовите минимальное значение S, при котором это возможно. Найленные значения запишите в ответе в Найдите наибольшее и наименьшее значения 5, при которых у Вани есть вышгрышная стратегия. Найденные значения запишите в ответе в порядке возрастания.

Смотреть с 1:12:25

2024 · 1:24:30 Задача с суперходом

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:24:30

2024 · 1:40:50 Гроб из Кулабуховой

def f(a,bym):
return ©
return any(h) if m%2!=0 else all(h)

Смотреть с 1:40:50

2024 · 1:53:45 Окончание и напутствия

def f(a,bym):
if a=20 or
return m&2:
return @
return any(h) if m%2!=0 else all(h)

Смотреть с 1:53:45

Типичные ошибки

перепутан игрок или номер хода
учтены не все ходы
неверное терминальное условие
ошибка на единицу в диапазоне S
перепутаны any и all
найдено одно значение вместо двух
не проверен порядок чисел в ответе

Практика

ФИПИОткрытый банк заданий Навигатор · 2026Теория ДемоверсияКИМ 2027 МетодикаРазбор ошибок 2026

Навигатор и методические рекомендации опубликованы в 2026 году: номера заданий в них могут отличаться от нумерации 2027 года. Ориентируйтесь на тему.