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

Совершенно замечательная важная формула в комбинаторике, о которой мы, конечно,

много говорили на лекции.

Ну вот я предлагаю рассмотреть некоторые задачи, которые вам лучше, наверное,

проиллюстрируют суть этой формулы и помогут решать самостоятельно те задачи,

которые вам уже придётся делать без моего участия.

Ну вот совсем простенькая постановка вопроса.

Первое утверждение, которое сейчас мы сделаем, я в его справедливости совершенно

не уверен, честно говоря, но, может быть, оно и правильное на самом деле.

Я так вот не берусь навскидку сказать.

Утверждается так: в России 1112 городов.

[ПИШЕТ НА ДОСКЕ] Ну по порядку точно верно.

Вот прям вот точную цифру, точное число,

— я не готов за него поручиться, — 1112 городов.

Но, наверное, оно правильное.

Так. И есть два великих путешественника: одного

зовут Алексей, другого зовут Даниил.

Значит, про этих великих путешественников известно,

что Алексей посетил половину

из этих городов, какую-то.

Но и Даниил от него не отстал, посетив с ним не ту же самую,

а тоже половину, но не ту же самую, вообще говоря, тоже половину городов России.

Так, давайте здесь напишем Даниил, а дальше вот так вот,

но я подчёркиваю: конечно, та половина городов, которую посетил Алексей,

вовсе не обязана совпадать с той половиной городов, которую посетил Даниил.

Более того, известно, что оба они одновременно,

оба они

побывали в

четверти от числа этих городов.

В четверти этих городов.

То есть среди той половины городов,

которую посетил Алексей, в свою очередь половину —

четверть от общего числа городов России — посетил Даниил.

Ну и естественно наоборот.

То есть у них такое достаточно жирное пересечение по посещаемости, по посещению.

Вот.

Но есть и некоторые разности, довольно тоже существенные.

Есть города, которые посетил Даниил и не посетил Алексей и есть города,

которые посетил Алексей и не посетил Даниил.

Вот, спрашивается: а сколько же городов России не посетил ни один из них?

Сколько городов

не посетил ни один из них?

[ПИШЕТ НА ДОСКЕ] Ну даже по постановке вопроса,

в общем-то, я думаю, что слушатель должен, решатель должен угадать,

что здесь речь идёт о какой-то формуле включения-исключения,

потому что не посетил ни один из них — это вот какое-то такое двойное отрицание,

которое типично для задач, если вы помните лекции,

для задач о формуле включения-исключения, на формулу включения-исключения.

Ну давайте формальную базу подведём так, чтобы это было похоже на то,

о чём говорилось на лекциях.

То есть скажем, о каких объектах идёт речь и о каких их свойствах.

Ну смотрите, объекты — это, конечно, города России.

Объекты — это, конечно, города России и N,

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

То есть количество объектов, с которыми мы имеем дело, — это и есть 1112.

У нас всего 1112 объектов, каждый из которых может

обладать или же не обладать некоторым свойством.

Так, ну я уж не буду, наверное, их никак обозначать,

хотя на лекции они обозначались a с индексом 1, a с индексом 2.

a с индексом N.

Это вот и были те самые города,

которые могли посещать или не посещать наши великие путешественники.

Ну вот N мне точно пригодится.

Зато, если вы помните, свойства,

которыми обладают или же не обладают наши объекты, свойства.

Давайте я напишу слово «свойства», мы обозначали греческими буквами α1,

α2, ..., α с индексом n.

Ну здесь, по счастью, n = 2 всего лишь.

Задачка-то простенькая.

Свойств очень мало.

А именно: есть свойства α1, которым может обладать или не обладать город.

И свойства α1 состоит в том, что данный конкретный город

посещал великий путешественник Алексей.

А свойство α2 состоит в том, что данный конкретный город

посещал великий путешественник Даниил.

Вот всего два свойства на самом деле.

И каждый город может либо обладать свойством α1, либо не обладать им.

И то же самое касается свойства α2.

Он может одновременно обладать этими двумя свойствами.

Это в случае когда и Алексей, и Даниил побывали в данном городе.

Ну а может не обладать ни одним из них.

Это когда город оказался лишён такого счастья лицезреть

какого-либо из этих великих путешественников.

Вот. Ну если вспомнить обозначения с лекции,

то там у нас было N(α1) — это количество, собственно,

объектов, которые обладают свойством α1.

То есть в данном случае это количество городов, которые посещал Алексей.

Ну мы знаем это количество — это 1112 пополам.

Ну можно сосчитать.

Это 556 получается, правильно?

Ну бог с ним.

И то же самое касается величины N(α2), то есть числа городов, которые были посещены,

когда-либо Даниилом — 1112 пополам.

И, коль скоро свойств всего два, последнее, что нам нужно

для применения формулы включения исключений, это величина N(α1, α2).

На лекции я произносил слово «полиглот».

Ну нелепо говорить про город, что он полиглот,

если его посетило сразу два великих путешественника.

Ну это просто очень счастливый город — это город, в котором побывали и Алексей,

и Даниил.

Вот. Ну таких городов мы знаем,

таких городов 1112 поделить на 4.

Ну то есть 278 (556 / 2 = 278).

А нас с вами в аккурат интересует величина N(α1',

α2') — это количество городов несчастных.

Несчастных в том смысле,

что в этих городах не появлялись ни Алексей ни Даниил.

Но по формуле включения исключения они, видите, не обладают ни свойством

α1 ни свойством α2, значит ни одного из великих путешественников там не было,

а ровно это количество с точки зрения нашей задачи нас и интересует.

Так вот по формуле включения исключений это есть N −

N(α1) − N(α2) + N(α1,

α2) и ничего больше, потому что свойств всего две штуки.

Ну мы все эти величины знаем.

У нас получается 1112 − 1112

пополам − 1112 / 2 + 1112 / 4.

Шлёп, шлёп, шлёп...

= 278.

Ну в общем-то это можно было, конечно, ответить и сразу, но вот для тех, кому это

не было очевидно, я подробно расписал с помощью формулы включения-исключения.

Ну видите, несмотря на величие великих путешественников,

довольно много городов осталось непосещённых.

Надо добавить кого-нибудь третьего.

В следующей задаче, я думаю, кто-нибудь третий.

Ну в следующей, не в следующей,

но в какой-нибудь будущей задаче кто-нибудь третий да появится.

Путешественники

Комбинаторика для начинающих

Meet the Instructors