Алгоритм решения задания 15. Часть 4

Тип 4

У нас за спиной уже целых три типа 15 заданий, для которых мы разобрали как ручное, так и программное решение. Теперь переходим к предпоследнему — четвёртому — типу этих заданий. Часто задания этого типа еще называются «задания с отрезками» и вот почему: в отличие от предыдущих формулировок, где были какие-либо функции, поразрядная конъюнкция или просто логическое высказывание с двумя неизвестными, здесь даются три отрезка. Два отрезка даны в явном виде, а длину третьего как раз и необходимо узнать исходя из истинности некоторого логического выражения.

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

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

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

В данной статье мы рассмотрим оба метода на нескольких примерах. Так что вы с уверенностью сможете выбрать подходящий именно вам стиль решения четвёртого типа 15 заданий ЕГЭ.

Алгоритм решения

Начнём мы, как обычно, с ручного метода. Для начала повторим некоторые математические термины.

В этих заданиях нам даны отрезки числовой прямой. Вспомним, что же это такое. Отрезком называется множество всех точек на числовой прямой между двумя числами, включая эти самые числа (концы отрезка). Отрезок обозначается квадратными скобками: [a; b].

Например, отрезок [2; 5] включает числа 2, 3, 4, 5 и все дробные числа между ними.

Не путайте отрезки и интервалы! Интервал — это множество точек между двумя числами, но без самих этих чисел (концы не включаются). Интервал обозначается круглыми скобками: (a; b).

Например, интервал (2; 5) включает все числа между 2 и 5, но не включает сами числа 2 и 5.

Также существуют полуинтервалы (или полуотрезки) — когда один конец включается, а другой нет: [a; b) или (a; b].

По условию 15 заданий от нас требуется найти длину отрезка. Длина отрезка — это расстояние между его концами. Для отрезка [a; b] длина вычисляется по формуле:

Важно не путать длину с количеством целых точек. В отрезке [3; 8] шесть целых чисел: 3, 4, 5, 6, 7 и 8. Но его геометрическая длина равна 8 − 3 = 5.

Открытая или закрытая граница тоже не меняет длину: [3; 8], (3; 8] и (3; 8) имеют длину 5. Скобки влияют на истинность формулы в концах, но не на расстояние между концами.

Длина = b — a

Например:

Длина отрезка [3; 8] равна 8 — 3 = 5
Длина отрезка [-2; 5] равна 5 — (-2) = 7

Ну а еще мы иногда будем называть точки «выколотыми». Выколотая точка — это точка, которая исключается из множества. Визуально на числовой прямой такая точка обозначается пустым кружком (в отличие от закрашенного для включённой точки).

Например, множество [2; 5) \ {3} означает отрезок от 2 до 5, где:

точка 2 включена
точка 5 не включена
точка 3 выколота (исключена)

Кстати, на языке Python это множество можно записать таким образом: (x >= 2) and (x < 5) and (x != 3).

В заданиях ЕГЭ при работе с логическими операциями, а особенно с отрицанием (НЕ), часто возникают обратные множества или дополнение множества.

Дополнение множества A — это все элементы, которые не входят в множество A. Другими словами, если мы возьмем всю числовую прямую и «вырежем» из нее множество A, то всё оставшееся и будет дополнением. Обозначаются такие множества чертой сверху: Ā.

Здесь снова работают законы де Моргана. Условие x ∈ [a; b] означает (x ≥ a) ∧ (x ≤ b). Его отрицание равно (x < a) ∨ (x > b).

Поэтому дополнение одного отрезка распадается на два луча. Если исходные концы включены, в дополнении они выколоты: одно и то же число не может одновременно входить и в множество, и в его дополнение.

Рассмотрим дополнение на примере. Нам дано множество A = [2; 5] (отрезок, включающий точки 2 и 5). Нарисуем числовую прямую и отметим этот отрезок:

Дополнение — это всё, что не закрашено зелёным, то есть всё, кроме отрезка [2; 5]:

Результат: Ā = (-∞; 2) ∪ (5; +∞), обратите внимание на выколотые точки:

Точка 2 была включена в A (квадратная скобка), поэтому в дополнении она не включена (круглая скобка)
Точка 5 была включена в A, поэтому в дополнении она не включена
Дополнение состоит из двух частей, объединённых знаком ∪ (объединение)

Как читать формулу как условие о множествах

