Глава
Теория
Метод двойного подсчёта состоит в том, что мы считаем один и тот же набор объектов двумя разными способами. Результатом может быть равенство, тождество, среднее значение или доказательство существования объекта с нужным свойством.
Чаще всего считаются пары: \((ученик, кружок)\), \((вершина, ребро)\), \((подмножество, элемент)\), \((точка, прямая)\). Если правильно выбрать, какие пары считать, задача часто становится короткой.
Ищите фразы “каждый объект связан с”, “в каждой группе”, “каждая пара”, “сколько всего участий”, “среднее число”. Они почти всегда подсказывают набор пар или инцидентностей.
Если видите сумму вида \(0C(n,0)+1C(n,1)+\cdots+nC(n,n)\), попробуйте считать пары “выбранное подмножество и отмеченный элемент в нём”.
Примеры
Каждое рукопожатие можно считать по двум участникам.
Задача. В комнате \(10\) человек, каждый пожал руку каждому. Сколько рукопожатий было?
Считаем пары людей: нужно выбрать \(2\) человека из \(10\), получаем \(45\). Иначе можно сказать: каждый человек дал \(9\) рукопожатий, всего \(90\) концов рукопожатий, каждое рукопожатие имеет два конца, значит \(90/2=45\).
Комментарий. Это первая версия суммы степеней.
Считаем пары “ученик — кружок”.
Задача. В школе \(30\) учеников, каждый ходит ровно в \(2\) кружка. Сколько всего ученических членств в кружках?
Каждый ученик даёт \(2\) пары \((ученик, кружок)\). Всего \(30\cdot2=60\) членств.
Комментарий. Если известны размеры кружков, их сумма тоже должна быть \(60\).
Если среднее большое, кто-то не меньше среднего.
Задача. В \(8\) кружках всего \(60\) членств. Докажите, что в некотором кружке не менее \(8\) учеников.
Если бы в каждом кружке было не более \(7\) учеников, всего было бы не более \(8\cdot7=56\) членств. Но их \(60\). Значит в некотором кружке хотя бы \(8\) учеников.
Комментарий. Это средний аргумент в форме противоречия.
Каждое ребро имеет два конца.
Задача. Докажите, что в любом графе сумма степеней всех вершин равна удвоенному числу рёбер.
Считаем пары \((v,e)\), где вершина \(v\) является концом ребра \(e\). Если считать по вершинам, получаем сумму степеней. Если считать по рёбрам, каждое ребро даёт \(2\) пары. Значит сумма степеней равна \(2E\).
Комментарий. Это главная лемма графового подсчёта.
Считаем подмножество и отмеченный элемент.
Задача. Докажите, что \(\sum_{k=0}^n kC(n,k)=n2^{n-1}\).
Считаем пары \((S,x)\), где \(S\) — подмножество \(n\)-элементного множества, а \(x\in S\). По размеру \(S=k\): получаем левую часть. По элементу \(x\): выбираем \(x\) \(n\) способами, а остальные элементы подмножества выбираются произвольно из \(n-1\), значит \(n2^{n-1}\).
Комментарий. Тождество стало задачей о парах.
Каждый элемент может быть вне обоих множеств, только в большем или в обоих.
Задача. Сколько пар \((A,B)\) подмножеств множества из \(n\) элементов удовлетворяют \(A\subset B\)?
Для каждого элемента есть три варианта: не входит в \(B\), входит в \(B\), но не в \(A\), входит в \(A\) и \(B\). Значит пар \(3^n\).
Комментарий. Это тоже двойной взгляд: по элементам вместо по множествам.
Одна и та же таблица “точка лежит на прямой” считается по строкам или столбцам.
Задача. Есть \(9\) прямых, на каждой отмечено \(5\) точек. Каждая отмеченная точка лежит ровно на \(3\) прямых. Сколько отмеченных точек?
Считаем инцидентности \((точка, прямая)\). По прямым их \(9\cdot5=45\). По точкам их \(3N\), где \(N\) — число точек. Значит \(3N=45\), откуда \(N=15\).
Комментарий. Классическая задача на инцидентности.
Если каждая тройка содержит \(3\) пары, можно ограничить число троек.
Задача. Имеются трёхэлементные подмножества \(10\)-элементного множества, причём никакая пара элементов не встречается в двух разных подмножествах. Докажите, что таких подмножеств не больше \(15\).
Каждое трёхэлементное подмножество содержит \(3\) пары элементов. Всего пар элементов в \(10\)-элементном множестве \(45\). Так как пары не повторяются, \(3m\le45\), где \(m\) — число подмножеств. Значит \(m\le15\).
Комментарий. Это уже олимпиадная оценка двойным подсчётом.
Задачи
В комнате \(10\) человек, каждый пожал руку каждому. Сколько рукопожатий было?
Посчитайте пары людей.
Каждое рукопожатие соответствует паре людей. Пар \(10\cdot9/2=45\).
В классе \(20\) учеников, каждый посещает ровно \(2\) кружка. Сколько всего пар \((ученик, кружок)\)?
Каждый ученик даёт две пары.
Всего \(20\cdot2=40\) пар.
В таблице записаны числа. Объясните, почему сумма сумм по строкам равна сумме сумм по столбцам.
Каждая клетка учитывается ровно один раз в обоих подсчётах.
При суммировании по строкам каждое число таблицы учитывается один раз. При суммировании по столбцам тоже каждое число учитывается один раз. Значит результаты равны.
Есть \(12\) слов длины \(5\). Сколько всего пар \((слово, позиция)\)?
У каждого слова \(5\) позиций.
Каждое из \(12\) слов даёт \(5\) позиций. Всего \(12\cdot5=60\) пар.
Сколько рёбер у графа, в котором \(6\) вершин и каждая пара вершин соединена ребром?
Ребро — это пара вершин.
Нужно выбрать \(2\) вершины из \(6\): \(6\cdot5/2=15\).
Докажите, что в любом графе число вершин нечётной степени чётно.
Используйте сумму степеней.
Сумма степеней равна \(2E\), значит она чётна. Сумма степеней вершин чётной степени чётна, поэтому сумма степеней вершин нечётной степени тоже чётна. Сумма нечётного количества нечётных чисел была бы нечётной, значит таких вершин чётное число.
В \(8\) кружках суммарно \(60\) членств. Докажите, что есть кружок, в котором не менее \(8\) учеников.
Сравните со средним \(60/8\).
Среднее число учеников в кружке равно \(60/8=7.5\). Если бы во всех кружках было не более \(7\), всего было бы не более \(56\), противоречие. Значит в некотором кружке хотя бы \(8\).
Для множества из \(5\) элементов найдите сумму размеров всех его подмножеств.
Считайте пары \((S,x)\), где \(x\in S\).
Каждый из \(5\) элементов входит ровно в половину всех подмножеств, то есть в \(2^4=16\) подмножеств. Сумма размеров равна числу пар \((S,x)\), значит \(5\cdot16=80\).
Сколько пар \((S,x)\), где \(S\subset\{1,\ldots,6\}\) и \(x\in S\)?
Сначала выберите \(x\), затем остальные элементы \(S\).
Элемент \(x\) выбирается \(6\) способами. Для каждого \(x\) остальные \(5\) элементов либо входят в \(S\), либо нет: \(2^5\) способов. Всего \(6\cdot2^5=192\).
В полном графе на \(6\) вершинах сколько упорядоченных путей вида \(A-B-C\), где \(A,B,C\) различны?
Выберите среднюю вершину, затем два конца по порядку.
Среднюю вершину \(B\) выбираем \(6\) способами. Конец \(A\) — \(5\) способами, конец \(C\) — \(4\) способами. Всего \(6\cdot5\cdot4=120\).
Выведите формулу числа диагоналей \(n\)-угольника через подсчёт концов диагоналей.
Из каждой вершины выходит \(n-3\) диагоналей.
Из каждой из \(n\) вершин выходит \(n-3\) диагоналей, значит концов диагоналей \(n(n-3)\). Каждая диагональ имеет два конца, поэтому диагоналей \(n(n-3)/2\).
\(25\) учеников суммарно решили \(100\) задач. Докажите, что некоторый ученик решил не менее \(4\) задач.
Среднее равно \(4\).
Если бы каждый решил не более \(3\) задач, всего было бы не более \(25\cdot3=75\), что меньше \(100\). Значит кто-то решил не менее \(4\) задач.
Докажите комбинаторно, что \(\sum_{k=0}^n kC(n,k)=n2^{n-1}\).
Считайте пары \((S,x)\), где \(x\in S\).
По размеру \(S=k\): есть \(C(n,k)\) подмножеств и \(k\) способов выбрать отмеченный элемент, получаем левую часть. По отмеченному элементу: \(n\) вариантов для \(x\), остальные \(n-1\) элементов выбираются в \(S\) произвольно, \(2^{n-1}\) способов. Получаем правую часть.
Докажите, что \(C(2,2)+C(3,2)+\cdots+C(n,2)=C(n+1,3)\).
Считайте трёхэлементные подмножества по наибольшему элементу.
Выберем \(3\)-элементное подмножество из \(\{1,\ldots,n+1\}\). Если наибольший элемент равен \(t+1\), то остальные два выбираются из \(1,\ldots,t\), то есть \(C(t,2)\) способами. Сумма по \(t=2,\ldots,n\) даёт левую часть, а всего таких подмножеств \(C(n+1,3)\).
В школе \(40\) учеников и \(5\) кружков. Каждый ученик ходит ровно в \(2\) кружка. Докажите, что некоторый кружок имеет не менее \(16\) учеников.
Посчитайте общее число членств.
Всего членств \(40\cdot2=80\). Если бы в каждом кружке было не более \(15\) учеников, всего было бы не более \(5\cdot15=75\), противоречие. Значит некоторый кружок имеет не менее \(16\) учеников.
Сколько пар \((A,B)\) подмножеств \(n\)-элементного множества удовлетворяют \(A\subset B\)?
Для каждого элемента есть три состояния.
Каждый элемент либо не входит в \(B\), либо входит в \(B\), но не входит в \(A\), либо входит в оба множества. Три независимых состояния для каждого из \(n\) элементов дают \(3^n\) пар.
На плоскости отмечены \(12\) точек, никакие три не лежат на одной прямой. Сколько отрезков с концами в отмеченных точках можно провести?
Отрезок задаётся парой точек.
Нужно выбрать \(2\) точки из \(12\). Получаем \(12\cdot11/2=66\) отрезков.
В турнире каждый из \(n\) игроков сыграл с каждым ровно один раз, ничьих нет. Докажите, что есть игрок, выигравший не менее \((n-1)/2\) партий.
Посчитайте общее число побед.
Всего партий \(n(n-1)/2\), и каждая даёт ровно одну победу. Среднее число побед на игрока равно \((n(n-1)/2)/n=(n-1)/2\). Значит некоторый игрок имеет не меньше среднего.
Сколько прямоугольников в сетке \(5\) на \(6\) клеток?
Выберите две вертикальные и две горизонтальные линии.
В сетке \(5\) на \(6\) клеток есть \(6\) горизонтальных и \(7\) вертикальных линий. Прямоугольник задаётся выбором двух вертикальных и двух горизонтальных линий. Ответ \(C(7,2)C(6,2)=21\cdot15=315\).
Есть \(12\) комитетов, каждый состоит из \(5\) человек, всего участвуют \(20\) человек. Докажите, что некоторый человек входит не менее чем в \(3\) комитета.
Посчитайте пары \((человек, комитет)\).
Всего членств \(12\cdot5=60\). Среднее число комитетов на человека равно \(60/20=3\). Значит некоторый человек входит не менее чем в \(3\) комитета.
В группе \(15\) человек каждый знаком не менее чем с \(7\) другими. Докажите, что всего есть не менее \(53\) пар знакомых.
Сложите степени в графе знакомств.
Построим граф знакомств. Сумма степеней не меньше \(15\cdot7=105\). Каждая пара знакомых даёт два вклада в сумму степеней, значит число рёбер не меньше \(105/2=52.5\). Так как оно целое, оно не меньше \(53\).
Докажите комбинаторно, что \(\sum_{k=0}^n k^2C(n,k)=n(n+1)2^{n-2}\).
Считайте тройки \((S,x,y)\), где \(x,y\in S\), причём \(x\) и \(y\) могут совпадать.
По размеру \(S=k\) получаем \(k^2\) способов выбрать упорядоченную пару \((x,y)\), значит левая часть. Теперь считаем по \((x,y)\). Если \(x=y\), выбираем этот элемент \(n\) способами, остальные элементы \(S\) произвольны: \(2^{n-1}\). Если \(x e y\), выбираем упорядоченную пару \(n(n-1)\) способами, остальные \(n-2\) элементов произвольны: \(2^{n-2}\). Итого \(n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}\).
Есть \(9\) прямых, на каждой \(5\) отмеченных точек. Каждая отмеченная точка лежит ровно на \(3\) прямых. Найдите число отмеченных точек.
Считайте инцидентности \((точка, прямая)\).
По прямым инцидентностей \(9\cdot5=45\). Если точек \(N\), то по точкам инцидентностей \(3N\). Значит \(3N=45\), откуда \(N=15\).
Из \(10\)-элементного множества выбраны \(17\) трёхэлементных подмножеств. Докажите, что найдутся два выбранных подмножества, имеющие не менее двух общих элементов.
Докажите противное: если любые две тройки имеют не более одного общего элемента, то пары элементов не повторяются.
Предположим, что любые две выбранные тройки имеют не более одного общего элемента. Тогда никакая пара элементов не может входить в две разные тройки, иначе эти две тройки имели бы общую пару, то есть два общих элемента. Каждая тройка содержит \(3\) пары, поэтому \(17\) троек содержали бы \(51\) различную пару элементов. Но всего пар в \(10\)-элементном множестве \(10\cdot9/2=45\). Противоречие. Значит две тройки имеют не менее двух общих элементов.
Лестницы