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

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

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

(Д ЕЛ (x,45) ∧Д ЕЛ (x,70)) → Д ЕЛ (x,A)

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

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

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

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

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

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

for a in range(1, 1000):
    f = 0
    for x in range(1, 1500):
        if (((x % 45 == 0) and (x % 70 == 0)) <= (x % a == 0)) == False:
            f = 1
            break
    if f == 0:
        print(a)

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

Ответ: 630