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

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

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

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

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

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

1. Для того чтобы формула была тождественно истинна, необходимо, чтобы при $¬Д ЕЛ (x,A) = 1$ (то есть $x$ не делится на $A$ ), выполнялось условие $¬Д ЕЛ (x,21) ∧¬ ДЕ Л(x,35)$ (то есть $x$ не делится на 21 и 35).

2. Таким образом, любое число $x$ , которое не делится на $A$ , не должно делиться на 21 и 35 одновременно. Это означает, что все числа $x$ , которые делятся на 21 или на 35, должны делиться на $A$ . То есть, $A$ должно быть делителем чисел, кратных 21 или 35.

3. Найдем наименьшее общее кратное (НОК) чисел 21 и 35:

НО К(21,35) = НО К(3 ⋅7,5 ⋅7) = 3⋅5 ⋅7 = 105.

Это означает, что все числа, которые делятся на 21 или на 35, также делятся на 105.

4. Следовательно, максимальное значение $A$ , которое делит все числа, кратные 21 или 35, является наибольшим делителем 105. Наибольший такой делитель — это $7$ , так как $7$ является наибольшим общим делителем чисел 21 и 35.

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

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

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

Ответ: 7