Задача к ЕГЭ по информатике на тему «Деление без остатка» №2

Просмотров 6 Комментарии 0

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

ДЕ Л (x, A ) → (Д ЕЛ (x, 14) ∧Д Е Л(x, 21))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Решение руками:

Введем обозначения: $A = Д ЕЛ (x, A ),P = ДЕ Л(x, 14),Q = ДЕ Л (x, 21))$

Таким образом истиным для всех $x$ должно быть выражение $A → (P ∧Q )$ .Упростим это выражение, раскрыв импликацию: $-- A ∨ P ∧ Q$ .

Из этой формулы видно, что множество $A$ должно перекрыть множество, которое не перекрыто множеством $P ∧ Q$ . Множество $P ∧ Q$ – это множество всех чисел, которые не делятся одновлеменно на 14 и 21. Поэтому чтобы найти наименьшее $A$ необходимо найти наименьшее общее кратное чисел 14 и 21 – это 42.

Решение программой:

for a in range(1, 1500):
    # Переменная-флаг,
    # которой присваивается 1, если хотя бы одно выражение выдаёт ложь
    f = 0
    for x in range(1, 5000):
        # Если выражение ложно(нам нужны только истинные),
        # то приостанавливаем цикл
        if ((x % a == 0) <= ((x % 14 == 0) and (x % 21 == 0))) == False:
            f = 1
            break
    # Так как ищем минимальное значение,
    # то сразу же после его нахождения прерываем цикл
    if f == 0:
        print(a)
        break

Получаем ответ: $42.$

Ответ: 42