Задание OGEINF6B7035: Поисковые запросы и множества

1. Переведём запросы на язык множеств.
A — страницы с ключевым выражением «Сомики»; B — страницы с ключевым выражением «Меченосцы»; C — страницы с ключевым выражением «Гуппи».
Пересечение ∩ означает выполнение обоих условий («И»), объединение ∪ — выполнение хотя бы одного («ИЛИ»). Общая страница входит в объединение один раз. N обозначает количество найденных объектов; все вычисления ведём в сайтах.
Из условия:
N(A) = 250.
N(B) = 200.
N(C) = 500.
N(A ∩ B) = 100.
N(A ∪ C) = 750.
N(B ∩ C) = 0.
Найти нужно N((A ∩ B) ∪ C). Всего в сегменте 1000 сайтов; это верхняя граница, а не количество сайтов, обязательно попавших в запрос.

2. Обоснуем подсчёт без повторов.
Для любых множеств X и Y выполняется N(X ∪ Y) = N(X) + N(Y) − N(X ∩ Y). При сложении общие страницы учитываются дважды, поэтому один раз вычитаем пересечение. Эту же формулу можно решить относительно неизвестного пересечения или одного из множеств.
Для трёх множеств получаем:
N(A ∪ B ∪ C) = N(A) + N(B) + N(C) − N(A ∩ B) − N(A ∩ C) − N(B ∩ C) + N(A ∩ B ∩ C).
Страница из одного множества учитывается один раз; из двух — 2 − 1 = 1 раз; из всех трёх — 3 − 3 + 1 = 1 раз. Поэтому формула считает каждую подходящую страницу ровно один раз.
Дополнительно N(B ∩ C) = 0 = 0. Это выражение равно сумме количеств в непересекающихся областях: есть B, C; нет A; либо есть A, B, C. Каждое количество неотрицательно; раз сумма нулевая, все перечисленные области пусты.
Дополнительно N(A) + N(C) − N(A ∪ C) = 250 + 500 − 750 = 0. Это выражение равно сумме количеств в непересекающихся областях: есть A, C; нет B; либо есть A, B, C. Каждое количество неотрицательно; раз сумма нулевая, все перечисленные области пусты.
С учётом этих соотношений выражаем искомое количество через известные:
N((A ∩ B) ∪ C) = N(C) + N(A ∩ B).

3. Подставим данные.
N((A ∩ B) ∪ C) = 500 + 100 = 600.
Полученное число выражено в сайтах. Умножать его на размер единицы таблицы не требуется: вопрос просит ответ в тех же единицах.

4. Проверка.
Перенесём остальные слагаемые обратно и восстановим одну известную величину:
N(C) = N((A ∩ B) ∪ C) − N(A ∩ B).
N(C) = 600 − 100 = 500.
Совпало с условием. Отдельно проверим, какие страницы учитывает полученная формула:
есть A; нет B, C — не учитывается.
есть B; нет A, C — не учитывается.
есть A, B; нет C — учитывается один раз.
есть C; нет A, B — учитывается один раз.
есть A, C; нет B — пустая область.
есть B, C; нет A — пустая область.
есть A, B, C — пустая область.
Таким образом, все и только страницы искомого запроса посчитаны без повторов.

Ответ: 600.