Дискретная математика и теория графов - сложные задачи с решениями

Решение:
Для всех [tex]n\ge 0[/tex] имеем [tex]\binom{n}{3}=\frac{n(n-1)(n-2)}{6}[/tex] (при [tex]n=0; 1; 2[/tex] обе части равны [tex]0[/tex]), поэтому
[tex]f(n)=q(n)\,(-1)^n,\qquad q(n)=\frac{n(n-1)(n-2)}{6}[/tex]
где [tex]q[/tex] — многочлен степени [tex]3[/tex]. Общее решение рекуррентного соотношения с характеристическим многочленом [tex](x+1)^4[/tex] имеет вид [tex](C_1+C_2n+C_3n^2+C_4n^3)(-1)^n[/tex], так как [tex]-1[/tex] — корень кратности [tex]4[/tex]. Следовательно, [tex]f[/tex] удовлетворяет соотношению порядка [tex]4[/tex] с характеристическим многочленом
[tex](x+1)^4=x^4+4x^3+6x^2+4x+1[/tex]
т.е. соотношению
[tex]f(n)=-4f(n-1)-6f(n-2)-4f(n-3)-f(n-4)[/tex]
Такого соотношения порядка [tex]k\le 3[/tex] не существует: при [tex]n=3[/tex] его правая часть — линейная комбинация некоторых из значений [tex]f(0)[/tex], [tex]f(1)[/tex], [tex]f(2)[/tex], равных [tex]0[/tex], а [tex]f(3)=-1\ne 0[/tex]. Значит, наименьший возможный порядок равен [tex]4[/tex]. Проверка при [tex]f(3)=-1[/tex], [tex]f(4)=4[/tex], [tex]f(5)=-10[/tex]:
[tex]f(4)=-4f(3)=-4\cdot (-1)=4; \qquad f(5)=-4f(4)-6f(3)=-16+6=-10[/tex]

