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

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

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

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

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

Составим систему для тех случаев, когда выражение тождественно ложно:

(| |.. |||{x |. A x ... 6 = 2 ⋅3 ||| |(x ... 9 = 3 ⋅3

Отсюда следует, что $x$ обязательно должен делиться на НОК $(6,9) = 18$ .

Нам требуется, чтобы любой $x$ , кратный $18$ , делится на $A$ , то есть $A$ — делитель числа $18$ . Максимальное $A$ равно максимальному делителю числа $18$ , то есть $18$ .

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

def f(x, A):
    return (x % A == 0) or (x % 6 != 0) or (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