25.5.Еще пример задания

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

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

кроманьонец & (мезозой | неандерталец)

Р ешение (способ 1, круги Эйлера):

1. обозначим области «мезозой», «кроманьонец» и «неандерталец» буквами М, К и Н; пронумеруем подобласти, получившиеся в результате пересечений кругов (см. рисунок справа)

2. через N­_i обозначим количество сайтов в области с номером i

3. нас интересует результат запроса

кроманьонец & (мезозой | неандерталец)

то есть N­₂ + N₅ + N₆ (зеленая область на рисунке)

1. из первых двух запросов следует, что

N₁ + N₂ + N₄ + N₅ = 50 (мезозой)

N₂ + N₃ + N₅ + N₆ = 60 (кроманьонец)

1. складывая левые и правые части уравнений, получаем

(1) N₁ + 2·N₂ + N₃ + N₄ + 2·N₅ + N₆ = 110

1. в то же время из запроса 4 получаем

(2) N₁ + N₂ + N₃ + N₄ + N₅ + N₆ = 80 (мезозой | кроманьонец)

1. вычитая из уравнения (1) уравнение (2), отдельно левые и правые части, получаем

N₂ + N₅ = 30 (мезозой & кроманьонец)

вспомним, что наша цель – определить N­₂ + N₅ + N₆, поэтому остается найти N₆

1. из запросов 1 и 3 следует, что

N₁ + N₂ + N₄ + N₅ = 50 (мезозой)

N₄ + N₅ + N₆ + N₇ = 70 (неандерталец)

1. складывая левые и правые части уравнений, получаем

(3) N₁ + N₂ + 2·N₄ + 2·N₅ + N₆ + N₇ = 120

1. в то же время из запроса 5 получаем

(4) N₁ + N₂ + N₄ + N₅ + N₆ + N₇ = 100 (мезозой | неандерталец)

1. вычитая из уравнения (3) уравнение (4), отдельно левые и правые части, получаем

(5) N₄ + N₅ = 20 (мезозой & неандерталец)

1. теперь проанализируем запрос 6:

неандерталец & (мезозой | кроманьонец)

(6) N₄ + N₅ + N­₆ = 20

1. вычитая из уравнения (6) уравнение (5) получаем N₆ = 0, поэтому

N₂ + N₅ + N₆ = N₂ + N₅ = 30

1. таким образом, ответ – 30.

Решение (способ 2, М.С. Коротков, г. Челябинск, Лицей № 102):

1. пп. 1-3 такие же, как в первом способе;

2. из запросов 1 и 6 следует, что

1. N₄ + N₅ + N₆ + N₇ = 70 (неандерталец)

2. N₄ + N₅ + N­₆ = 20 неандерталец & (мезозой | кроманьонец)

1. вычитая (2) из (1), сразу получаем, что N₇ = 50

2. из запросов 5 и 4 следует, что

1. N₁ + N₂ + N₄ + N₅ + N₆ + N₇ = 100 (мезозой | неандерталец)

2. N₁ + N₂ + N₃ + N₄ + N₅ + N₆ = 80 (мезозой | кроманьонец)

1. вычитая (4) из (3), сразу получаем, что N₇ - N₃ = 20

2. в п. 3 мы уже определили, что N₇ = 50, поэтому 50 - N₃ = 20, откуда N₃ = 30

3. из запроса 2 получаем

N₂ + N₃ + N₅ + N₆ = 60 (кроманьонец)

поэтому размер интересующей нас области равен

N₂ + N₅ + N₆ = 60 – N₃ = 60 – 30 = 30

1. т аким образом, ответ – 30.

Решение (способ 3, круги Эйлера, И.Б. Курбанова, г. Санкт-Петербург, ГОУ СОШ № 594):

1. обозначим: М – мезозой, К – кроманьонец, Н – неандерталец.

2. нас интересует результат запроса (см. диаграмму Эйлера)

K & (M | Н)

1. т .к. по условию М = 50, К = 60, а объединение этих множеств М | К = 80, можно сделать вывод, что область пересечения

M & K = 50 + 60 – 80 = 30;

1. т.к. по условию М = 50, Н = 70, а объединение этих множеств М | Н = 100, можно сделать вывод, что область пересечения

M & Н = 50 + 70 – 100 = 20;

1. заметим, что M & Н = 20 и Н & (М | К) = 20, следовательно множества Н и К не пересекаются (К & Н = 0);

2. перерисуем диаграмму Эйлера так, чтобы множества К и Н не пересекались (см. рисунок справа); из новой схемы видно, что

К & (М | Н) = (К & М) | (К & Н) = К & М = 30

1. ответ: 30