Фраза «если x входит в P, то x входит в Q» должна быть истинна для всех x. Это возможно ровно тогда, когда каждый элемент P содержится в Q, то есть P ⊆ Q.

Эквивалентность P ≡ Q требует одинаковой принадлежности: x либо входит в оба множества, либо не входит ни в одно. Она ложна на симметрической разности — там, где x принадлежит ровно одному из множеств.

Эти два перевода позволяют видеть за символами геометрию. Вместо длинной таблицы истинности мы спрашиваем: какой участок должен содержаться в A и какой участок A не должен захватывать?

Рассмотрим более «серьёзный» пример. Нужно найти наименьшее число А, при котором для любого числа x выполняется импликация:

((x ∈ [10; 20]) → (x ∈ [5; A]))

Первым делом определим, когда наша импликация ложна: импликация P → Q ложна только в одном случае: когда P истинно, а Q ложно. Во всех остальных случаях она истинна.

Когда наша импликация будет ложной? Когда:

P: (x ∈ [10; 20]) = истина
Q: (x ∈ [5; A]) = ложь

То есть x принадлежит [10; 20], но не принадлежит [5; A].

Условие «x не принадлежит [5; A]» и есть дополнение этого отрезка: x ∈ (−∞; 5) ∪ (A; +∞).

Нам нужно, чтобы импликация была истинна для всех x. Значит, ложный случай не должен наступать никогда. Ложный случай — это когда x одновременно в [10; 20] и в дополнении [5; A]. То есть пересечение [10; 20] и (-∞; 5) ∪ (A; +∞) должно быть пустым!

Напомним, что пересечение двух множеств — это те числа, которые одновременно принадлежат и первому множеству, и второму множеству. Представьте два круга, которые частично накладываются друг на друга (как кольца Олимпиады).

Пересечение — это та область, где круги перекрываются, то есть где выполняются оба условия одновременно. С пересечением мы также работали при решении 6 заданий.

В нашем случае мы ищем пересечение отрезка [10; 20] и дополнения (-∞; 5) ∪ (A; +∞). Другими словами, мы ищем такие числа x, которые одновременно:

принадлежат отрезку [10; 20], то есть лежат между 10 и 20 включительно
не принадлежат отрезку [5; A], то есть находятся либо левее 5, либо правее A

Вспомним условие задачи: импликация должна быть истинна для всех x. Это значит, что не должно существовать ни одного числа x, при котором импликация станет ложной.

А когда импликация ложная? Когда x одновременно лежит в [10; 20] и в дополнении отрезка [5; A]. Если такое число x существует, то при этом x импликация даст ложь, и условие задачи нарушится.

Поэтому нам нужно, чтобы таких «плохих» чисел вообще не было. То есть не должно быть ни одного числа, которое одновременно лежит и в [10; 20], и в дополнении [5; A]. А «не должно быть ни одного числа в пересечении» математически как раз и означает, что пересечение пустое.

Итак, дополнение состоит из двух частей: (-∞; 5) и (A; +∞). Давайте проверим каждую часть отдельно.

Сначала берём левую часть дополнения: (-∞; 5). Это все числа, которые меньше пятёрки. Теперь спросим себя: есть ли в отрезке [10; 20] хотя бы одно число, которое меньше пятёрки? Тут даже без визуализации понятно, что самое маленькое число в отрезке [10; 20] — это десятка, а она уже больше пятёрки. Значит, в отрезке [10; 20] нет ни одного числа, которое было бы меньше пятёрки. Пересечение [10; 20] с (-∞; 5) пустое. Отлично, с этой частью всё хорошо.

Теперь берём правую часть дополнения: (A; +∞). Это все числа, которые больше A. И вот тут начинается самое интересное, потому что A — это как раз то, что мы ищем!

Спросим себя: есть ли в отрезке [10; 20] числа, которые больше A? Это зависит от того, какое значение имеет A.

Давайте нарисуем несколько вариантов. Для начала, пусть А равняется 15:

Смотрим на картинку. В отрезке [10; 20] есть числа больше 15? Конечно есть! Например, 16, 17, 18, 19, 20. Все эти числа одновременно лежат и в [10; 20], и в (15; +∞). Значит, пересечение не пустое. Это плохо, потому что для всех этих чисел (16, 17, 18, 19, 20) импликация будет ложной. A = 15 нам не подходит.

Теперь увеличим значение А до 19:

