Задание №15. Поиск параметра в логическом условии

Требуется выбрать число или отрезок так, чтобы логическое выражение было истинным при всех разрешённых значениях переменных. Основной приём — определить, когда выражение могло бы стать ложным. Затем параметр выбирается так, чтобы исключить каждый такой случай. Одного подходящего набора переменных недостаточно, зато одного неподходящего достаточно для опровержения.

От истинности к запрещённому случаю

Утверждения обозначим P и Q. У каждого два значения: истина или ложь. Для поиска запрещённых случаев достаточно следующих правил.

Отрицание \neg P меняет значение утверждения на противоположное. Контрпример всегда ищется внутри области, указанной в задаче: положительные числа не включают нуль, неотрицательные включают, а точки отрезков могут быть вещественными.

Неравенства: минимальный параметр

В EGE-15-0003 ↗ требуется наименьшее целое неотрицательное A, при котором для всех целых неотрицательных x,y истинно:

(xy<A)\lor(x<y)\lor(9<x).

1. Где два последних условия не помогают

Чтобы всё выражение оказалось ложным, должны одновременно оказаться ложными все три части. Отрицание x<y даёт x\ge y, а отрицание 9<x — x\le9. С учётом неотрицательности остаётся область:

0\le y\le x\le9.

За её пределами уже истинно хотя бы одно из двух последних условий. Внутри неё истинность должно обеспечить первое условие xy<A.

2. Наибольшее произведение в этой области

Оба множителя не больше девяти, поэтому xy\le81. Граница достигается: пара x=y=9 разрешена. Значит, требуется 81<A, и наименьшее целое значение равно 82.

3. Почему подходит и почему меньше нельзя

При A=82 внутри найденной области всегда выполнено xy\le81<82; вне неё работают другие части. При A=81 пара (9,9) даёт три ложных неравенства: 81<81, 9<9 и 9<9. Та же пара опровергает любое меньшее значение параметра.

Теперь программная проверка имеет доказанные границы: достаточно всех целых точек 0\le y\le x\le9.

def works(a):
    return all(
        x * y < a
        for x in range(10)
        for y in range(x + 1)
    )

# False True
print(works(81), works(82))

Здесь проверяется только первая часть, потому что две остальные ложны во всей перебираемой области. Это сокращение следует из формулы, а не из предположения, что небольших чисел обычно достаточно.

Если требуется максимум

В EGE-15-0002 ↗ требуется наибольшее целое неотрицательное A, при котором формула (2x+y\ne40)\lor(x<y)\lor(A<x) истинна для всех целых неотрицательных x,y. Последнее условие обязано выполняться там, где 2x+y=40 и x\ge y.

Подстановка y=40-2x во второе ограничение даёт 3x\ge40. Наименьшее целое x равно 14, и ему соответствует допустимое y=12. Поэтому нужно A<14. Максимум — 13; параметр 14 и все большие значения опровергаются парой (14,12).

Отрезки: какие точки должен содержать ответ

В EGE-15-0007 ↗ заданы P=[25;64] и Q=[40;115]. Требуется минимальная длина отрезка A, обеспечивающего истинность:

(x\in P)\to\bigl(((x\in Q)\land\neg(x\in A))\to\neg(x\in P)\bigr).

Запись x\in P — утверждение о принадлежности одной точки отрезку. Внешняя импликация ложна только тогда, когда x\in P, а внутренняя импликация ложна. Для ложности внутренней нужны одновременно x\in Q, x\notin A и ложность x\notin P. Последнее уже следует из принадлежности P.

Итак, запрещённый случай — точка общей части P и Q, оставленная вне A. Общая часть равна [40;64]. Наименьший подходящий отрезок совпадает с ней, а его длина равна 64-40=24.

Формула может требовать и другую часть прямой. В EGE-15-0034 ↗ внешнее условие — x\notin B, а ложность внутреннего требует x\in C и x\notin A. Поэтому в A должна войти разность C\setminus B=(40;63]. Наименьший замкнутый отрезок — [40;63], длина 23: сдвиг левого конца вправо потеряет часть обязательных точек.

