bulgakov

31. Включения и исключения через свойства

Принцип включений и исключений часто применяют так: нужно посчитать объекты, у которых нет ни одного из заданных «нежелательных» свойств. Для каждого набора из kk свойств считаем объекты, обладающие сразу всеми свойствами набора, и складываем эти числа по всем наборам — получаем число w(k)w(k). Тогда ответ равен w(0)−w(1)+w(2)−w(3)+⋯+(−1)nw(n)w(0)-w(1)+w(2)-w(3)+\dots+(-1)^nw(n).

Что пригодится из прошлого: формула для nn множеств — это та же формула на другом языке; следствия бинома — знакопеременная сумма ∑(−1)k(tk)=0\sum(-1)^k\dbinom tk=0; включения и исключения для трёх множеств. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Язык свойств

Пусть S={s1,s2,…,sN}S=\{s_1,s_2,\dots,s_N\} — множество объектов, а P={p1,p2,…,pn}P=\{p_1,p_2,\dots,p_n\} — набор свойств, которыми объекты могут обладать (или не обладать). Примеры: объекты — числа от 11 до 100100, свойство p1p_1 — «делится на 22», p2p_2 — «делится на 33», p3p_3 — «делится на 55».

Введём обозначения:

  • w(pi)w(p_i) — число объектов, обладающих свойством pip_i (1≤i≤n1\le i\le n);
  • w(pi1,pi2)w(p_{i_1},p_{i_2}) — число объектов, обладающих обоими свойствами pi1p_{i_1} и pi2p_{i_2} (1≤i1<i2≤n1\le i_1<i_2\le n);
  • w(pi1,…,pik)w(p_{i_1},\dots,p_{i_k}) — число объектов, обладающих всеми этими kk свойствами;
  • w(p1,…,pn)w(p_1,\dots,p_n) — число объектов, обладающих всеми nn свойствами.

Теперь соберём одинаковые по размеру наборы:

w(0)=∣S∣=N,w(1)=∑i=1nw(pi),w(2)=∑1≤i1<i2≤nw(pi1,pi2),  …w(0)=|S|=N,\qquad w(1)=\sum_{i=1}^{n}w(p_i),\qquad w(2)=\sum_{1\le i_1<i_2\le n}w(p_{i_1},p_{i_2}),\ \ \dots w(k)=∑1≤i1<⋯<ik≤nw(pi1,…,pik),w(n)=w(p1,…,pn).w(k)=\sum_{1\le i_1<\dots<i_k\le n}w(p_{i_1},\dots,p_{i_k}),\qquad w(n)=w(p_1,\dots,p_n).

Теорема (принцип включений и исключений). Если E(0)E(0) — число объектов множества SS, не обладающих ни одним из свойств PP, то

E(0)=w(0)−w(1)+w(2)−w(3)+⋯+(−1)nw(n).\boxed{E(0)=w(0)-w(1)+w(2)-w(3)+\cdots+(-1)^nw(n)}.

Здесь E(0)E(0) — число объектов, у которых ровно 00 свойств (буква EE — от английского exactly, «ровно»). Обратите внимание на два смысла буквы ww: w(pi1,…,pik)w(p_{i_1},\dots,p_{i_k}) — число объектов (в скобках перечислены свойства), а w(k)w(k) с целым номером — сумма таких чисел по всем наборам из kk свойств.

Связь с прошлой главой. Пусть SiS_i — объекты со свойством pip_i. Тогда w(pi1,…,pik)=∣Si1∩⋯∩Sik∣w(p_{i_1},\dots,p_{i_k})=|S_{i_1}\cap\dots\cap S_{i_k}|, а w(k)w(k) — сумма размеров пересечений по всем наборам из kk множеств. Объекты без ни одного свойства — S1‾∩⋯∩Sn‾\overline{S_1}\cap\dots\cap\overline{S_n}, их ∣S∣−∣S1∪⋯∪Sn∣|S|-|S_1\cup\dots\cup S_n|. Подставим формулу для объединения:

∣S∣−∣S1∪⋯∪Sn∣=w(0)−(w(1)−w(2)+w(3)−⋯ )=w(0)−w(1)+w(2)−w(3)+⋯\begin{aligned} |S|-|S_1\cup\dots\cup S_n|&=w(0)-\bigl(w(1)-w(2)+w(3)-\cdots\bigr)\\ &=w(0)-w(1)+w(2)-w(3)+\cdots \end{aligned}

Это то же утверждение, только в более удобной записи.

Что такое w(k)w(k): сколько раз учитывается объект