В отрезке [10; 20] есть числа больше 19? Да, есть число 20. Оно одновременно лежит и в [10; 20], и в (19; +∞). Пересечение опять не пустое. A = 19 тоже не подходит.

Но увеличив значение А до 20, всё становится на свои места:

Луч (20; +∞) начинается сразу после двадцатки (круглая скобка означает, что 20 не включается). А отрезок [10; 20] заканчивается на двадцатке (квадратная скобка означает, что 20 включается в отрезок). Есть ли в отрезке [10; 20] числа, которые больше 20? Нет! Самое правое число в отрезке — это сама двадцатка, а она уже не входит в луч (20; +∞). Значит, пересечение пустое! Ура, A = 20 подходит.

Таким образом, мы проверили, что пересечение отрезка [10; 20] с левой частью дополнения пустое автоматически (потому что 10 > 5). А вот пересечение с правой частью дополнения зависит от A.

Чтобы пересечение отрезка [10; 20] с лучом (A; +∞) было пустым, нужно, чтобы в отрезке [10; 20] не было ни одного числа больше A. Самое большое число в отрезке [10; 20] — это двадцатка. Значит, A должно быть не меньше двадцати: A ≥ 20.

Задача просит найти наименьшее целое A. Наименьшее целое число, удовлетворяющее условию A ≥ 20, это само число 20 — задача решена!

Проверим наш учебный ответ на границе. При A = 19 точка x = 20 входит в [10; 20], но не входит в [5; 19]. Получаем истина → ложь, то есть ложь.

При A = 20 весь отрезок [10; 20] содержится в [5; 20]. Поэтому всякий раз, когда посылка истинна, истинно и заключение. А если посылка ложна, импликация истинна автоматически.

И примерно такую же логику мы будем применять для решения реальных заданий ЕГЭ. Давайте убедимся в этом на задании с такой формулировкой:

На числовой прямой даны два отрезка: B = [36; 75] и C = [60; 110].

Укажите наименьшую возможную длину такого отрезка A, что логическое выражение ¬(x ∈ A) → ((x ∈ B) ≡ (x ∈ C)) истинно (т.е. принимает значение 1) при любом значении переменной х.

Открыть задание

Давайте сначала нарисуем на числовой прямой отрезки B и C, чтобы понять, как они расположены относительно друг друга.

Отрезок B = [36; 75]:

Отрезок C = [60; 110]:

Теперь нарисуем оба отрезка на одной прямой:

Видим, что отрезки частично перекрываются. Есть область, где они пересекаются (от 60 до 75), есть область, где есть только B (от 36 до 60), и есть область, где есть только C (от 75 до 110).

Перекрытие [60; 75] — спокойная зона: обе принадлежности истинны. Вне обоих отрезков обе принадлежности ложны, и это тоже спокойная зона.

Опасными остаются два «крыла», где принадлежности различаются. Слева это часть только B, справа — часть только C. На языке множеств это симметрическая разность B и C.

Теперь переходим ко второму шагу — анализу логического выражения. В нашей формуле есть знак ≡ (эквивалентность). Эквивалентность — это логическая операция, которая возвращает истину тогда и только тогда, когда обе части имеют одинаковое значение.

То есть (x ∈ B) ≡ (x ∈ C) истинно в двух случаях:

Когда x принадлежит и отрезку B, и отрезку C одновременно
Когда x не принадлежит ни отрезку B, ни отрезку C

Третьим шагом будет разбиение числовой прямой на зоны в зависимости от того, каким отрезкам принадлежит x. У нас будет 5 зон:

x < 36 (левее обоих отрезков)
36 ≤ x < 60 (только в B)
60 ≤ x ≤ 75 (в обоих отрезках)
75 < x ≤ 110 (только в C)
x > 110 (правее обоих отрезков)

Теперь проанализируем истинность выражения (x∈ B) ≡ (x∈ C) в каждой зоне:

Зона 1:

x ∉ B (x не принадлежит B)
x ∉ C (x не принадлежит C)
(x ∈ B) = ложь, (x ∈ C) = ложь
(x ∈ B) ≡ (x ∈ C) ⇒ ложь ≡ ложь ⇒ истина

Зона 2:

x ∈ B
x ∉ C
(x ∈ B) = истина, (x ∈ C) = ложь
(x ∈ B) ≡ (x ∈ C) ⇒ истина ≡ ложь ⇒ ложь

Зона 3:

