Задание 15
тема 3 из 7

Тождественная истинность

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

Главная тема в задании15На карте навыков

Параметр в неравенстве

Выражение тождественно истинно, если оно равно 1 при любых значениях переменных. Тождественно ложно — если его отрицание тождественно истинно.

  • Приведите выражение к дизъюнкции: P→Q=¬P∨QP \to Q = \neg P \lor Q, ¬(P∧Q)=¬P∨¬Q\neg (P \land Q) = \neg P \lor \neg Q.
  • Найдите область MM: значения переменных, при которых ложны все условия без AA.
  • Найдите на MM худшую точку — ту, где условие с AA выполнить труднее всего. Из неё получите границу для AA.
  • Для целых чисел строгое неравенство сдвигает границу на 1: из 57<A57 < A следует A≥58A \geq 58.
  • x&m=0x \mathbin{\&} m = 0 — у xx нет единиц в тех разрядах, где они есть у mm.
  • Программа перебирает AA и проверяет выражение при всех xx и yy из диапазона, который накрывает MM.

Худшее значение переменной

Пусть выражение — дизъюнкция условия с AA и условий без AA. Условие с AA должно быть истинно при всех значениях из области MM, где ложны остальные условия. Достаточно проверить худшее значение — точку MM, где условие с AA выполнить труднее всего. Если условие выполнено там, оно выполнено во всей области.

Для условия f(x)<Af(x) < A худшая точка — та, где f(x)f(x) наибольшее, и тогда AA больше этого наибольшего значения. Для условия f(x)≥Af(x) \geq A худшая точка — та, где f(x)f(x) наименьшее. Следите за тем, какие значения переменных разрешены: «целые неотрицательные» начинаются с 0, «целые положительные» и «натуральные» — с 1.

Пример

Для какого наименьшего целого AA выражение (x≥20)∨(3x<A)(x \geq 20) \lor (3x < A) тождественно истинно при любом целом неотрицательном xx?

  1. 1.Условие x≥20x \geq 20 ложно при x=0,1,…,19x = 0, 1, \ldots, 19. Это область MM.
  2. 2.3x3x наибольшее при x=19x = 19: 3⋅19=573 \cdot 19 = 57. Нужно 57<A57 < A.
  3. 3.Наименьшее целое AA, которое больше 57, — это 58.

Ответ: 5858

Две переменные и произведение x · y

Выражение (x<A)∧(y<A)∧(x⋅y>N)(x < A) \land (y < A) \land (x \cdot y > N) тождественно ложно, если его отрицание (x≥A)∨(y≥A)∨(x⋅y≤N)(x \geq A) \lor (y \geq A) \lor (x \cdot y \leq N) тождественно истинно. Область MM — пары, где x<Ax < A и y<Ay < A, то есть x,y≤A−1x, y \leq A - 1.

Произведение наибольшее при x=y=A−1x = y = A - 1. Значит, нужно (A−1)2≤N(A - 1)^2 \leq N. Найдите наибольшее целое число, квадрат которого не больше NN, и прибавьте 1.

Пример задания

Открытый банк ФИПИ

Для какого наибольшего целого неотрицательного числа А выражение
(x<A)∧(y<A)∧(x⋅y>1200)\left(x < A\right) \land \left(y < A\right) \land \left(x \cdot y > 1200\right)
тождественио ложно, т. е. принимает значение 0 при любых целых положительных x и y?

Линейное выражение на области

Если условий без AA несколько, область MM — фигура на плоскости (x,y)(x, y): прямоугольник, треугольник или четверть круга. Линейное выражение ax+byax + by с положительными aa и bb растёт вправо и вверх, поэтому его наибольшее значение — в дальнем углу области. Для условия вида y≥3x+Ay \geq 3x + A нужна граница A≤y−3xA \leq y - 3x: ищите наименьшее значение y−3xy - 3x, то есть самое маленькое yy и самое большое xx.

Если граница области — окружность x2+y2≤R2x^2 + y^2 \leq R^2, переберите целые точки около окружности и выберите лучшую. Например, при x2+y2≤128x^2 + y^2 \leq 128 сумма x+yx + y наибольшая в точке (8;8)(8; 8): 64+64=12864 + 64 = 128.

Пример

Для какого наименьшего целого AA выражение (x+3y<A)∨(y>x)∨(x>40)(x + 3y < A) \lor (y > x) \lor (x > 40) тождественно истинно при любых целых неотрицательных xx и yy?

  1. 1.Условия без AA ложны, если y≤xy \leq x и x≤40x \leq 40. Область MM — треугольник с вершинами (0;0)(0; 0), (40;0)(40; 0), (40;40)(40; 40).
  2. 2.x+3yx + 3y наибольшее в углу (40;40)(40; 40): 40+120=16040 + 120 = 160.
  3. 3.Нужно 160<A160 < A, наименьшее целое A=161A = 161.

Ответ: 161161

Программа: перебор A и пар (x, y)

Если AA входит в два условия или область сложная, проще перебрать. Внешний цикл идёт по AA, а all(...) с двумя for проверяет выражение для всех пар xx и yy. Знаки <, >= и логические and, or, not пишут так же, как в условии.

Диапазон переменных должен накрывать область MM с запасом: вне неё условия без AA истинны, и проверка там ничего не меняет. Если сказано «целое AA», перебор начинают с отрицательных чисел: range(-100, 100). Если ответ совпал с границей перебора, расширьте её.

