МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Задание 4 - Формула включений – исключений

Часть 1

1.

Пусть P – множество прямоугольных треугольников, R – множество равнобедренных треугольников и S – множество равносторонних треугольников. Изобразите эти множества с помощью кругов Эйлера.

Ответ

Ответ.

Где зеленое - P, голубое - R, а синие - S.

2.

Все девочки в классе увлекаются вязанием или шитьем. Сколько девочек в классе, если вязанием занимаются 15 человек, шитьем – 20, а вязанием и шитьем – 10?

Решение Ответ

Решение.

. Сложим множество умеющих вязать и множество умеющих шить. Получим тех кто умеет только шить, только вязать и еще дважды посчитанных тех, кто умеет и то, и то. значит чтобы получить количество девочек, нужно сложить тех кто умеет шить, тех кто умеет вязать и вычесть тех, кто умеет и то и то. получим 15+20-10=25

Ответ. 25

3.

Докажите формулу включений – исключений для двух множеств:
|A∪B|=|A|+|B|-|A∩B|

Решение

Решение.

сложим множества |A| и |В|. мы получим, что в итоге мы Посчитали |A\B|+|B\A|+2*|A∩B|, а |A∩В| состоит из |A\B|+|B\A|+|A∩B|. Значит формула выглядит так: |A∪B|=|A|+|B|-|A∩B|

4.

В поход ходили 80% учеников класса, а на экскурсии было 60% класса, причем каждый был в походе или на экскурсии. Сколько процентов класса были и там, и там?

Решение Ответ

Решение. Из вышеупомянутой формулы выведем, что |A∩B|=|A|+|B|-|A∪B|, а значит и там и там было 80+60-100=40 процентов класса.

Ответ. 40%

Часть 2

5.

В первом классе читать умеют 12 учеников, считать – 8, писать – 9; читать и писать – 4, читать и считать – 5, писать и считать – 3; читать, писать и считать – 2; 6 учеников до сих пор ничему не научились. Сколько учеников в классе?

Решение Ответ

Решение.

Пусть множество |A|=12 - множество учеников умеющих читать, |B|=8 - умеющих считать, |C|=9 - умеющих писать, тогла |A∩С|=4 - читать и писать, |A∩B|=5 - читать и считать, |B∩С|=3 - считать и писать, а |A∩B∩С|=2 - читать и писать, При сложении |A|+|B|+|C|, мы получим |A\(B∪C)| + |B\(A∪C)| +|C\(B∪A)|+2*|(A∩С)\B|+2*|(A∩B)\C|+2*|(C∩B)\A|+3*|A∩B∩C|, значит нужно вычесть |(A∩С)\B| + |(A∩B)\C| + |(C∩B)\A| + 2*|A∩B∩C|(что-бы получить |A∪B∪C|) что равносильно |A∩С| + |A∩B| + |C∩B| - |A∩B∩C|, значит ответ будет вида 8+9+12-3-4-5+2=19, Но мы не учли то, что у нас есть еще 6 учеников, не занятых ничем, значит ответ 19+6=25

Ответ. 25

6.

Докажите формулу включений – исключений для трех множеств:
|A∪B∪C|=|A|+|B|+|C|-|A∩С|-|A∩B|-|C∩B|+|A∩B∩C|

Решение

Решение.

При сложении |A|+|B|+|C|, мы получим |A\(B∪C)| + |B\(A∪C)| +|C\(B∪A)|+2*|(A∩С)\B|+2*|(A∩B)\C|+2*|(C∩B)\A|+3*|A∩B∩C|, значит нужно вычесть |(A∩С)\B| + |(A∩B)\C| + |(C∩B)\A| + 2*|A∩B∩C|(что-бы получить |A∪B∪C|) что равносильно |A∩С| + |A∩B| + |C∩B| - |A∩B∩C|, значит формула будет вида |A∪B∪C|=|A|+|B|+|C|-|A∩С|-|A∩B|-|C∩B|+|A∩B∩C|

7.

В комнате площадью 6 м² постелили три ковра произвольной формы площадью 3 м² каждый. Докажите, что какие-либо два из них перекрываются по площади, не меньшей 1 м².

Решение

Решение. k(1)-Первый ковер,
K(2)-Второй ковер,
k(3)-Третий ковер.
По формуле, получаем, что
|k(1)∪k(2)∪k(3)|=|k(1)|+|k(2)|+|k(3)|-|k(1)∩k(2)|-|k(1)∩k(3)|-|k(2)∩k(3)|+|k(1)∩k(2)∩k(3)|,значит 6=3+3+3-|k(1)∩k(2)|-|k(1)∩k(3)|-|k(2)∩k(3)|+|k(1)∩k(2)∩k(3)|, а значит 3+|k(1)∩k(2)∩k(3)|=|k(1)∩k(2)|+|k(1)∩k(3)|+|k(2)∩k(3)|. Чтобы минимизировать правую сумму, надо минимизировать |k(1)∩k(2)∩k(3)|. Сделаем его равным нулю.
Сделаем предположение, что |k(1)∩k(2)|<1 ,|k(1)∩k(3)|<1, |k(2)∩k(3)|<1, но тогда и их сумма меньше трех, а значит противоречие, так как там сумма должна равнятся трем, значит хотябы один их них больше 1.

8.

В классе учится a(1) учеников, получивших в течение года хотя бы одну двойку, a(2) учеников, получивших не менее двух двоек, и т.д., a(k) учеников, получивших не менее k двоек. Сколько всего двоек в этом классе? (Предполагается, что ни у кого нет более k двоек).

Решение Ответ

Решение.

Количество учеников которые полуили только одну двойку, это a(1)-a(2), количество учеников, которые получили только две двойки a(2)-a(3) и так далее. Распишем сумму, учитывая количество двоек:
(|a(1)|-|a(2)|)+2*(|a(2)|-|a(3)|)+…+(k-1)*(|a(k-1)|-|a(k)|)+k*|a(k)|=
=|a(1)|+|a(2)|+…+|a(k-1)|+|a(k)|.

Ответ. |a(1)|+|a(2)|+…+|a(k-1)|+|a(k)|

Часть третья. Дополнительная.

9.

Обобщите формулу включений – исключений для

a)

4 множеств;

b)

5 множеств;

c)

n множеств.

10.

Художник Худобеднов за месяц работы написал 42 картины. На 17 из них есть лес, на 26 – река, а на 13 – и то, и другое, на остальных картинах – не пойми что. Сколько картин изображают не пойми что?

11.

На олимпийских играх наши спортсмены завоевали 96 медалей, из них 65 золотых и бронзовых, а золотых и серебряных 61. Сколько было золотых, серебряных и бронзовых медалей в отдельности?

12.

На дискотеке 80% времени был выключен свет, 90% времени играла музыка и 50% времени шел дождь. Какую наименьшую долю времени все это обязано было происходить одновременно?