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

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

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

Д ЕЛ (x,24) → (ДЕ Л (x,72) → Д ЕЛ (x,A ))

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

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

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

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

Из этой формулы видно, что множество $A$ должно перекрыть множество, которое не перекрыто множеством $P-∨ Q-$ . Предположим, что $P-∨Q-= 0$ , отсюда $P ∧Q = 1$ , значит, множество $P-∨Q-$ ложно, когда число делится и на 24, и на 77. Найдем НОК чисел 24 и 72, оно равно 72. Значит число 72 должно делиться на А без остатка, тогда наибольшее возможное А это 72.

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

for a in range(1, 200):
    f = 0
    for x in range(1, 500):
        if ((x % 24 == 0) <= ((x % 72 == 0) <= (x % a == 0))) == False:
            f = 1
            break
    if f == 0:
        print(a)

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

Ответ: 72