В EGE-15-0001 ↗ формула \neg(x\in A)\to((x\in B)\equiv(x\in C)) требует включить в A точки с разной принадлежностью отрезкам B=[22;40] и C=[32;50]. Это [22;32)\cup(40;50]. Поскольку ответ должен быть одним отрезком, он включает и промежуток между этими частями. Минимальная длина равна 50-22=28.

Делимость: условие для всех кратных

Обозначение \text{ДЕЛ}(n,m) означает, что n делится на положительное m без остатка. В EGE-15-0032 ↗ требуется максимальное натуральное A для формулы:

\neg\text{ДЕЛ}(x,A)\to\bigl(\text{ДЕЛ}(x,12)\to\neg\text{ДЕЛ}(x,14)\bigr).

Ложность означает: число делится на 12 и на 14, но не делится на A. Их наименьшее общее кратное равно 84. Поэтому общие неотрицательные кратные имеют вид 84k, где k — целое неотрицательное число. Все они должны делиться на A.

Подстановка x=84 показывает необходимость: A должно делить 84. Это и достаточно: тогда любое 84k делится на A. Максимум — 84. Нуль не мешает: он делится на любой положительный делитель.

Другие формулы меняют набор обязательных чисел. В EGE-15-0009 ↗ делиться на A должны кратные 22 внутри [60;80]. Единственное такое число — 66, поэтому максимум равен 66. При нескольких обязательных числах наибольшим общим делителем был бы их НОД.

В EGE-15-0010 ↗ условие x+A\ge80 должно выполняться на всех положительных кратных 15. Самое малое из них — 15, поэтому достаточно и необходимо 15+A\ge80: минимум 65.

В EGE-15-0079 ↗ запрещены кратные A, не делящиеся ни на 26, ни на 39. При x=A необходимо, чтобы само A делилось хотя бы на одно из этих чисел. Этого достаточно и для всех его кратных. Минимум равен 26; НОК здесь не требуется.

Побитовая операция: обязательный разряд

Побитовая конъюнкция обозначается \mathbin{\&}. В EGE-15-0008 ↗ условие имеет вид:

\bigl((x\mathbin{\&}52\ne0)\land(x\mathbin{\&}48=0)\bigr)\to\neg(x\mathbin{\&}A=0).

Записи 52=110100_2 и 48=110000_2 отличаются только разрядом с весом 4. Если у числа нет общих единиц с 48, но есть с 52, эта единица обязательно стоит в разряде веса 4. Выбор A=4 обеспечивает требуемое ненулевое пересечение для каждого такого числа.

Меньшее значение не подходит: у него нет нужного разряда, и x=4 становится контрпримером. Старшие разряды x не влияют на пересечение с двумя заданными числами, поэтому рассуждение охватывает все неотрицательные целые. Ответ: 4.

При поиске максимума нужно обосновать, какие разряды добавлять нельзя. В EGE-15-0086 ↗ дана формула (x\mathbin{\&}A\ne0)\to((x\mathbin{\&}12=0)\to(x\mathbin{\&}5\ne0)). Она ложна, когда у x есть общая единица с A, но нет общих единиц ни с 12=1100_2, ни с 5=0101_2. Следовательно, A может содержать только разряды, присутствующие хотя бы в одной из этих двух масок: их объединение равно 1101_2=13. Все эти разряды допустимы, а любой добавленный разряд вне них даёт контрпример — число с одной единицей в добавленном разряде. Максимум равен 13.

Возможные ловушки

• Произвольная граница перебора. Проверка первых тысячи чисел не доказывает утверждение для всех. В EGE-15-0003 ↗ конечная область выведена из неравенств; в задачах о делимости доказательство охватывает все кратные.
• Потеря строгого знака. В EGE-15-0003 ↗ максимальное произведение 81, но требуется A=82. Равенство не выполняет строгое неравенство; подстановка граничной пары обнаруживает ошибку.
• Точки вместо длины. В EGE-15-0007 ↗ длина [40;64] равна 24. Прибавление единицы считает целые точки, хотя переменная вещественная.
• Подмена операции. В EGE-15-0008 ↗ Python & сравнивает разряды чисел, а and связывает логические условия. Их замена меняет смысл формулы. Для импликации между условиями p и q используется (not p) or q.