Задание №15. Короткий конспект
Условия ложности, выбор параметра по запрещённым случаям и проверка минимума или максимума.
Подходящий параметр делает формулу истинной для всех разрешённых значений переменных. Основной порядок: область значений → условие ложности → ограничение на параметр → доказательство границы. Один контрпример исключает проверяемый параметр.
Когда выражение ложно
P,Q — логические утверждения.
| Операция | Условие ложности |
|---|---|
| \neg P | P истинно |
| P\land Q | Хотя бы одна часть ложна |
| P\lor Q | Обе части ложны |
| P\to Q | P истинно, Q ложно |
| P\equiv Q | Значения частей различаются |
Как выбрать параметр
- Неравенства. Выделяется область, где части без параметра ложны. Оставшееся условие должно выполняться в каждой её точке. Для строгой целой границы t<A, если максимум t равен M, минимальное A=M+1.
- Отрезки. По формуле определяется обязательное множество точек. Если оно должно содержаться в одном отрезке, включается и промежуток между его раздельными частями. Длина [l;r] равна r-l.
- Делимость. \text{ДЕЛ}(n,m) при положительном m означает
n % m == 0. Общие кратные строятся через НОК. Наибольший делитель всех чисел конечного непустого набора положительных чисел — их НОД. Сначала устанавливается, какие числа обязаны на что делиться. - Побитовые операции. Числа записываются в двоичной системе. Для каждой обязательной или запрещённой единицы определяется разряд. Необходимость удобно проверять числом с единственной единицей в этом разряде.
Возможные ловушки
- В EGE-15-0003 ↗ пара (9,9) требует 81<A, поэтому ответ 82. Подмена строгого знака равенством уменьшает ответ на единицу.
- В EGE-15-0010 ↗ переменная положительна. Подстановка нуля создаёт запрещённый условием случай и завышает требуемую границу.
- В EGE-15-0001 ↗ сумма длин двух обязательных частей не равна длине покрывающего их отрезка: нужен также промежуток между ними.
- Перебор до произвольного числа не охватывает бесконечную область. Конечные границы должны следовать из формулы, свойств кратных или разрядов.
Проверка результата состоит из двух частей: найденный параметр подходит везде; любое значение за требуемой границей не подходит. Проверка только соседа достаточна, если объяснено, почему дальнейшее изменение параметра не может исправить найденный контрпример.