Представим, что нам нужно из множества объектов выбрать те, которые обладают определенным свойством. Например, выбрать среди группы людей тех, кто знает английский язык. Для этого мы возьмем общее число людей и вычтем из него то количество, которое не говорит на английском.
Задача усложнится, если нужно найти число людей с большим количеством свойств. Допустим, нас интересует не только английский язык, но и еще пять других. В таком случае придется выполнить много вычислений. В математике для этого применяют принцип включения и исключения.
В этом уроке разберемся, как работает принцип включения и исключения, а также докажем его. С помощью этих знаний вы научитесь подсчитывать элементы, которые входят в два множества.
Принцип включения и исключения
Этот принцип применяется, когда нужно вычислить количество элементов, у которых есть хотя бы одно из нескольких свойств. При этом элементы, у которых есть более чем одно свойство, не учитываются дважды. Здесь происходит сложение и вычитание количества элементов, которые подходят хотя бы одной из двух категорий — поэтому двойной подсчет делать не нужно.
Представим, что нам нужно найти число людей, у которых есть хотя бы одна кошка или собака. Мы знаем, что у пяти человек есть кошка, а у восьми — собака. Также у трех из них есть и кошка, и собака.
Получается следующее решение:
— число людей, у которых есть хотя бы одна кошка или одна собака
PIE полезен в комбинаторике и теории вероятности, так как гарантирует, что объект не посчитается дважды.
Мы разобрали, как найти количество определенных элементов из одного множества. Также бывают задачи, когда объекты разделяются на два множества.
Как это работает на практике
Представим, что нам снова нужно найти людей, у которых есть хотя бы одна кошка или собака. Но теперь у нас есть две рассматриваемые группы — два множества.
Когда объекты разделяются на два множества, принцип включения и исключения гласит:
В этом случае обозначает кардинальность или мощность — то есть количество элементов множества в нотации множеств.
Докажем это утверждение.
Как доказать принцип включения и исключения
Для начала нужно показать, как учитывать элементы:
-
Если элемент входит в одно из двух множеств, он учитывается один раз
-
Если элемент не входит в эти множества, он учитывается ноль раз
Рассмотрим четыре случая:
-
Элемента нет ни в , ни в
-
Элемент находится в , но не в
-
Элемент находится в , но не в
-
Элемент находится в и в
Вот так PIE для двух множеств выглядит в виде диаграммы Венна:
Рассмотрим доказательство на примере. Допустим, нам нужно узнать ответ на вопрос:
Сколько целых чисел от до кратны или ?
Далее зададим такие условия:
-
Пусть — множество целых чисел от до , кратных , тогда
-
Пусть — множество целых чисел от до , кратных , тогда
Затем найдем элементы, которые входят в оба множества:
-
— это множество целых чисел от до , которые кратны и
-
Делаем вывод, что целые числа из множества кратны
-
Следовательно, — количество элементов, которые кратны и
-
Далее перечислим эти 16 чисел:
В итоге мы получаем такую формулировку по PIE:
чисел от до кратны или
Выводы
В этом уроке мы познакомились с принципом включения и исключения, а также разобрали, как посчитать элементы, которые входят в одно и два множества.
PIE помогает из множества объектов выбрать те, которые обладают определенным свойством. При этом, он не учитывает их дважды. Поэтому решать такие задачи с помощью принципа включения и исключения проще и безопаснее.
Самостоятельная работа
Задача №1
Представим группу учеников, которая сдала выпускные экзамены:
-
учеников сдали английский язык
-
— сдали математику
-
— успешно сдали оба предмета
-
учеников завалили два экзамена
Найдите общее число выпускников.
Нажмите, чтобы увидеть ответ
Для начала найдем, сколько учеников успешно сдали хотя бы один предмет.
Из условия:
-
успешно сдали оба предмета
Из этого следует, что:
-
сдали английский, но завалили математику
-
сдали математику, но завалили английский
Далее посчитаем, сколько учеников сдали хотя бы один экзамен. Для этого нужно сложить процент учеников, которые сдали оба экзамена или только математику или только английский:
-
сдали хотя бы один экзамен
Делаем такой вывод:
-
завалили два экзамена
-
В условии сказано, что это учеников
-
Значит, от общего числа кандидатов — это учеников
Делаем последний шаг:
-
выпускников сдавали экзамены
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