x ∈ B
x ∈ C
(x ∈ B) = истина, (x ∈ C) = истина
(x ∈ B) ≡ (x ∈ C) ⇒ истина ≡ истина ⇒ истина

Зона 4:

x ∉ B
x ∈ C
(x ∈ B) = ложь, (x ∈ C) = истина
(x ∈ B) ≡ (x ∈ C) ⇒ ложь ≡ истина ⇒ ложь

Зона 5:

x ∉ B
x ∉ C
(x ∈ B) = ложь, (x ∈ C) = ложь
(x ∈ B) ≡ (x ∈ C) ⇒ ложь ≡ ложь ⇒ истина

Изобразим это на прямой (зелёные зоны — истина, оранжевые — ложь):

На четвёртом шаге проанализируем импликацию. Вспомним, когда импликация ложна: только когда левая часть истинна, а правая ложна.

Левая часть: ¬(x ∈ A) — это «x не принадлежит A», то есть x находится в дополнении отрезка A (Ā).

Правая часть: (x ∈ B) ≡ (x ∈ C) — мы уже разобрали, когда она истинна и когда ложна.

Импликация будет ложной, когда:

¬(x ∈ A) = истина, то есть x не принадлежит A
И при этом (x ∈ B) ≡ (x ∈ C) = ложь

Мы уже знаем, что (x ∈ B) ≡ (x ∈ C) = ложь в зонах 2 и 4, то есть, когда x ∈ [36; 60) или x ∈ (75; 110].

Можно получить тот же вывод одной цепочкой преобразований. Импликация ¬A → E равносильна A ∨ E. Она ложна только там, где A ложно и E ложно.

Следовательно, все точки, где эквивалентность E ложна, обязаны попасть в A. Иначе найдётся x вне A, на котором правая часть тоже ложна.

Значит, импликация будет ложной, когда x одновременно:

не принадлежит A
принадлежит либо отрезку [36; 60), либо отрезку (75; 110]

Значит, что нам нужно сделать? Нужно избавиться от тех случаев, когда импликация будет ложная. То есть сделать так, чтобы не существовало числа x, которое одновременно не принадлежит A и находится в зонах 2 и 4.

Иными словами, отрезок А должен «покрывать» обе эти зоны. То есть содержать в себе как зону 2 (от 36 до 60), так и зону 4 (от 75 до 110).

Значит, минимальный отрезок, который содержит обе эти области, должен начинаться не позже 36 и заканчиваться не раньше 110.

Но давайте будем точнее. Зона 2 — это [36; 60), то есть от 36 включительно до 60 не включая. Зона 4 — это (75; 110], то есть от 75 не включая до 110 включительно.

Чтобы A содержал [36; 60), левая граница A должна быть ≤ 36, а правая граница должна быть > 60 (или ≥ 60, если правая граница включается).

Чтобы A содержал (75; 110], левая граница A должна быть < 75 (или ≤ 75, если левая граница не включается), а правая граница должна быть ≥ 110.

Объединяя эти условия:

Левая граница A должна быть ≤ 36
Правая граница A должна быть ≥ 110

Минимальный отрезок, удовлетворяющий обоим условиям: A = [36; 110].

Осталось лишь вычислить длину такого отрезка: 110 – 36 = 74. Таким образом, наименьшая возможная длина отрезка A равна 74. Это число и запишем в ответ.

Но вы лучше всегда проверяйте полученные значения, особенно на экзамене! Для этого нужно проверить истинность импликации, подставляя значения из полученного диапазона A. И, кроме этого, проверьте возможность «укоротить» отрезок А, чтобы убедиться, что полученный отрезок действительно минимальный.

Давайте резюмируем все вышесказанное и выведем такой шаблонный алгоритм ручного решения 15 задания четвёртого типа:

Шаг 1. Изобразите данные отрезки на числовой прямой

Нарисуйте все отрезки, которые даны в условии (B, C и другие, если есть). Отметьте границы отрезков и посмотрите, как они расположены относительно друг друга: пересекаются ли, есть ли промежутки между ними.

Шаг 2. Поймите логическую операцию в правой части импликации

Определите, какая логическая операция используется (эквивалентность ≡, конъюнкция ∧, дизъюнкция ∨ и т.д.). Вспомните её таблицу истинности.

Основные операции:

