Question

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

$$
eg 	ext{ДЕЛ}(x, A) 	o (	ext{ДЕЛ}(x, 6) 	o 
eg 	ext{ДЕЛ}(x, 4))$$

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

Accepted Answer

12

Answer

Идея решения: свести логическое выражение к условию на множества, найти пересечение делимостей и определить наибольший делитель этого пересечения.

Обозначим:
- $A = \{x : x \equiv 0 \pmod{A}\}$ — множество чисел, делящихся на $A$;
- $P = \{x : x \equiv 0 \pmod{6}\}$ — множество чисел, делящихся на 6;
- $Q = \{x : x \equiv 0 \pmod{4}\}$ — множество чисел, делящихся на 4.

Исходная формула имеет вид $
eg A 	o (P 	o 
eg Q)$.

Раскроем импликации, используя эквивалентность $X 	o Y \equiv 
eg X \lor Y$:

$$
eg A 	o (P 	o 
eg Q) \equiv A \lor (
eg P \lor 
eg Q) \equiv A \lor 
eg(P \cap Q)$$

Для истинности при всех $x$ требуется:

$$A \cup 
eg(P \cap Q) = \mathbb{N}$$

Это равносильно:

$$P \cap Q \subseteq A$$

Множество $P \cap Q$ состоит из чисел, делящихся одновременно на 6 и на 4. Поскольку $	ext{lcm}(6, 4) = 12$, имеем:

$$P \cap Q = \{x : x \equiv 0 \pmod{12}\} = \{12, 24, 36, \ldots\}$$

Чтобы $P \cap Q \subseteq A$, число $A$ должно делить все элементы множества $P \cap Q$. Это возможно тогда и только тогда, когда $A$ делит 12.

Делители числа 12: $\{1, 2, 3, 4, 6, 12\}$.

Наибольший делитель — 12.

```python
for a in range(100, 0, -1):
    valid = True
    for x in range(1, 1000):
        # Проверяем: (x % a != 0) <= ((x % 6 == 0) <= (x % 4 != 0))
        if not ((x % a != 0) <= ((x % 6 == 0) <= (x % 4 != 0))):
            valid = False
            break
    if valid:
        print(a)
        break
```

Альтернативный вариант:

```python
def f(x, a):
    return (x % a != 0) <= ((x % 6 == 0) <= (x % 4 != 0))

for a in range(1, 1000):
    if all(f(x, a) == 1 for x in range(1, 1000)):
        print(a)
```

Оба варианта выдают ответ 12.

![Рисунок](https://ege.sdamgia.ru/formula/svg/37/37ae87aab11601f49c1b6035271d117b.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/12/12a7cb0919bf5d9b63f01d42ad81ebf2.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/32/3259c3032187705cc75259ab34f88211.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/09/09777e5f2128782805ab6ee504679fd9.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/9d/9ddedac295b63e35f3d42d4c9f067325.svg)

Задание №15Математическая логикаЕГЭ по информатике