Решение задачи B12 (2012)

Задача

В языке запросов поискового сервера для обозначения логической операции ИЛИ используется символ "|", а для логической операции И - символ "&".
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос	Найдено страниц (в тысячах)
Шахматы | Теннис	7770
Теннис	5500
Шахматы & Теннис	1000

Какое количество страниц (в тысячах) будет найдено по запросу Шахматы?

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

Решение

Рассмотрим найденные по запросам наборы страниц как множества, мощность которых нам известна. 

Введём обозначения множеств. Пусть Ш - множество, содержащее все страницы, найденные по запросу Шахматы, а Т - множество, содержащее все страницы, найденные по запросу Теннис.
Нам известна мощность множества Т, а мощность множества Ш требуется найти.
|Т| = 5500

По определению логической операции ИЛИ, по запросу Шахматы|Теннис будут найдены все страницы, содержащие хотя бы одно из искомых слов. Это отвечает определению объединения множеств, в которое входят элементы, принадлежащие хотя бы одному множеству из объединения.
|Ш ∪ T| = 7770

Аналогично можно утверждать соответствие логической операции И пересечению множеств.
|Ш ∩ Т| = 1000

Рис 1. Жёлтым цветом показано множество Ш, голубым - множество Т, 

зелёным - пересечение Ш∩Т, штриховкой - объединение Ш∪T

Выразим мощность множества Ш через известные. По определению разности множеств:
1. |Ш ∪ T| - |Т| = |Ш \ Т|
2. |Ш \ Т| = |Ш| - |Ш ∩ Т|
3. |Ш| = |Ш \ Т| + |Ш ∩ Т| = |Ш∪T| - |Т| + |Ш∩Т|
Подставим известные значения в полученную формулу:
|Ш| = 7770-5500+1000=3270


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

Ответ: 3270