Эквивалентность (P ≡ Q): истинна, когда P и Q имеют одинаковые значения (оба истинны или оба ложны)
Конъюнкция (P ∧ Q): истинна, только когда оба P и Q истинны
Дизъюнкция (P ∨ Q): истинна, когда хотя бы одно из P или Q истинно
Импликация (P → Q): ложна только когда P истинно, а Q ложно

При необходимости примените законы математической логики.

Шаг 3. Разбейте числовую прямую на зоны

Границы отрезков B, C (и других) делят числовую прямую на несколько зон. Для каждой зоны определите:

Принадлежит ли x отрезку B?
Принадлежит ли x отрезку C?
Какое значение принимает правая часть импликации (истина или ложь)?

Выпишите это в виде таблицы или отметьте прямо на числовой прямой.

Шаг 4. Найдите «опасные зоны»

Опасные зоны — это те участки числовой прямой, где правая часть импликации ложна (зачастую в заданиях этого типа дана как раз импликация).

Почему они опасные? Потому что если x попадёт в опасную зону и при этом не будет принадлежать отрезку A (то есть левая часть импликации ¬(x ∈ A) будет истинна), то вся импликация станет ложной, и условие задачи нарушится.

Шаг 5. Определите, что должен содержать отрезок A

Чтобы импликация была истинна для всех x, отрезок A обязательно должен полностью покрывать все опасные зоны.

Если x находится в опасной зоне, но принадлежит A, то левая часть импликации ¬(x ∈ A) будет ложной, и вся импликация автоматически станет истинной (ложь → что угодно = истина).

Шаг 6. Найдите минимальный отрезок A

Определите:

Какая самая левая точка всех опасных зон? Это будет левая граница A.
Какая самая правая точка всех опасных зон? Это будет правая граница A.

Обратите внимание на тип скобок (включается граница или нет) в опасных зонах и соответственно постройте A.

Если опасные зоны не соприкасаются, а в задаче требуется один отрезок A, то придётся взять отрезок, который покроет все промежутки между опасными зонами.

Это важный момент. Нам разрешён один отрезок, а не объединение двух отрезков. Поэтому вместе с двумя опасными крыльями A неизбежно захватит и безопасный промежуток между ними.

В нашем примере нужно покрыть [36; 60) и (75; 110]. Самый короткий единый отрезок соединяет крайние обязательные точки: [36; 110]. То, что участок [60; 75] сам по себе безопасен, не позволяет его вырезать.

Если один заданный отрезок целиком лежит внутри другого, картина будет похожей: опасными станут два края большого отрезка. Для одного A всё равно придётся соединить их и накрыть внутренний промежуток.

Шаг 7. Вычислите длину отрезка A

Длина отрезка [a; b] вычисляется по формуле: длина = b — a

Шаг 8. Проверьте решение (по возможности)

Проверьте несколько характерных точек:

Точки на границах отрезка A
Точки внутри опасных зон
Точки вне опасных зон

Ещё два расположения отрезков

Чтобы алгоритм не привязался в памяти к одной картинке, рассмотрим две другие ситуации. Сама формула останется прежней: ¬(x ∈ A) → ((x ∈ B) ≡ (x ∈ C)).

Сначала пусть B = [2; 5], а C = [9; 12]. Отрезки не пересекаются. Эквивалентность ложна на всём B и на всём C, потому что в каждой из этих областей x входит ровно в один отрезок.

Отрезок A обязан покрыть обе опасные области. Но A должен быть одним непрерывным отрезком, поэтому он захватит и безопасный промежуток от 5 до 9. Минимальный вариант — [2; 12], его длина равна 10.

Теперь пусть C = [7; 10] целиком лежит внутри B = [3; 14]. Внутри C обе принадлежности истинны, а снаружи B обе ложны. Опасны только левое и правое «крылья» большого отрезка.

Получаем [3; 7) и (10; 14]. Чтобы накрыть их одним A, снова соединяем крайние обязательные точки: A = [3; 14]. Длина равна 11.

Эти примеры показывают общий принцип: нас интересует не вид рисунка сам по себе, а самые левая и правая точки всех обязательных зон. Между ними один отрезок A заполнит всё автоматически.

Как восстановить ручной алгоритм на экзамене

Если последовательность шагов вылетела из головы, начните с вопроса: «При каком x вся формула станет ложной?» Не пытайтесь сразу угадывать A по рисунку.

Выпишите ложный случай каждой операции. Для импликации это истина → ложь, для эквивалентности — разные значения, для дизъюнкции — все части ложны.

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