Число w(1)w(1) — это не число объектов «с одним свойством». Объект, у которого tt свойств, участвует в w(1)w(1) ровно tt раз (по разу на каждое своё свойство). В w(2)w(2) он участвует (t2)\dbinom t2 раз — по разу на каждую пару своих свойств, в w(k)w(k) — (tk)\dbinom tk раз.

Вернёмся к классу из прошлой главы: математику любят 1818, физику 1414, химию 1010 человек и так далее; восстановленная карта областей показала 33 человека без любимых предметов, 1414 с ровно одним, 1111 с ровно двумя, 22 с тремя. Подсчитаем, сколько раз учтён каждый:

Каждый человек, у которого ровно tt свойств (любимых предметов), входит в w(k)w(k) ровно (tk)\dbinom tk раз (это первый множитель в каждом произведении ниже):

  • t=0t=0: 3 чел.; учтены в w(0)w(0) — 1 · 3 = 3, в w(1)w(1) — 0 · 3 = 0, в w(2)w(2) — 0 · 3 = 0, в w(3)w(3) — 0 · 3 = 0
  • t=1t=1: 14 чел.; учтены в w(0)w(0) — 1 · 14 = 14, в w(1)w(1) — 1 · 14 = 14, в w(2)w(2) — 0 · 14 = 0, в w(3)w(3) — 0 · 14 = 0
  • t=2t=2: 11 чел.; учтены в w(0)w(0) — 1 · 11 = 11, в w(1)w(1) — 2 · 11 = 22, в w(2)w(2) — 1 · 11 = 11, в w(3)w(3) — 0 · 11 = 0
  • t=3t=3: 2 чел.; учтены в w(0)w(0) — 1 · 2 = 2, в w(1)w(1) — 3 · 2 = 6, в w(2)w(2) — 3 · 2 = 6, в w(3)w(3) — 1 · 2 = 2

Получаем w(0)=30w(0)=30, w(1)=42w(1)=42, w(2)=17w(2)=17, w(3)=2w(3)=2. Тогда

E(0)=30−42+17−2=3,E(0)=30-42+17-2=3,

то есть три человека не любят ни одного предмета. Совпало с прошлым ответом.

Доказательство

Докажем теорему индукцией по числу объектов ∣S∣|S|.

База. Если S=∅S=\varnothing, то E(0)=0E(0)=0 и все w(k)=0w(k)=0: равенство верно.

Шаг. Любое конечное множество получается из пустого добавлением объектов по одному, поэтому достаточно проверить шаг. Допустим, равенство верно для множества SS. Добавим новый объект a∉Sa\notin S и проверим, что обе части равенства изменятся на одно и то же число. Пусть объект aa обладает tt свойствами из PP.

  • t=0t=0, то есть aa не обладает ни одним свойством. Тогда E(0)E(0) увеличивается на 11. Правая часть: w(0)=∣S∣w(0)=|S| тоже увеличивается на 11; остальные w(k)w(k) не меняются, ведь у aa нет ни одного свойства. Обе части выросли на 11.
  • t>0t>0. Объект aa обладает свойством, поэтому E(0)E(0) не меняется. А w(k)w(k) увеличивается на число наборов из kk свойств, которыми aa обладает: на (tk)\dbinom tk при k≤tk\le t и на 00 при k>tk>t. Правая часть меняется на
(t0)−(t1)+(t2)−(t3)+⋯+(−1)t(tt)=∑k=0t(−1)k(tk)=0\binom t0-\binom t1+\binom t2-\binom t3+\cdots+(-1)^t\binom tt=\sum_{k=0}^{t}(-1)^k\binom tk=0

(это (1−1)t=0(1-1)^t=0 по формуле бинома, см. следствия бинома; здесь t≥1t\ge1). Правая часть не изменилась — как и левая.

Значит, равенство сохраняется при добавлении любого объекта. □\square

Как решать задачи

  1. Определите объекты SS и «нежелательные» свойства p1,…,pnp_1,\dots,p_n.
  2. Найдите w(k)w(k): сколько объектов обладает заранее выбранными kk свойствами (если для всех наборов получилось одно и то же число, умножьте его на число наборов (nk)\dbinom nk).
  3. Подставьте в E(0)=w(0)−w(1)+w(2)−…E(0)=w(0)-w(1)+w(2)-\dots

Пример. Числа, не делящиеся на 22, 33 и 55. Сколько чисел от 11 до 100100 не делятся ни на 22, ни на 33, ни на 55? Свойства p1,p2,p3p_1,p_2,p_3 — «делится на 22», «на 33», «на 55».

