Задание 15 ЕГЭ по информатике на Python: отрезки и ДЕЛ

В задании 15 ЕГЭ по информатике дана логическая формула с параметром A — отрезком на числовой прямой, делителем или числом в неравенстве. Нужно найти A, при котором формула тождественно истинна, то есть верна при любом x. Рассуждать можно руками, но на Python решение одно для всех видов: формулу записывают функцией, «при любом x» проверяют через all(), а A перебирают. Примеры ниже запускаются прямо на странице и составлены для этой статьи: на экзамене отрезки и числа будут другими, а шаблон — тот же.

ЕГЭ / 01koddo

Отрезки проверяют и между целыми точками

Пример задачи: отрезки

На числовой прямой даны отрезки P = [10, 20] и Q = [21, 30]. Укажи наибольшую возможную длину отрезка A, при котором формула

(x ∈ A) → ((x ∈ P) ∨ (x ∈ Q))

тождественно истинна, то есть принимает значение 1 при любом x.

Решение

def inside(x, a, b):
    return a <= x <= b

def f(x, a1, a2):
    return not inside(x, a1, a2) or inside(x, 10, 20) or inside(x, 21, 30)

best = 0
for a1 in range(0, 41):
    for a2 in range(a1, 41):
        if all(f(x2 / 2, a1, a2) for x2 in range(0, 81)):
            best = max(best, a2 - a1)
print(best)

10

• inside(x, a, b) — «x лежит на отрезке [a, b]». Концы входят в отрезок, поэтому сравнения нестрогие.
• Импликация «X → Y» в Python записывается как not X or Y: она ложна, только когда X истинно, а Y ложно.
• all(...) — «при любом x»: True, только если формула верна во всех проверенных точках.
• x2 / 2 при x2 от 0 до 80 даёт x = 0; 0,5; 1; …; 40 — целые точки и середины между ними.
• Концы A перебираются целыми от 0 до 40 — с запасом вокруг P и Q, а best хранит наибольшую длину подходящего A.

Ответ: 10.

Проверка рассуждением. Формула требует, чтобы каждая точка A лежала в P или в Q. Между 20 и 21 есть точки, которые не входят ни в один отрезок, поэтому A целиком лежит внутри P или внутри Q. Длина P — 10, длина Q — 9, значит, наибольшая длина A — 10.

Почему шаг 0,5

Если проверять только целые x, программа ответит иначе:

def inside(x, a, b):
    return a <= x <= b

def f(x, a1, a2):
    return not inside(x, a1, a2) or inside(x, 10, 20) or inside(x, 21, 30)

best = 0
for a1 in range(0, 41):
    for a2 in range(a1, 41):
        if all(f(x, a1, a2) for x in range(0, 41)):
            best = max(best, a2 - a1)
print(best)

20

Среди целых x нет ни одного между 20 и 21, поэтому A = [10, 30] проходит проверку, хотя точка 20,5 его опровергает. Значение формулы может меняться только в концах отрезков, а они целые, — значит, достаточно проверить целые x и по одной точке между соседними целыми.

ДЕЛ: делимость

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на m». Для какого наибольшего натурального A формула

(ДЕЛ(x, 28) ∧ ДЕЛ(x, 42)) → ДЕЛ(x, A)

тождественно истинна при любом натуральном x?

def f(x, a):
    return not (x % 28 == 0 and x % 42 == 0) or x % a == 0

good = [a for a in range(1, 1000) if all(f(x, a) for x in range(1, 1000))]
print(good[-1])
print(good)

84
[1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84]

ДЕЛ(x, m) — это x % m == 0. Подходят все делители 84, наибольший — 84. Проверка рассуждением: x делится и на 28, и на 42 тогда и только тогда, когда делится на их наименьшее общее кратное 84, а такие x делятся на A, только если A — делитель 84.

Частые ошибки

Только целые x в отрезках. Как показано выше, для этих отрезков ответ выйдет 20 вместо 10. Для отрезков с целыми концами нужен шаг 0,5.

Импликация не в ту сторону. «X → Y» — это not X or Y, а не X or not Y. Перепутанное направление проверяет другую формулу, и ответ будет другим.

Мало x в переборе. В примере с ДЕЛ x доходит до 999: это включает 84 и его кратные. Если перебирать x только до 50, ни одно x не будет делиться на 28 и 42 сразу, формула станет верной при любом A, и ответом выйдет 999 — просто последнее A из перебора.

Какие ещё задания решают программой — в статье «Python для ЕГЭ по информатике», таблица истинности и логические операции из задания 2 — в статье «Задание 2 ЕГЭ на Python». Свой вариант удобно проверять в песочнице Python: там можно вывести точки, в которых формула ложна, и увидеть, какой кусок прямой мешает.