В конце возьмите по одной точке из каждой зоны и точки на границах. Такая проверка обычно сама обнаруживает перепутанную скобку или неверно раскрытое отрицание.

Программное решение

Почему программный алгоритм конечный?

На первый взгляд x принимает все действительные значения, а концов у A бесконечно много. Но формула меняется только тогда, когда x проходит через одну из границ заданных отрезков.

Между соседними границами ничего не меняется: x продолжает входить в те же множества. Поэтому для каждой открытой зоны достаточно взять одну точку, например её середину.

Сами границы проверяем отдельно. В точке 20 условие x ≤ 20 истинно, а сразу справа от неё — уже ложно. Только середины не заметили бы разницу между квадратной и круглой скобкой.

Наконец, берём по одной точке левее всех границ и правее всех границ. Так программа проверяет крайние бесконечные лучи, не пытаясь перебирать бесконечность.

Что же, с ручным решением разобрались, перейдём теперь к программному. Начнём разбор с вот такого задания:

На числовой прямой даны два отрезка: B = [14; 20] и C = [15; 27].

Открыть задание

Оно во многом похоже на предыдущее. И по опыту решения прошлого задания, можем сразу сказать, что отрезок A здесь будет от 14 до 27, то есть иметь длину 13.

Но теперь давайте добьёмся этого значения от программы!

Для перебора границ отрезка используем combinations_with_replacement из модуля itertools. Она, в отличие от combinations, не потеряет вариант отрезка нулевой длины [a; a].

from itertools import combinations_with_replacement

Функция принимает не только x, но и обе границы проверяемого отрезка A:

def f(x, A1, A2):
    B = 14 <= x <= 20
    C = 15 <= x <= 27
    A = A1 <= x <= A2

А после ключевого слова return запишем логическое выражение. При этом принадлежность x к какому-либо отрезку будем писать просто буквой этого отрезка. Например, если x принадлежит B (x∈ B), то запишем это просто буквой B.

Тогда выражение из условия можно записать так: (not A) <= (B == C). Добавим эту запись в код:

def f(x, A1, A2):
    B = 14 <= x <= 20
    C = 15 <= x <= 27
    A = A1 <= x <= A2
    return (not A) <= (B == C)

Значение формулы меняется только на границах исходных отрезков. Поэтому соберём все границы в отсортированный список points.

x < 14 (левее обоих отрезков)
14 ≤ x < 15 (только в B)
15 ≤ x ≤ 20 (в обоих отрезках)
20 < x ≤ 27 (только в C)
x > 27 (правее обоих отрезков)

Для наглядности дополнитель отобразим на числовой прямой эти отрезки:

Сразу отметим, что крайние зоны (1 и 5) нас не интересуют: не могут быть значения отрезка A от какого-либо числа до бесконечности.

То есть нам следует перебрать такие отрезки:

От 14 до 15 (зона 2)
От 14 до 20 (зоны 2 и 3)
От 14 до 27 (зоны 2, 3, 4)
От 15 до 20 (зона 3)
От 15 до 27 (зоны 3 и 4)
От 20 до 27 (зона 4)

Кандидатами на границы A будут пары точек из этого списка.

Почему концы A тоже можно искать среди исходных границ? Пока мы двигаем конец внутри одной зоны, набор обязательных точек не меняется. Для минимальной или максимальной длины выгодно дотянуть его до ближайшей значимой границы.

Функция combinations_with_replacement создаёт пары в неубывающем порядке: A1 ≤ A2. Повторение разрешает пару (14, 14), то есть вырожденный отрезок длины ноль.

Повторяющиеся границы нам не нужны, поэтому удобно сразу создать множество и отсортировать его:

points = sorted({14, 20, 15, 27})

Отдельно подготовим контрольные x. Нужно проверить сами границы, точки между соседними границами и по одной точке слева и справа.

Для точек 14, 15, 20 и 27 мы проверяем включённость концов. Середины 14.5, 17.5 и 23.5 представляют три промежуточные зоны. Точки 13 и 28 представляют внешние лучи.

Итого вместо бесконечного множества x получается всего девять контрольных значений. Это не приближение: в каждой из остальных точек набор истинных предикатов будет точно таким же, как у одного из представителей.

points = sorted({14, 20, 15, 27})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]

Так мы не пропустим отличия между закрашенной и выколотой границей.

Теперь переберём все пары границ A и сохраним длины подходящих отрезков.

