Question

Для какого наименьшего целого неотрицательного числа $A$ выражение

$$(x < A) \lor (y < A) \lor (y > x - 5) \lor (y < 2x - 15)$$

тождественно истинно при всех целых неотрицательных $x$ и $y$?

Accepted Answer

6

Answer

Идея решения: найти минимальное значение $A$, при котором логическое выражение принимает значение истина для всех пар $(x, y)$ в диапазоне $[0, 300) 	imes [0, 300)$.

Выражение тождественно истинно, если не существует пары $(x, y)$, для которой все четыре дизъюнкта одновременно ложны. Это означает, что система неравенств

$$x \geq A, \quad y \geq A, \quad y \leq x - 5, \quad y \geq 2x - 15$$

не должна иметь решений.

Переберём значения $A$ от 0 до 300. Для каждого кандидата подсчитаем количество пар $(x, y)$, удовлетворяющих исходному выражению. Когда это количество достигнет $300 	imes 300 = 90000$ (все пары), найдём минимальное такое $A$.

```python
for a in range(0, 300):
    k = 0
    for x in range(0, 300):
        for y in range(0, 300):
            if ((x < a) or (y < a) or 
                (y > x - 5) or (y < 2 * x - 15)):
                k += 1
    if k == 90000:
        print(a)
        break
```

Программа проверяет каждое значение $A$, начиная с нуля. Для каждого $A$ подсчитывает количество пар $(x, y)$ из диапазона $[0, 300)$, для которых выражение истинно. Когда счётчик достигает полного количества пар (90000), выводится текущее значение $A$ и цикл завершается.

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