Практика
В комнате \(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\). Противоречие. Значит две тройки имеют не менее двух общих элементов.