Напомним: ⌊x⌋\lfloor x\rfloor — целая часть числа xx, то есть наибольшее целое число, не превосходящее xx. Среди чисел от 11 до 100100 ровно ⌊100/2⌋=50\lfloor100/2\rfloor=50 кратны 22.

  • w(0)=100w(0)=100.
  • w(1)=⌊1002⌋+⌊1003⌋+⌊1005⌋=50+33+20=103w(1)=\bigl\lfloor\tfrac{100}{2}\bigr\rfloor+\bigl\lfloor\tfrac{100}{3}\bigr\rfloor+\bigl\lfloor\tfrac{100}{5}\bigr\rfloor=50+33+20=103.
  • w(2)=⌊1006⌋+⌊10010⌋+⌊10015⌋=16+10+6=32w(2)=\bigl\lfloor\tfrac{100}{6}\bigr\rfloor+\bigl\lfloor\tfrac{100}{10}\bigr\rfloor+\bigl\lfloor\tfrac{100}{15}\bigr\rfloor=16+10+6=32 (число делится на 22 и 33 тогда и только тогда, когда делится на 66; для 22 и 55 — на 1010; для 33 и 55 — на 1515).
  • w(3)=⌊10030⌋=3w(3)=\bigl\lfloor\tfrac{100}{30}\bigr\rfloor=3.

Тогда E(0)=100−103+32−3=26E(0)=100-103+32-3=26. Вот эти числа: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97.

Частые ошибки

  • Считать w(1)w(1) числом объектов ровно с одним свойством. Объект с tt свойствами учтён в w(1)w(1) ровно tt раз.
  • Обрывать сумму. После w(1)w(1) нужно продолжать: +w(2)−w(3)…+w(2)-w(3)\dots до w(n)w(n).
  • Потерять знаки. Знак перед w(k)w(k) равен (−1)k(-1)^k.
  • Считать число кратных нескольким числам сразу по одному. Для делимости на несколько простых чисел делят на их произведение: ⌊N/(p1p2)⌋\lfloor N/(p_1p_2)\rfloor, а не ⌊N/p1⌋⋅⌊N/p2⌋\lfloor N/p_1\rfloor\cdot\lfloor N/p_2\rfloor.

Проверь себя

1. Сколько чисел от 11 до 6060 не делятся ни на 22, ни на 33, ни на 55?

Решение

w(0)=60w(0)=60; w(1)=30+20+12=62w(1)=30+20+12=62; w(2)=⌊60/6⌋+⌊60/10⌋+⌊60/15⌋=10+6+4=20w(2)=\lfloor60/6\rfloor+\lfloor60/10\rfloor+\lfloor60/15\rfloor=10+6+4=20; w(3)=⌊60/30⌋=2w(3)=\lfloor60/30\rfloor=2. E(0)=60−62+20−2=16E(0)=60-62+20-2=16.

2. Сколько чисел от 11 до 10001000 не делятся ни на 22, ни на 55?

Решение

w(0)=1000w(0)=1000, w(1)=500+200=700w(1)=500+200=700, w(2)=⌊1000/10⌋=100w(2)=\lfloor1000/10\rfloor=100. E(0)=1000−700+100=400E(0)=1000-700+100=400.

3. Известно: w(0)=50w(0)=50, w(1)=60w(1)=60, w(2)=25w(2)=25, w(3)=5w(3)=5. Сколько объектов не обладают ни одним из трёх свойств?

Решение

E(0)=50−60+25−5=10E(0)=50-60+25-5=10.

4. Объект обладает 44 свойствами из n=6n=6. В скольких слагаемых w(2)w(2) он участвует?

Решение

В каждой паре из его 44 свойств: (42)=6\dbinom42=6 раз.

Итог

  • Свойства p1,…,pnp_1,\dots,p_n; w(k)w(k) — сумма по всем наборам из kk свойств числа объектов, обладающих сразу всеми свойствами набора; w(0)=∣S∣w(0)=|S|.
  • E(0)=w(0)−w(1)+w(2)−⋯+(−1)nw(n)E(0)=w(0)-w(1)+w(2)-\dots+(-1)^nw(n) — число объектов без единого свойства.
  • Доказательство: добавление объекта с tt свойствами меняет правую часть на ∑k(−1)k(tk)=0\sum_{k}(-1)^k\dbinom tk=0 (для t≥1t\ge1).
  • Объект с tt свойствами учтён в w(k)w(k) ровно (tk)\dbinom tk раз.
ПрактикаЗагружаем тест…