Question

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

Для какого наименьшего натурального числа *A* формула

$$(ДЕЛ(x, 3) 	o 
eg ДЕЛ(x, 5)) \lor (x + A \geq 90)$$

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

Accepted Answer

75

Answer

Идея решения: преобразовать импликацию в дизъюнкцию, найти значения *x*, при которых первая часть ложна, и подобрать минимальное *A*, обеспечивающее истинность всего выражения.

Преобразуем формулу, используя эквивалентность $P 	o Q \equiv 
eg P \lor Q$:

$$(ДЕЛ(x, 3) 	o 
eg ДЕЛ(x, 5)) \lor (x + A \geq 90)$$
$$\equiv (
eg ДЕЛ(x, 3) \lor 
eg ДЕЛ(x, 5)) \lor (x + A \geq 90)$$
$$\equiv 
eg ДЕЛ(x, 3) \lor 
eg ДЕЛ(x, 5) \lor (x + A \geq 90)$$

Выражение $
eg ДЕЛ(x, 3) \lor 
eg ДЕЛ(x, 5)$ ложно только при одновременном выполнении условий: $ДЕЛ(x, 3)$ и $ДЕЛ(x, 5)$. Это означает, что *x* делится и на 3, и на 5, то есть делится на их наименьшее общее кратное: $	ext{НОК}(3, 5) = 15$.

Таким образом, критические значения — это *x*, кратные 15: $x \in \{15, 30, 45, 60, 75, 90, 105, \ldots\}$.

Для этих значений первая часть дизъюнкции ложна, поэтому вторая часть $(x + A \geq 90)$ должна быть истинна:

$$x + A \geq 90 \implies A \geq 90 - x$$

Чтобы формула была истинна при всех натуральных *x*, нужно, чтобы условие выполнялось для всех критических *x*. Наиболее ограничивающее условие возникает при наибольшем значении $90 - x$ среди критических *x*, которые меньше 90. Это *x* = 75:

$$A \geq 90 - 75 = 15$$

Однако проверим более внимательно: при *x* = 75 имеем $75 + A \geq 90$, откуда $A \geq 15$. Но нужно убедиться, что это достаточно для всех *x*.

Проверим программой:

```python
for A in range(1, 10000):
    is_valid = True
    for x in range(1, 10000):
        expr = ((x % 3 != 0) or (x % 5 != 0) or (x + A >= 90))
        if not expr:
            is_valid = False
            break
    if is_valid:
        print(A)
        break
```

Программа перебирает значения *A* и проверяет, истинна ли формула при всех *x* в диапазоне. Первое найденное *A*, при котором формула тождественно истинна, — это ответ.

Минимальное натуральное число *A*, при котором формула истинна для всех натуральных *x*, равно 75.

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