Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

2 Задача усложнится, если нужно найти число людей с большим количеством свойств. Допустим, нас интересует не только английский язык, но и еще пять других. В таком случае придется выполнить много вычислений. В математике для этого применяют принцип включения и исключения.

3 В этом уроке разберемся, как работает принцип включения и исключения, а также докажем его. С помощью этих знаний вы научитесь подсчитывать элементы, которые входят в два множества.

4 <h2>Принцип включения и исключения</h2>

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

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

7 Получается следующее решение:

8 5 + 8 - 3 = 10 - число людей, у которых есть хотя бы одна кошка или одна собака

9 PIE полезен в комбинаторике и теории вероятности, так как гарантирует, что объект не посчитается дважды.

10 Мы разобрали, как найти количество определенных элементов из одного множества. Также бывают задачи, когда объекты разделяются на два множества.

11 <h2>Как это работает на практике</h2>

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

13 Когда объекты разделяются на два множества, принцип включения и исключения гласит:

14 |AcupB|=|A|+|B|-|AcapB|

15 В этом случае |A||B| обозначаеткардинальностьилимощность- то есть количество элементов множества AB в нотации множеств.

16 Докажем это утверждение.

17 <h3>Как доказать принцип включения и исключения</h3>

18 Для начала нужно показать, как учитывать элементы:

19 <ul><li>Если элемент входит в одно из двух множеств, он учитывается один раз</li>

20 <li>Если элемент не входит в эти множества, он учитывается ноль раз</li>

21 </ul>Рассмотрим четыре случая:

22 <ol><li>Элемента нет ни в A, ни в B</li>

23 <li>Элемент находится в A, но не в B</li>

24 <li>Элемент находится в B, но не в A</li>

25 <li>Элемент находится в A и в B Вот так PIE для двух множеств выглядит в виде диаграммы Венна:</li>

26 </ol>Рассмотрим доказательство на примере. Допустим, нам нужно узнать ответ на вопрос:

27 Сколько целых чисел от 1 до 100 кратны 2 или 3?

28 Далее зададим такие условия:

29 <ul><li>Пусть A - множество целых чисел от 1 до 100, кратных 2, тогда |A|=50</li>

30 <li>Пусть B - множество целых чисел от 1 до 100, кратных 3, тогда |B|=33</li>

31 </ul>Затем найдем элементы, которые входят в оба множества:

32 <ul><li>A cap B - это множество целых чисел от 1 до 100, которые кратны 2 и 3</li>

33 <li>Делаем вывод, что целые числа из множества A cap B кратны 6</li>

34 <li>Следовательно, |A cap B|=16 - количество элементов, которые кратны 2 и 3</li>

35 <li>Далее перечислим эти 16 чисел: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60,66,72,78,84,90,96</li>

36 </ul>В итоге мы получаем такую формулировку по PIE:

37 |A cup B| = |A|+|B|-|Acap B| = 50 + 33 - 16 = 67 чисел от 1 до 100 кратны 2 или 3

38 <h2>Выводы</h2>

39 В этом уроке мы познакомились с принципом включения и исключения, а также разобрали, как посчитать элементы, которые входят в одно и два множества.

40 PIE помогает из множества объектов выбрать те, которые обладают определенным свойством. При этом, он не учитывает их дважды. Поэтому решать такие задачи с помощью принципа включения и исключения проще и безопаснее.