points = sorted({14, 20, 15, 27})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]
ans = []
for A1, A2 in combinations_with_replacement(points, 2):
    if all(f(x, A1, A2) for x in test_x):
        ans.append(A2 - A1)

Осталось лишь добавить поиск минимума среди списка границ ans:

from itertools import combinations_with_replacement


def f(x, A1, A2):
    B = 14 <= x <= 20
    C = 15 <= x <= 27
    A = A1 <= x <= A2
    return (not A) <= (B == C)


points = sorted({14, 20, 15, 27})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]

ans = []
for A1, A2 in combinations_with_replacement(points, 2):
    if all(f(x, A1, A2) for x in test_x):
        ans.append(A2 - A1)

print(min(ans))

Наша программа готова! Запускаем её и видим заветное число 13, как мы и предполагали в начале. Значит, программа работает корректно, и число 13 можно смело записывать в ответ.

Что делает программа:

Проследим одну неудачную попытку. Если программа возьмёт A = [14; 20], то в точке x = 23.5 предикат C истинен, B ложен, а A ложен. Эквивалентность ложна, посылка ¬A истинна — импликация рушится.

Теперь берём A = [14; 27]. В обеих зонах, где B и C различаются, предикат A истинен. Поэтому ¬A ложен, а импликация автоматически истинна. В остальных зонах эквивалентность и так истинна.

Функция f проверяет формулу для x и конкретного отрезка [A1; A2].
points хранит все границы, на которых может измениться истинность формулы.
combinations_with_replacement(points, 2) создаёт все отрезки, чьи концы совпадают с важными границами.
test_x содержит границы, середины всех зон и точки за крайними границами.
Для каждого A функция all требует истинности формулы во всех контрольных точках.
Длины подходящих отрезков попадают в ans, после чего min(ans) выбирает наименьшую.

Общий шаблон для B = [B1; B2] и C = [C1; C2]:

from itertools import combinations_with_replacement


def f(x, A1, A2):
    B = B1 <= x <= B2
    C = C1 <= x <= C2
    A = A1 <= x <= A2
    return выражение_из_условия


points = sorted({B1, B2, C1, C2})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]

ans = []
for A1, A2 in combinations_with_replacement(points, 2):
    if all(f(x, A1, A2) for x in test_x):
        ans.append(A2 - A1)

print(min(ans))

Вам останется вписать границы данных отрезков, сохранить структуру перебора и правильно переписать логическое выражение из условия.

Помните, это лишь один из вариантов программного решения 15 заданий четвёртого типа. Эту программу можете еще модернизировать под себя: иначе определять выражение из условия, граничные значения для x и так далее. Главное, чтобы программа эффективно и правильно решала задания, а еще важнее, чтобы вы не забыли этот код на экзамене!

Но, как пример, в прошлой версии разбора этого типа мы приводили такой код:

from itertools import combinations_with_replacement


def f(x):
    B = 14 <= x <= 20
    C = 15 <= x <= 27
    A = A1 <= x <= A2
    return (not A) <= (B == C)


line_A = sorted([14, 20, 15, 27])
line_x = [14.5, 20.5, 15.5]

ans = []
for A1, A2 in combinations_with_replacement(line_A, 2):
    if all(f(x) for x in line_x):
        ans.append(A2 - A1)

print(min(ans))

Он работает и даже выдаёт правильный ответ на эту задачу, но у него есть недостатки, из-за которых мы от него отказались.

Во-первых, функция f(x) берёт значения A1 и A2 «из воздуха»: они появляются только в цикле ниже, а внутри функции нигде не объявлены. Python такое позволяет, но разобраться в этом новичку непросто, а на экзамене легко запутаться. Гораздо понятнее передавать в функцию всё, от чего зависит результат: f(x, A1, A2).

Во-вторых, и это главное, список line_x мы составляли вручную: взяли середины между соседними границами и записали их числами. Для этой конкретной задачи такой список подходит. Но в другом условии границы будут другими, и придётся каждый раз заново считать середины и не ошибиться. К тому же в нём нет сами границ 14, 15, 20, 27, хотя из-за знаков <= именно в них формула может измениться, и нет точек левее и правее всех отрезков. В итоге можно пропустить зону, в которой формула ложна, и получить неверный ответ.

Поэтому в новой версии проверочные точки программа строит сама, по единому правилу:

points = sorted({14, 20, 15, 27})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]

