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

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

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

(¬Д ЕЛ (x,19)∨ ¬Д ЕЛ (x,15)) → ¬Д ЕЛ (x,A)

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

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

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

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

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

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

for a in range(1, 300):
    f = 0
    for x in range(1, 500):
        if (((x % 19 != 0) or (x % 15 != 0)) <= (x % a != 0)) == False:
            f = 1
            break
    if f == 0:
        print(a)

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

Ответ: 285