4 Разбор задач
Разбор задач
Все задачи ниже взяты из официальных источников: демоверсий ФИПИ, реальных вариантов ЕГЭ, ЕГКР и апробаций.
Разбираем каждый комплект двумя способами: сначала быстрый ручной взгляд через «зону финиша», потом Python — универсальный и надёжный. На реальном ЕГЭ хватит любого из них, но полезно уметь оба: код — основной, ручной — для проверки и для быстрого 19-го.
💡 Что такое «зона финиша» (пригодится во всех ручных разборах) Зона финиша — это все позиции, из которых можно закончить игру за один ход. Кто попал в зону — тот выигрывает своим ходом. А «горячая» позиция — та, из которой сам финишировать нельзя, но любой твой ход загоняет соперника в зону финиша. Кто ходит из «горячей» позиции — проигрывает: соперник добьёт следующим ходом. Именно «горячие» позиции — это ответы задания 19. |
Задача 1. Одна куча: +1, +4, ×2 (финиш ≥ 51)
Условие Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней становится не менее 51. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней, 1 ≤ S ≤ 50. |
Ручной разбор
Найдём зону финиша — из каких позиций можно за один ход набрать ≥ 51. Самый «мощный» ход — удвоение: 2·s ≥ 51 при s ≥ 26. Значит, из любой позиции 26…50 можно финишировать. Зона финиша: [26; 50].
Теперь горячая позиция — та, из которой сам не финишируешь (s ≤ 25), но любой ход попадает в [26; 50]. Наименьший ход s+1, наибольший 2s. Нужно s+1 ≥ 26 (то есть s ≥ 25) и 2s ≤ 50 (то есть s ≤ 25). Остаётся ровно s = 25: ходы дают 26, 29, 50 — все в зоне финиша. Значит, 25 — единственная горячая позиция.
Прототип 19 (минимальное S, где Петя не выиграет за ход, но Ваня выиграет первым): это и есть горячая позиция → S = 25.
Прототип 20 (два наименьших S, где Петя выигрывает вторым ходом): Пете надо суметь сходить в горячую позицию 25. Откуда попадаем в 25?
s+1=25 → s=24,s+4=25 → s=21,2s=25— нельзя. Оба (21 и 24) меньше 26, значит сам Петя не финиширует. Два наименьших → 21 и 24.Прототип 21 (S, где Ваня выигрывает 1-м или 2-м ходом, но не гарантированно 1-м; берём наименьшее): при любом ходе Пети Ваня добирается до победы не позже второго хода, но у Пети есть ход, лишающий Ваню мгновенной победы. Наименьшее такое → S = 20 (ходы Пети 21, 24, 40: из 21 и 24 Ваня идёт в 25, из 40 — сразу финиш).
Решение на Python
def F(s, p): # s — камней, p — глубина просмотра
if s >= 51: # финиш: набрали не менее 51
return p % 2 == 0
if p == 0:
return False
hod = [F(s + 1, p - 1), # ходы из условия: +1, +4, ×2
F(s + 4, p - 1),
F(s * 2, p - 1)]
return any(hod) if p % 2 == 1 else all(hod)
print("19:", [s for s in range(1, 51) if F(s, 2)]) # [25]
print("20:", [s for s in range(1, 51) if F(s, 3) and not F(s, 1)]) # [21, 24]
print("21:", [s for s in range(1, 51) if F(s, 4) and not F(s, 2)]) # [20, 23]Прототип 19 просит минимальное — берём 25. Прототип 20 просит два наименьших — 21 и 24. Прототип 21 просит наименьшее из найденных — из [20, 23] берём 20.
Ответ 19: 25 |
Ответ 20: 21 24 |
Ответ 21: 20 |
Задача 2. Одна куча: +2, +5, ×2 (финиш ≥ 128)
Условие Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в кучу 2 камня; добавить в кучу 5 камней; увеличить количество камней в куче в 2 раза. Игра завершается, когда камней становится не менее 128. Победителем считается игрок, сделавший последний ход. В начальный момент было S камней, 1 < S < 127. |
Ручной разбор
Зона финиша: 2·s ≥ 128 при s ≥ 64. Значит из [64; 127] можно финишировать одним удвоением.
Горячие позиции: сам не финиширует (s ≤ 63), но все ходы в [64; 127]. Наименьший ход s+2 ≥ 64 → s ≥ 62; наибольший 2s ≤ 127 → s ≤ 63. Подходят s = 62 и s = 63 (проверка: 62 → 64, 67, 124; 63 → 65, 68, 126 — все в зоне). Горячих позиций две.
Прототип 19 (минимальное): наименьшая горячая позиция → S = 62.
Прототип 20 (два наименьших, Петя выигрывает 2-м ходом): Пете нужно сходить в 62 или 63. В 62:
s+2=62 → 60,s+5=62 → 57,2s=62 → 31. В 63:s+2=63 → 61,s+5=63 → 58. Собираем: 31, 57, 58, 60, 61. Два наименьших → 31 и 57.Прототип 21 (наименьшее, Ваня выигрывает 2-м ходом): полный список — 55, 56, 59; наименьшее → S = 55.
Решение на Python
def F(s, p):
if s >= 128: # порог из этого условия
return p % 2 == 0
if p == 0:
return False
hod = [F(s + 2, p - 1), # ходы: +2, +5, ×2
F(s + 5, p - 1),
F(s * 2, p - 1)]
return any(hod) if p % 2 == 1 else all(hod)
print("19:", [s for s in range(2, 127) if F(s, 2)]) # [62, 63]
print("20:", [s for s in range(2, 127) if F(s, 3) and not F(s, 1)]) # [31, 57, 58, 60, 61]
print("21:", [s for s in range(2, 127) if F(s, 4) and not F(s, 2)]) # [55, 56, 59]Ответ 19: 62 |
Ответ 20: 31 57 |
Ответ 21: 55 |
Задача 3. Одна куча, «убывающая» игра: −3, −5, //4 (финиш ≤ 30)
Условие Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из кучи 3 камня; убрать из кучи 5 камней; уменьшить количество камней в куче в 4 раза (при делении округляем до меньшего). Игра завершается, когда камней становится не более 30. Победителем считается игрок, сделавший последний ход. В начальный момент было S камней, S ≥ 31. |
⚠️ Осторожно: игра «убывающая» Здесь камни убывают, а финиш — стать не более 30. Логика та же, но в коде порог проверяем через |
Ручной разбор
Зона финиша: из каких s > 30 можно за ход дойти до ≤ 30. Самый «мощный» здесь ход — деление на 4: s // 4 ≤ 30 уже при s ≤ 123 (ведь 123 // 4 = 30). Значит финишировать одним ходом можно из огромного диапазона [31; 123].
Горячие позиции: сам не финиширует (s ≥ 124, ведь 124 // 4 = 31 > 30), но любой ход попадает в [31; 123]. Проверяем s − 3 ≤ 123 → s ≤ 126. Получаем s = 124, 125, 126 (например, 124 → 121, 119, 31 — все в зоне финиша).
Прототип 19 (минимальное): S = 124.
Прототип 20 (два наименьших, Петя — 2-м ходом): Пете нужно сходить в 124…126. Полный список подходящих S — 127, 128, 129, 130, 131. Два наименьших → 127 и 128 (например, 127 → 124).
Прототип 21 (наименьшее, Ваня — 2-м ходом): список 132, 133, 134; наименьшее → S = 132.
Решение на Python
def F(s, p):
if s <= 30: # финиш: стало не более 30
return p % 2 == 0
if p == 0:
return False
hod = [F(s - 3, p - 1), # ходы: −3, −5, //4 (целочисленное деление!)
F(s - 5, p - 1),
F(s // 4, p - 1)]
return any(hod) if p % 2 == 1 else all(hod)
print("19:", [s for s in range(31, 200) if F(s, 2)]) # [124, 125, 126]
print("20:", [s for s in range(31, 200) if F(s, 3) and not F(s, 1)]) # [127, 128, 129, 130, 131]
print("21:", [s for s in range(31, 200) if F(s, 4) and not F(s, 2)]) # [132, 133, 134]Ответ 19: 124 |
Ответ 20: 127 128 |
Ответ 21: 132 |
Задача 4. Две кучи: +1 или ×2 в любую кучу (финиш ≥ 81)
Условие Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в 2 раза. Игра завершается, когда суммарное количество камней в кучах становится не менее 81. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было семь камней, во второй — S камней, 1 ≤ S ≤ 73. |
⚠️ Прототип 19 здесь особенный — «неудачный ход» Формулировка: «Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна». Это НЕ «при любом ходе Пети». Тут достаточно, чтобы существовал один неудачный ход Пети, после которого Ваня добивает. Поэтому у проигрывающего (Пети) меняем |
Ручной разбор прототипа 19
Петя удваивает вторую кучу: (7, S) → (7, 2S). Ваня в ответ удваивает её же: (7, 2S) → (7, 4S). Сумма после хода Вани: 7 + 4S. Ваня финиширует, если 7 + 4S ≥ 81, то есть 4S ≥ 74, то есть S ≥ 18,5, то есть S ≥ 19.
Проверим, что ход Пети действительно «неудачный», а не выигрышный: после него сумма 7 + 2·19 = 45 < 81 — Петя не финишировал, всё честно. Значит минимальное S, при котором возможна такая ситуация, — S = 19.
Решение на Python
def hodi(a, b): # все ходы из позиции (a, b)
return [(a + 1, b), (a * 2, b), # +1 или ×2 в первую кучу
(a, b + 1), (a, b * 2)] # +1 или ×2 во вторую кучу
def F(a, b, p):
if a + b >= 81: # финиш: сумма не менее 81
return p % 2 == 0
if p == 0:
return False
hod = [F(x, y, p - 1) for x, y in hodi(a, b)]
return any(hod) if p % 2 == 1 else all(hod)
# Прототип 19 — «неудачный ход»: у Пети берём any (есть неудачный ход),
# и при этом сам Петя за один ход выиграть не может.
otv19 = [S for S in range(1, 74)
if any(F(x, y, 1) for x, y in hodi(7, S)) # есть ход Пети, после которого Ваня добьёт
and not F(7, S, 1)] # но сам Петя первым ходом не финиширует
print("19:", min(otv19)) # 19
# Прототипы 20 и 21 — стандартные (Петя играет оптимально → all)
print("20:", [S for S in range(1, 74) if F(7, S, 3) and not F(7, S, 1)]) # [33, 36]
print("21:", [S for S in range(1, 74) if F(7, S, 4) and not F(7, S, 2)]) # [32, 35]Прототип 19 (неудачный ход) → минимальное 19. Прототип 20 — два наименьших → 33 и 36. Прототип 21 — наименьшее из [32, 35] → 32.
📌 Почему для двух куч Python тем более удобен Считать дерево игры на две кучи вручную тяжело: позиций много, зона финиша зависит уже от обеих куч. Прототип 19 красиво решается «в лоб» (см. выше), а вот 20 и 21 честнее и быстрее посчитать кодом. Это ровно тот случай, когда универсальный шаблон экономит и время, и нервы. |
Ответ 19: 19 |
Ответ 20: 33 36 |
Ответ 21: 32 |