Дискретна математика и теория на графите - трудни задачи с решения

Решение:
За всяко [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]3[/tex] в [tex]G[/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] души.