Решение:
Разделим рекуррентное соотношение на [tex](n+1)![/tex] и положим [tex]b_n=\frac{a_n}{n!}[/tex]. Тогда [tex]b_1=0[/tex] и
[tex]b_{n+1}-b_n=\frac{(-1)^{n+1}}{(n+1)!},\quad n\ge 1[/tex]
Складывая эти равенства для индексов от [tex]1[/tex] до [tex]n-1[/tex] (сумма слева телескопическая), получаем
[tex]b_n=b_1+\sum_{k=2}^{n}\frac{(-1)^k}{k!}=\sum_{k=0}^{n}\frac{(-1)^k}{k!}[/tex]
так как слагаемые при [tex]k=0[/tex] и [tex]k=1[/tex] дают [tex]1-1=0=b_1[/tex] (при [tex]n=1[/tex] сумма от [tex]k=2[/tex] пустая). Умножая на [tex]n![/tex], получаем [tex]a_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}[/tex].
Проверка: из рекуррентного соотношения [tex]a_2=1[/tex], [tex]a_3=2[/tex], [tex]a_4=9[/tex], а по формуле
[tex]2!\left(1-1+\frac{1}{2}\right)=1; \quad 3!\left(\frac{1}{2}-\frac{1}{6}\right)=2; \quad 4!\left(\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=9[/tex]

Решение:
Обозначим расстояние Хэмминга через [tex]d[/tex]. Векторы [tex]\alpha[/tex] и [tex]\beta[/tex] различаются в позициях [tex]1[/tex], [tex]3[/tex], [tex]6[/tex], [tex]7[/tex] и совпадают в позициях [tex]2[/tex], [tex]4[/tex], [tex]5[/tex], т.е. [tex]d(\alpha,\beta)=4[/tex].
В позиции, где [tex]\alpha[/tex] и [tex]\beta[/tex] совпадают, [tex]\gamma[/tex] добавляет одно и то же число ([tex]0[/tex] или [tex]1[/tex]) к [tex]d(\gamma,\alpha)[/tex] и к [tex]d(\gamma,\beta)[/tex]. Поэтому эти [tex]3[/tex] позиции не влияют на равенство, и в них [tex]\gamma[/tex] произволен: [tex]2^3=8[/tex] вариантов.
В каждой из [tex]4[/tex] позиций, где они различаются, [tex]\gamma[/tex] совпадает ровно с одним из векторов [tex]\alpha[/tex] и [tex]\beta[/tex], поэтому добавляет [tex]1[/tex] ровно к одному из двух расстояний. Следовательно, [tex]d(\gamma,\alpha)=d(\gamma,\beta)[/tex] тогда и только тогда, когда [tex]\gamma[/tex] совпадает с [tex]\alpha[/tex] ровно в [tex]2[/tex] из этих [tex]4[/tex] позиций (а с [tex]\beta[/tex] — в остальных [tex]2[/tex]): [tex]\binom{4}{2}=6[/tex] вариантов.
По правилу произведения число искомых векторов равно
[tex]\binom{4}{2}\cdot 2^3=6\cdot 8=48[/tex]

Решение:
Пусть [tex]G[/tex] — такой граф, и предположим, что некоторая вершина [tex]v[/tex] имеет в [tex]G[/tex] степень не менее [tex]3[/tex]; пусть [tex]a,b,c[/tex] — три её соседа. Если две из них смежны в [tex]G[/tex], то они вместе с [tex]v[/tex] образуют треугольник в [tex]G[/tex]; иначе [tex]a,b,c[/tex] образуют треугольник в [tex]\overline{G}[/tex]. Значит, каждая степень в [tex]G[/tex] не больше [tex]2[/tex].
Условие симметрично относительно [tex]G[/tex] и [tex]\overline{G}[/tex], поэтому и каждая степень в [tex]\overline{G}[/tex] не больше [tex]2[/tex]. У каждой вершины [tex]4[/tex] возможных соседа, следовательно,
[tex]d_G(v)=4-d_{\overline{G}}(v)\ge 4-2=2[/tex]
Итак, каждая степень в [tex]G[/tex] равна [tex]2[/tex], т.е. [tex]G[/tex] — объединение непересекающихся циклов, каждый длины не менее [tex]3[/tex], всего с [tex]5[/tex] вершинами. Так как [tex]5[/tex] не является суммой двух или более чисел [tex]\ge 3[/tex], граф [tex]G[/tex] — один цикл длины [tex]5[/tex].
Обратно, цикл длины [tex]5[/tex] не содержит треугольника, а его дополнение — снова цикл длины [tex]5[/tex] (каждая вершина соединяется с двумя не соседними с ней вершинами, получается пентаграмма), поэтому и оно не содержит треугольника.
Осталось подсчитать циклы длины [tex]5[/tex] на [tex]5[/tex] помеченных вершинах. Каждое из [tex]5![/tex] упорядочений вершин задаёт цикл, причём каждый цикл получается [tex]5\cdot 2[/tex] раз ([tex]5[/tex] начальных вершин и [tex]2[/tex] направления):
[tex]\frac{5!}{5\cdot 2}=\frac{120}{10}=12[/tex]

Решение:
Пусть [tex]n=|V|[/tex]. Сначала покажем, что [tex]|E|\lt 3n[/tex]. При [tex]n\le 2[/tex] это ясно, так как [tex]|E|\le 1[/tex]. Пусть [tex]n\ge 3[/tex]. Добавление ребра между двумя компонентами плоской укладки сохраняет планарность и только увеличивает [tex]|E|[/tex], поэтому можно считать граф [tex]G[/tex] связным. Тогда граничный обход каждой грани имеет длину не менее [tex]3[/tex], а каждое ребро учитывается в этих обходах не более двух раз. Вместе с формулой Эйлера [tex]n-|E|+F=2[/tex], где [tex]F[/tex] — число граней, это даёт
[tex]3F\le 2|E|\ \Rightarrow\ 3(2-n+|E|)\le 2|E|\ \Rightarrow\ |E|\le 3n-6\lt 3n[/tex]
По лемме о рукопожатиях
[tex]\sum_{v\in V}d(v)=2|E|\lt 6n[/tex]
Пусть [tex]D=\frac{600}{100-p}\gt 0[/tex] и [tex]q[/tex] — число вершин с [tex]d(v)\ge D[/tex]. Каждая из них вносит в сумму степеней не менее [tex]D[/tex], поэтому
[tex]qD\le\sum_{v\in V}d(v)\lt 6n\ \Rightarrow\ q\lt\frac{6n}{D}=\frac{6n(100-p)}{600}=\frac{(100-p)n}{100}[/tex]
Следовательно, число вершин степени меньше [tex]D[/tex] равно
[tex]n-q\gt n-\frac{(100-p)n}{100}=\frac{pn}{100}[/tex]
т.е. больше [tex]p\%[/tex] всех вершин. Утверждение доказано.

Решение:
Никто не пожимает руку себе и своему супругу, поэтому каждый ответ — одно из чисел от [tex]0[/tex] до [tex]8[/tex]. Девять ответов различны, значит, это ровно
[tex]0,1,2,\ldots,8[/tex]
Назовём человека, ответившего [tex]j[/tex], «человеком [tex]j[/tex]». Человек [tex]8[/tex] пожал руки всем, кроме своего супруга. Человек [tex]0[/tex] никому не пожимал руку, в частности человеку [tex]8[/tex], поэтому человек [tex]0[/tex] — супруг человека [tex]8[/tex]. Обоих спрашивали, поэтому никто из них не госпожа Иванова; а человек [tex]8[/tex] не господин Иванов, так как его супругу, госпожу Иванову, не спрашивали. Значит, люди [tex]8[/tex] и [tex]0[/tex] — одна из приглашённых пар.
Удалим эту пару. Каждый из оставшихся пожал руку человеку [tex]8[/tex] и не пожимал руку человеку [tex]0[/tex], поэтому каждое из оставшихся чисел уменьшается ровно на [tex]1[/tex]. Получаем ту же ситуацию с [tex]3[/tex] приглашёнными парами: у семи опрошенных теперь различные числа [tex]0,1,\ldots,6[/tex].
Повторяя рассуждение, получаем, что люди [tex]7[/tex] и [tex]1[/tex], затем [tex]6[/tex] и [tex]2[/tex], затем [tex]5[/tex] и [tex]3[/tex] — приглашённые пары, а последний опрошенный, человек [tex]4[/tex], — господин Иванов. На каждом шаге человек с наибольшим числом пожал руки всем присутствующим, кроме своего супруга, в частности госпоже Ивановой, а человек с числом [tex]0[/tex] ей руку не пожимал. Своему мужу госпожа Иванова руку тоже не пожимала. Следовательно, она пожала руки ровно людям [tex]8[/tex], [tex]7[/tex], [tex]6[/tex] и [tex]5[/tex], т.е. [tex]4[/tex] людям.