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

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

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

¬Д ЕЛ (x,А) → (ДЕ Л (x,6) → ¬Д Е Л(x,9))

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

Решение 1 (ручками)

Рассмотрим формулу:

¬Д ЕЛ (x,A ) → (Д ЕЛ(x,6) → ¬ДЕ Л(x,9))

Нам нужно найти наибольшее $A$ , при котором формула всегда истинна для любого $x$ .

Формула утверждает, что если $x$ не делится на $A$ , то если $x$ делится на 6, то $x$ не должно делиться на 9. Чтобы формула была истинной, необходимо, чтобы $A$ было таким, что при делении на 6 $x$ не делится на 9. Это возможно, если $A$ — наименьшее общее кратное чисел 6 и 9:

НО К(6,9) = 18

Таким образом, наибольшее $A = 18$ .

Ответ: $A = 18$ .

Решение 2 (прогой)

def f(x, A):
    return (x % A != 0) <= ((x % 6 == 0) <= (x % 9 != 0))


for A in range(10000, 0, -1):
    flag = True
    for x in range(1000):
        if not f(x, A):
            flag = False
    if flag:
        print(A)
        break

Ответ: 18