20 задание ЕГЭ информатика
Теория игр: выигрыш вторым ходом
1 балл ≈ 8 мин уровень П Выигрышная стратегия игры
Задание 20 – найти значения S, при которых у Пети есть выигрышная стратегия: Петя не может выиграть за один ход, но выигрывает своим вторым ходом при любой игре Вани. Ответ – обычно два значения в порядке возрастания. 1 балл.
Логика без программы
- Найди позиции, где выигрывает тот, кто ходит, за 1 ход (W1).
- Найди позиции L1: все ходы ведут в W1 (это ответ задания 19).
- W2: из позиции есть ход в L1, но нет хода сразу к победе. Это и есть ответ 20.
С программой (функция f из задания 19):
print([s for s in range(1, 29) if f(s) == 2])Разобранный пример (ходы +1 или ×2, финиш при s ≥ 29). W1: s ≥ 15 (×2 даёт ≥ 30). L1: s = 14 (ходы в 15 и 28 – оба W1). W2: s, из которых можно попасть в 14 и нельзя выиграть сразу: 13 (+1) и 7 (×2). Ответ: 7 13.
Как проверить себя: для каждого найденного s выпиши ход Пети в L1-позицию и убедись, что из неё любой ход Вани даёт Пете победу.
Ловушки: записать значения не в порядке возрастания; включить s, из которых Петя может выиграть первым ходом; перепутать «Петя выигрывает вторым ходом» и «Ваня выигрывает вторым ходом».
- W2 = «есть ход в L1» и «нет хода в победу». Проверь оба условия.
- Значения пиши через пробел в порядке возрастания.
- Если значений больше двух, а спрашивают два наименьших – бери первые два.
Разобранные задания 20 из открытого банка ФИПИ
Пример 1 · код ФИПИ F7BE0F
| Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: – Петя не может выиграть за один ход; – Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. |
Показать ответ и решение
Ответ: 24 26
Игра: две кучи (5, S), +1 или ×2, конец при сумме ≥ 59.
Петя не выигрывает за 1 ход, но может пойти в позицию, из которой любой ход Вани даёт Пете выигрыш одним ходом.
Перебор программой даёт значения 24 26.
Пример 2 · код ФИПИ 1D271B
| Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: – Петя не может выиграть за один ход; – Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. |
Показать ответ и решение
Ответ: 42 43
Игра: две кучи (14, S), +3 или ×3, конец при сумме ≥ 176.
Петя не выигрывает за 1 ход, но может пойти в позицию, из которой любой ход Вани даёт Пете выигрыш одним ходом.
Перебор программой даёт значения 42 43.
Пример 3 · код ФИПИ 7c7DD5
| Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: – Петя не может выиграть за один ход; – Петя может выиграть своим вторым ходом независимо от того, Найденные значения запишите в ответе в порядке возрастания. |
Показать ответ и решение
Ответ: 98 99
Игра: −2, −4, :4, конец при ≤ 23.
Петя не выигрывает за 1 ход, но может пойти в позицию, из которой любой ход Вани даёт Пете выигрыш одним ходом.
Перебор программой даёт значения 98 99.
Частые вопросы о задании 20
Сколько баллов даёт задание 20 ЕГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 8 мин. Уровень сложности – П.
Что проверяет задание 20?
Задание 20 – найти значения S, при которых у Пети есть выигрышная стратегия: Петя не может выиграть за один ход, но выигрывает своим вторым ходом при любой игре Вани. Ответ – обычно два значения в порядке возрастания. 1 балл.
Как подготовиться к заданию 20?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.