Алгоритм решения задания 15 ЕГЭ по информатике. Часть 4

Тип 4

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

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

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

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

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

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

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

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

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

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

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

Длина = 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, то всё оставшееся и будет дополнением. Обозначаются такие множества чертой сверху: Ā.

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

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

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

• Точка 2 была включена в A (квадратная скобка), поэтому в дополнении она не включена (круглая скобка)
• Точка 5 была включена в 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 ∈ (-∞; 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 — задача решена!

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

Задание 1514

«На числовой прямой даны два отрезка: 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).

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

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

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

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

1. x < 36 (левее обоих отрезков)
2. 36 ≤ x < 60 (только в B)
3. 60 ≤ x ≤ 75 (в обоих отрезках)
4. 75 < x ≤ 110 (только в C)
5. 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].

Значит, импликация будет ложной, когда 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, то придётся взять отрезок, который покроет все промежутки между опасными зонами.

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

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

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

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

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

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

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

Задание 1519

«На числовой прямой даны два отрезка: B = [14; 20] и C = [15; 27]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение ¬(x ∈ A) → ((x ∈ B) ≡ (x ∈ C)) истинно (т.е. принимает значение 1) при любом значении переменной х.»

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

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

В самом начале уже была упомянута функция combinations из модуля itertools. Хоть пока мы до неё не дошли, давайте все же импортируем её:

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

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

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

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

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

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

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

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

И среди всех этих шести вариантов как раз будет находиться интересующий нас отрезок А. Давайте подумаем, как получить эти отрезки? Для этого нам и пригодится combinations!

Для начала нам стоит выписать в нужном порядке все точки на числовой прямой. Эти точки обязательно должны располагаться в порядке возрастания! Если не уверены в том, что безошибочно перепишете все значения, то можете воспользоваться функцией sorted(), в которую требуется передать список чисел прямо из условия: 14, 20, 15, 27:

Давайте проверим, что с таким отсортированным списком сделаем функция combinations. Поскольку нам нужны пары чисел (концы отрезка), то в качестве второго параметра будем передавать число 2:

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

Теперь вернёмся к нашему решению и допишем строчку со списком line_A:

Что же, отрезки мы получим, но как проверить истинность логического высказывания? Нужны же какие-то значения для переменной x.

Для этого нам достаточно будет взять по одной точке внутри каждой рассматриваемой зоны. Это могут быть любые точки, но мы будем брать значения на 0,5 больше, чем границы отрезков. Дробное число берётся как раз из-за того, что нужно проверить отрезок от 14 до 15. В таком случае можем взять, например, число 14,5, которое как раз будет больше 14 и меньше 15.

Таких чисел у нас будет 3: во второй, третьей и четвёртой зонах, поскольку первую и пятую зоны мы уже исключили из решения. Запишем эти числа в виде списка line_x (здесь порядок не важен):

Почти закончили! Создадим пустой список ans, в который будем помещать все допустимые длины отрезков:

Ну а теперь в цикле будем перебирать значения A1 и A2 из кортежей, которые вернёт функция combinations:

Внутри цикла у нас перебираются все точки внутри допустимых зон (из line_x), и если выражение из функции f() возвращает истину для всех контрольных точек, то значит такой отрезок от A1 до A2 подходит.

Для проверки всех точек используем функцию all(), которая возвращает True, только если все элементы истинны:

Следовательно, если условие выполнилось, такой отрезок нам подходит, и мы сохраняем его длину в ans:

В конце же выводим минимальную длину отрезка среди сохранённых в ans:

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

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

1. Функция f(x) проверяет логическое выражение — она принимает число x и возвращает True, если для этого x логическое выражение из условия истинно, и False в противном случае.
2. Список line_A содержит все важные границы — это точки 14, 15, 20, 27, которые делят числовую прямую на зоны. Мы их сортируем, чтобы гарантировать порядок слева направо.
3. Функция combinations(line_A, 2) генерирует все возможные отрезки — она берёт любые две точки из списка line_A и создаёт из них пару (левая граница, правая граница). Всего получается 6 вариантов отрезков.
4. Список line_x содержит контрольные точки — это точки внутри каждой «интересной» зоны (14,5, 15,5 и 20,5), которые мы используем для проверки. Если отрезок A работает для всех этих точек, значит он работает для всей зоны.
5. Цикл перебирает все возможные отрезки A — для каждой пары (A1, A2) программа проверяет, выполняется ли условие для всех контрольных точек с помощью all(f(x) for x in line_x).
6. Сохраняем длины подходящих отрезков — если отрезок прошёл проверку, мы вычисляем его длину (A2 — A1) и добавляем в список ans.
7. Находим минимум — в конце программа выбирает самую маленькую длину из всех подходящих вариантов с помощью min(ans).

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

Давайте выведем шаблонный код, при условии, что: B = [*1; *2] и C = [*3; *4]:

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

Пример 1

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

Задание 1523

«На числовой прямой даны два отрезка: P = [25; 64] и Q = [40; 115]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение (x ∈ P) → (((x ∈ Q) ∧ ¬ (x ∈ A) → ¬ (x ∈ P)) истинно (т.е. принимает значение 1) при любом значении переменной х.»

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

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

Далее переписываем числа из условия:

И каждое, кроме последнего увеличиваем на 0,5:

А заключительная часть программы у нас никогда и не меняется:

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

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