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

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

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

¬Д ЕЛ (x,A) → (¬Д ЕЛ (x,21)∧ ¬Д Е Л(x,35))

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

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

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

( . |||| x ||.. A { ⌊ .. || |x . 21 = 7 ⋅3 ||( ⌈ .. x . 35 = 7 ⋅5

Отсюда следует, что $x$ обязательно должен делиться на $7$ .

Нам требуется взять наибольшее $A$ , чтобы система была всегда ложна, то есть при любом $x$ множество решений системы пусто. Для этого достаточно взять $A = 7$ . Заметим, что если в качестве $A$ взять, например, $14$ , то система будет истина, если взять $x = 21$ .

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

def f(x, A):
    return (x % A != 0) <= ((x % 21 != 0) and (x % 35 != 0))

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

Ответ: 7