Пример

Для какого наименьшего целого AA выражение (x≥10)∨(y≥20)∨(y≤x+A)∨(y≥2x−A)(x \geq 10) \lor (y \geq 20) \lor (y \leq x + A) \lor (y \geq 2x - A) тождественно истинно при любых целых неотрицательных xx и yy?

  1. 1.Вручную: в области x≤9x \leq 9, y≤19y \leq 19 выражение ложно, если x+A<y<2x−Ax + A < y < 2x - A. Этот промежуток шире всего при x=9x = 9: 9+A<y<18−A9 + A < y < 18 - A.
  2. 2.При A=3A = 3 подходит y=13y = 13, выражение ложно. При A=4A = 4 промежуток 13<y<1413 < y < 14 не содержит целых чисел.
  3. 3.Программа перебирает AA от −100-100, печатает первое подходящее значение и останавливается: 4.

Ответ: 44

Предикат из условия: ТРЕУГ и МАКС

Иногда условие задаёт свой предикат. ТРЕУГ(n, m, k) — «существует невырожденный треугольник со сторонами nn, mm, kk». Он истинен, если каждая сторона меньше суммы двух других. Для сторон xx, aa, bb при a≤ba \leq b это b−a<x<a+bb - a < x < a + b. МАКС(a, b) — большее из двух чисел, МАКС(x,5)>10\text{МАКС}(x, 5) > 10 равно x>10x > 10.

Вручную разбейте ось xx на участки по границам всех предикатов и найдите на каждом значение частей без AA. В программе предикат — функция: treug сортирует стороны и сравнивает сумму двух меньших с большей, МАКС — встроенная max.

Пример

Для какого наибольшего натурального AA выражение ¬((ТРЕУГ(x,5,9)≡¬(МАКС(x,5)>10))∧ТРЕУГ(x,A,2))\neg ((\text{ТРЕУГ}(x, 5, 9) \equiv \neg (\text{МАКС}(x, 5) > 10)) \land \text{ТРЕУГ}(x, A, 2)) тождественно истинно при натуральных xx?

  1. 1.ТРЕУГ(x,5,9)\text{ТРЕУГ}(x, 5, 9) истинно при 4<x<144 < x < 14, то есть при x=5,…,13x = 5, \ldots, 13. Вторая часть эквивалентности истинна при x≤10x \leq 10.
  2. 2.Эквивалентность истинна при x=5,…,10x = 5, \ldots, 10 и при x≥14x \geq 14. При этих xx должно быть ложно ТРЕУГ(x,A,2)\text{ТРЕУГ}(x, A, 2).
  3. 3.ТРЕУГ(x,A,2)\text{ТРЕУГ}(x, A, 2) истинно при A−2<x<A+2A - 2 < x < A + 2: это три числа A−1A - 1, AA, A+1A + 1. Они должны лежать среди 1, 2, 3, 4 или 11, 12, 13. Наибольшее A=12A = 12.
  4. 4.Программа печатает 12.

Ответ: 1212

Поразрядная конъюнкция: рассуждение по битам

x&mx \mathbin{\&} m — поразрядная конъюнкция: x&m=0x \mathbin{\&} m = 0, если у xx нули во всех разрядах, где у mm единица, и x&m≠0x \mathbin{\&} m \neq 0, если хотя бы в одном таком разряде у xx единица: конъюнкция с маской.

Запишите числа из условия в двоичной системе и найдите MM как набор требований к битам xx. Если в MM есть числа, у которых ровно одна единица, условие x&A≠0x \mathbin{\&} A \neq 0 требует, чтобы у AA была единица в этом разряде. Наименьшее AA — сумма всех обязательных степеней двойки.

Пример

Для какого наименьшего неотрицательного целого AA выражение (x&13=0)∨(x&6≠0)∨(x&A≠0)(x \mathbin{\&} 13 = 0) \lor (x \mathbin{\&} 6 \neq 0) \lor (x \mathbin{\&} A \neq 0) тождественно истинно при любом неотрицательном целом xx?

  1. 1.13=1101213 = 1101_2, 6=011026 = 0110_2. Первые две части ложны, если у xx нули в разрядах 1 и 2 и единица в разряде 0 или 3.
  2. 2.В MM есть x=1x = 1 и x=8x = 8. Значит, у AA единицы в разрядах 0 и 3: A≥1+8=9A \geq 1 + 8 = 9.
  3. 3.При A=9=10012A = 9 = 1001_2 каждое xx из MM имеет общую единицу с AA.

Ответ: 99

Программа для поразрядной конъюнкции

В Python поразрядная конъюнкция — знак &. Он выполняется раньше сравнения, поэтому x & 52 != 0 значит (x & 52) != 0. Скобки всё равно делают запись понятнее.

Если числа в условии меньше 64, они занимают разряды от 0 до 5. Старшие разряды xx тогда не влияют на ответ, поэтому достаточно проверить x в range(0, 1024). AA перебирают от 0 и печатают первое подходящее значение.

Пример задания

Открытый банк ФИПИ

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4.

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

((x & 52 ≠ 0) ∧ (x & 48 = 0)) → ¬(x & A = 0)

истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?

Потренируйте навык

Все задания на этот навык

Решать