Сначала берём по одной точке слева и справа от всех границ. Затем сами границы. Затем середины между соседними границами. Так мы проверяем все места, где формула может поменять своё значение. При этом меняется только список points: в него вы переписываете числа из условия, остальное остаётся как есть.

Пример 1

Для закрепления решим еще одно задание:

Не пугайтесь других обозначений или сложного логического выражения. На нашу программу это никак не повлияет!

Здесь важно сохранить имена из условия: P — принадлежность [25; 64], Q — принадлежность [40; 115], A — принадлежность проверяемому отрезку. Имена в return должны совпадать с именами выше.

Разберём логику. Внешняя импликация интересует нас только при x ∈ P. Внутренняя импликация может стать ложной, когда x ∈ Q, x ∉ A, но x ∈ P.

Значит, опасная область — пересечение P и Q, не покрытое A. Пересечение равно [40; 64], поэтому самый короткий A должен покрыть именно его. Длина равна 64 − 40 = 24.

Теперь ответ программы не выглядит случайной цифрой: код лишь перебором подтверждает уже понятную геометрическую картину.

Импортируем combinations_with_replacement и записываем функцию f:

from itertools import combinations_with_replacement


def f(x, A1, A2):
    P = 25 <= x <= 64
    Q = 40 <= x <= 115
    A = A1 <= x <= A2
    return P <= ((Q and (not A)) <= (not P))

Далее в шаблонном коде меняем только числа в списке points (но сами числа у нас во множестве всё еще):

points = sorted({25, 64, 40, 115})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]

ans = []
for A1, A2 in combinations_with_replacement(points, 2):
    if all(f(x, A1, A2) for x in test_x):
        ans.append(A2 - A1)

print(min(ans))

Запишем программу целиком:

from itertools import combinations_with_replacement


def f(x, A1, A2):
    P = 25 <= x <= 64
    Q = 40 <= x <= 115
    A = A1 <= x <= A2
    return P <= ((Q and (not A)) <= (not P))


points = sorted({25, 64, 40, 115})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]

ans = []
for A1, A2 in combinations_with_replacement(points, 2):
    if all(f(x, A1, A2) for x in test_x):
        ans.append(A2 - A1)

print(min(ans))

Запускаем её и получаем ответ на это задание — число 24.

Итоги

В четвёртом типе задания 15 мы превратили числовую прямую в конечный набор зон. В каждой зоне принадлежность отрезкам постоянна, поэтому достаточно найти участки, где формула может стать ложной, и понять, должен ли A их покрыть или, наоборот, избегать.

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

Проверка перед ответом

Сначала перечитайте вопрос: требуется наименьшая или наибольшая длина? Даже верно найденные опасные зоны дадут неправильный ответ, если выбрать не тот экстремум.

Затем проверьте крайние точки. Квадратная скобка включает границу, круглая исключает её. Подставьте каждую границу прямо в исходную формулу, не полагаясь только на рисунок.

Убедитесь, что вы нашли длину, а не число целых точек. Для концов a и b в ответ идёт b − a, независимо от того, открыты или закрыты границы.

В программном решении отдельно должны присутствовать сами границы, точки между ними и точки снаружи. Если оставить только целые x, можно пропустить ложную зону между соседними целыми границами.

Наконец, прочитайте строку return как обычное предложение. Все обозначения P, Q, B, C и A должны совпадать с переменными, объявленными выше. Такая минутная проверка спасает от самой обидной ошибки — правильного алгоритма с неправильным именем.

В следующей статье разберём пятый тип задания 15 — с множествами натуральных делителей.

Шаблон решения

from itertools import combinations_with_replacement

def f(x, A1, A2):
    B = B1 <= x <= B2
    C = C1 <= x <= C2
    A = A1 <= x <= A2
    return *1

points = sorted({B1, B2, C1, C2})
test_x = [points[0] - 1, points[-1] + 1]
test_x += points
test_x += [(a + b) / 2 for a, b in zip(points, points[1:])]

ans = []
for A1, A2 in combinations_with_replacement(points, 2):
    if all(f(x, A1, A2) for x in test_x):
        ans.append(A2 - A1)
print(*2(ans))

Здесь B1, B2, C1, C2 — концы отрезков из условия, *1 — формула из условия, *2 — min или max в зависимости от вопроса. Если в условии другие названия отрезков (например, P и Q), меняйте их одинаково в функции и в списке points.