Задачи по комбинаторика - много трудни задачи с решения

Решение:
Всяко естествено число се записва еднозначно във вида [tex]2^k m[/tex], където [tex]k\ge 0[/tex] е цяло число, а [tex]m[/tex] е нечетно; ще наричаме [tex]m[/tex] нечетна част на числото.
Нечетната част на число от [tex]\{1; 2; \ldots; 2n\}[/tex] не надминава самото число, следователно тя е едно от [tex]n[/tex]-те нечетни числа [tex]1, 3, 5, \ldots, 2n-1[/tex].
Избраните числа са [tex]n+1[/tex], а възможните нечетни части са само [tex]n[/tex], затова по принципа на Дирихле две от избраните числа, например [tex]a\lt b[/tex], имат една и съща нечетна част [tex]m[/tex]:
[tex]a=2^k m, \quad b=2^l m, \quad a\lt b\ \Rightarrow\ k\lt l\ \Rightarrow\ b=2^{l-k}\cdot a[/tex]
Следователно [tex]a[/tex] дели [tex]b[/tex], с което твърдението е доказано.

Решение:
Нека числата са [tex]a_1\lt a_2\lt \ldots\lt a_{102}[/tex], всички от множеството [tex]\{1; 2; \ldots; 200\}[/tex]. Разглеждаме [tex]101[/tex]-те числа
[tex]a_2-a_1, a_3-a_1, \ldots, a_{102}-a_1[/tex]
които са различни помежду си и са между [tex]1[/tex] и [tex]199[/tex], както и [tex]101[/tex]-те числа
[tex]a_2, a_3, \ldots, a_{102}[/tex]
които са различни помежду си и са между [tex]2[/tex] и [tex]200[/tex]. Общо това са [tex]202[/tex] числа от множество с едва [tex]200[/tex] елемента, затова по принципа на Дирихле две от тях са равни. Те не може да са от една и съща група, защото във всяка група числата са различни. Следователно за някои [tex]i, j\in\{2; 3; \ldots; 102\}[/tex] е изпълнено
[tex]a_i-a_1=a_j\ \Rightarrow\ a_1=a_i-a_j[/tex]
Тук [tex]i\ne j[/tex], защото от [tex]a_1\gt 0[/tex] следва [tex]a_i\gt a_j[/tex], а [tex]a_i[/tex] и [tex]a_j[/tex] са различни от [tex]a_1[/tex], защото [tex]i, j\ge 2[/tex]. Следователно най-малкото число [tex]a_1[/tex] е равно на разликата на две други от дадените числа.

Решение:
Записваме всяко такова число с точно пет цифри, като при нужда добавяме нули отпред: [tex]n=\overline{d_1d_2d_3d_4d_5}[/tex]. Това е взаимно еднозначно съответствие между числата [tex]0\le n\lt 10^5[/tex] и наредените петорки от цифри, а нулите отпред не променят сбора на цифрите. Следователно броим целите решения на
[tex]d_1+d_2+d_3+d_4+d_5=12,\qquad 0\le d_i\le 9[/tex]
Без горната граница [tex]d_i\le 9[/tex] броят на решенията в неотрицателни цели числа е (метод „звезди и черти“: [tex]12[/tex] звезди и [tex]4[/tex] черти)
[tex]\binom{16}{4}=1820[/tex]
Сега премахваме решенията, в които някоя цифра е поне [tex]10[/tex]. Две цифри не могат едновременно да са поне [tex]10[/tex], тъй като [tex]10+10\gt 12[/tex], затова тези случаи не се припокриват. Ако например [tex]d_1\ge 10[/tex], полагаме [tex]d_1=10+e_1[/tex], където [tex]e_1\ge 0[/tex]; тогава [tex]e_1+d_2+d_3+d_4+d_5=2[/tex], което има [tex]\binom{6}{4}=15[/tex] решения. Същото важи за всяка от [tex]5[/tex]-те позиции, така че броят на неподходящите решения е
[tex]5\cdot 15=75[/tex]
Следователно търсеният брой е
[tex]1820-75=1745[/tex]

Решение:
Броят на думите с точно [tex]k[/tex] букви [tex]a[/tex] е [tex]\binom{n}{k}3^{n-k}[/tex]: избираме [tex]k[/tex]-те позиции на буквата [tex]a[/tex], а на всяка от останалите [tex]n-k[/tex] позиции стои една от буквите [tex]b, c, d[/tex].
Нека [tex]E_n[/tex] и [tex]O_n[/tex] са съответно броят на думите с четен и с нечетен брой букви [tex]a[/tex]. От Нютоновия бином
[tex]E_n+O_n=\sum_{k=0}^{n}\binom{n}{k}3^{n-k}=(3+1)^n=4^n[/tex]
[tex]E_n-O_n=\sum_{k=0}^{n}\binom{n}{k}(-1)^k3^{n-k}=(3-1)^n=2^n[/tex]
Като извадим двете равенства, получаваме
[tex]2O_n=4^n-2^n\Rightarrow O_n=\frac{4^n-2^n}{2}[/tex]
Проверка: при [tex]n=1[/tex] получаваме [tex]1[/tex] (думата [tex]a[/tex]); при [tex]n=2[/tex] получаваме [tex]6[/tex] (думите [tex]ab, ac, ad, ba, ca, da[/tex]).

Решение:
Трябва да изберем [tex]5[/tex] от [tex]12[/tex] места в кръг така, че никои две избрани места да не са съседни.
Лема. От [tex]m[/tex] обекта, наредени в редица, могат да се изберат [tex]k[/tex] два по два несъседни обекта по [tex]\binom{m-k+1}{k}[/tex] начина. Наистина, неизбраните [tex]m-k[/tex] обекта образуват [tex]m-k+1[/tex] празнини (включително двата края), а избор без съседни обекти съответства точно на поставяне на [tex]k[/tex]-те избрани обекта в [tex]k[/tex] различни празнини, най-много по един във всяка.
Номерираме рицарите около масата с [tex]1; 2; \ldots; 12[/tex]. Случай 1: рицар [tex]1[/tex] е избран. Тогава рицари [tex]2[/tex] и [tex]12[/tex] не могат да бъдат избрани и трябва да изберем [tex]4[/tex] два по два несъседни рицари измежду [tex]3; 4; \ldots; 11[/tex]. Тези [tex]9[/tex] рицари образуват редица (никой от тях не е съсед на рицар [tex]1[/tex], а рицари [tex]3[/tex] и [tex]11[/tex] не са съседи), затова според лемата броят на начините е
[tex]\binom{9-4+1}{4}=\binom{6}{4}=15[/tex]
Случай 2: рицар [tex]1[/tex] не е избран. Тогава избираме [tex]5[/tex] два по два несъседни рицари измежду [tex]2; 3; \ldots; 12[/tex]. Тези [tex]11[/tex] рицари образуват редица, защото рицари [tex]2[/tex] и [tex]12[/tex] са разделени от рицар [tex]1[/tex], затова броят на начините е
[tex]\binom{11-5+1}{5}=\binom{7}{5}=21[/tex]
Двата случая не се припокриват, затова отговорът е
[tex]15+21=36[/tex]

Решение:
Въвеждаме координати така, че Кермит тръгва от [tex]\left(0; 0\right)[/tex]. Той прави точно [tex]100[/tex] скока и всеки скок променя една от координатите с [tex]\pm 1[/tex].
Всеки скок променя [tex]|x|+|y|[/tex] с най-много [tex]1[/tex], затова накрая [tex]|x|+|y|\le 100[/tex]. Всеки скок променя [tex]x+y[/tex] с [tex]\pm 1[/tex], т.е. сменя четността му; след четен брой скокове числото [tex]x+y[/tex], а значи и [tex]|x|+|y|[/tex], е четно.
Обратно, всеки възел с [tex]d=|x|+|y|\le 100[/tex] и четно [tex]d[/tex] е достижим: Кермит прави [tex]|x|[/tex] хоризонтални и [tex]|y|[/tex] вертикални скока към него, а после изразходва оставащите [tex]100-d[/tex] джаула (четен брой), като [tex]\frac{100-d}{2}[/tex] пъти скача на изток и обратно на запад.
При [tex]d\ge 1[/tex] има точно [tex]4d[/tex] възела с [tex]|x|+|y|=d[/tex], а при [tex]d=0[/tex] – един възел. Като положим [tex]d=2t[/tex], получаваме броя на възможните възли:
[tex]1+\sum_{t=1}^{50}4\cdot 2t=1+8\cdot \frac{50\cdot 51}{2}=1+10200=10201=101^2[/tex]

Решение:
Многочленът е
[tex]P(x)=\sum_{k=0}^{100}x^{k}(1+x)^{100-k}[/tex]
Използваме тъждеството [tex]a^{n}-b^{n}=(a-b)\left(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1}\right)[/tex] при [tex]a=1+x[/tex], [tex]b=x[/tex], [tex]n=101[/tex]. Тъй като [tex]a-b=1[/tex], вторият множител е точно [tex]P(x)[/tex], следователно
[tex]P(x)=(1+x)^{101}-x^{101}[/tex]
Членът [tex]x^{101}[/tex] не влияе на коефициента пред [tex]x^{50}[/tex], затова според Нютоновия бином този коефициент е [tex]\binom{101}{50}[/tex].
Проверка по друг начин: при [tex]k\le 50[/tex] коефициентът пред [tex]x^{50}[/tex] в [tex]x^{k}(1+x)^{100-k}[/tex] е [tex]\binom{100-k}{50-k}=\binom{100-k}{50}[/tex] (при [tex]k\gt 50[/tex] той е [tex]0[/tex]), а от тъждеството [tex]\sum_{m=r}^{N}\binom{m}{r}=\binom{N+1}{r+1}[/tex]
[tex]\sum_{m=50}^{100}\binom{m}{50}=\binom{101}{51}=\binom{101}{50}[/tex]

Решение:
Простите цифри са [tex]2; 3; 5; 7[/tex] (четири цифри); останалите шест цифри [tex]0; 1; 4; 6; 8; 9[/tex] не са прости. Седемцифрените числа са [tex]9\cdot 10^6=9\,000\,000[/tex], затова броим допълнението – числата, в които няма две съседни прости цифри.
За [tex]k=1; 2; \ldots; 7[/tex] нека [tex]p_k[/tex] и [tex]q_k[/tex] са броят на допустимите начала с дължина [tex]k[/tex] (първа цифра различна от нула, без две съседни прости цифри), завършващи съответно с проста и с непроста цифра, и нека [tex]T_k=p_k+q_k[/tex]. За първата цифра (ненулевите непрости цифри са [tex]1; 4; 6; 8; 9[/tex])
[tex]p_1=4,\qquad q_1=5,\qquad T_1=9[/tex]
Проста цифра може да следва само непроста цифра, а непроста цифра може да следва всяка цифра, следователно
[tex]p_{k+1}=4q_k,\qquad q_{k+1}=6T_k[/tex]
Тогава [tex]T_2=4\cdot 5+6\cdot 9=74[/tex], а при [tex]k\ge 2[/tex]
[tex]T_{k+1}=6T_k+4q_k=6T_k+24T_{k-1}[/tex]
Следователно
[tex]T_3=6\cdot 74+24\cdot 9=660,\qquad T_4=6\cdot 660+24\cdot 74=5736[/tex]
[tex]T_5=6\cdot 5736+24\cdot 660=50\,256,\qquad T_6=6\cdot 50\,256+24\cdot 5736=439\,200[/tex]
[tex]T_7=6\cdot 439\,200+24\cdot 50\,256=3\,841\,344[/tex]
Значи търсеният брой е
[tex]9\,000\,000-3\,841\,344=5\,158\,656[/tex]

Решение:
Условието за правоъгълниците означава, че няма два реда и два стълба, в четирите общи полета на които стои [tex]1[/tex]; с други думи, всеки два реда имат единици в най-много един общ стълб.
За всеки ред разглеждаме двойките стълбове, в които този ред има единици: всеки ред дава [tex]\binom{3}{2}=3[/tex] такива двойки. Ако една и съща двойка стълбове се появи при два различни реда, тези два реда и два стълба биха образували правоъгълник с единици в четирите ъгъла (сбор [tex]4[/tex]), което е забранено. Следователно всичките [tex]3n[/tex] двойки са различни двойки стълбове и
[tex]3n\le\binom{n}{2}=\frac{n(n-1)}{2}\Rightarrow n-1\ge 6\Rightarrow n\ge 7[/tex]
При [tex]n=7[/tex] такава таблица съществува: номерираме редовете и стълбовете от [tex]1[/tex] до [tex]7[/tex] и в ред [tex]i[/tex] записваме [tex]1[/tex] в стълбовете [tex]i[/tex], [tex]i+1[/tex], [tex]i+3[/tex] (взети по модул [tex]7[/tex]), а в останалите полета – [tex]0[/tex]. Редовете съдържат единици в стълбовете
[tex]\{1; 2; 4\},\ \{2; 3; 5\},\ \{3; 4; 6\},\ \{4; 5; 7\},\ \{5; 6; 1\},\ \{6; 7; 2\},\ \{7; 1; 3\}[/tex]
Всеки ред и всеки стълб съдържа точно три единици, а всеки две от тези множества имат точно един общ елемент, затова никой правоъгълник няма единици в четирите си ъгъла. Следователно най-малката възможна стойност е [tex]n=7[/tex].

Решение:
Нека [tex]\omega=-\frac{1}{2}+\frac{\sqrt{3}}{2}i[/tex]. Тогава
[tex]\omega^3=1,\qquad 1+\omega+\omega^2=0,\qquad 1+\omega=-\omega^2[/tex]
Тъй като [tex]\omega^j[/tex] зависи само от остатъка на [tex]j[/tex] при деление на [tex]3[/tex], имаме [tex]\sum_{0\lt j\lt n}\binom{n}{j}\omega^j=S_0+S_1\omega+S_2\omega^2[/tex]. От Нютоновия бином [tex]\sum_{j=0}^{n}\binom{n}{j}\omega^j=(1+\omega)^n[/tex], затова след премахване на събираемите с [tex]j=0[/tex] и [tex]j=n[/tex] получаваме
[tex]S_0+S_1\omega+S_2\omega^2=(1+\omega)^n-1-\omega^n=(-1)^n\omega^{2n}-1-\omega^n[/tex]
Твърдение: [tex]S_0=S_1=S_2[/tex] тогава и само тогава, когато [tex]S_0+S_1\omega+S_2\omega^2=0[/tex]. Ако трите сбора са равни на [tex]s[/tex], лявата страна е [tex]s(1+\omega+\omega^2)=0[/tex]. Обратно, заместването [tex]\omega^2=-1-\omega[/tex] дава [tex](S_0-S_2)+(S_1-S_2)\omega=0[/tex] с реални коефициенти; тъй като [tex]\omega[/tex] не е реално число, [tex]S_1=S_2[/tex], а тогава и [tex]S_0=S_2[/tex].
Следователно трябва [tex](-1)^n\omega^{2n}=1+\omega^n[/tex]. Двете страни зависят само от остатъка на [tex]n[/tex] при деление на [tex]6[/tex]; пресмятаме ги в шестте случая:
[tex]n=6k:\quad (-1)^n\omega^{2n}=1,\quad 1+\omega^n=2[/tex]
[tex]n=6k+1:\quad (-1)^n\omega^{2n}=-\omega^2,\quad 1+\omega^n=1+\omega=-\omega^2[/tex]
[tex]n=6k+2:\quad (-1)^n\omega^{2n}=\omega^4=\omega,\quad 1+\omega^n=1+\omega^2=-\omega[/tex]
[tex]n=6k+3:\quad (-1)^n\omega^{2n}=-\omega^6=-1,\quad 1+\omega^n=1+\omega^3=2[/tex]
[tex]n=6k+4:\quad (-1)^n\omega^{2n}=\omega^8=\omega^2,\quad 1+\omega^n=1+\omega^4=1+\omega=-\omega^2[/tex]
[tex]n=6k+5:\quad (-1)^n\omega^{2n}=-\omega^{10}=-\omega,\quad 1+\omega^n=1+\omega^5=1+\omega^2=-\omega[/tex]
Двете страни са равни само при [tex]n=6k+1[/tex] и [tex]n=6k+5[/tex] (при [tex]n=6k+2[/tex] и [tex]n=6k+4[/tex] те са противоположни ненулеви числа). Следователно условието е изпълнено точно при [tex]n=6k+1[/tex] и [tex]n=6k+5[/tex], [tex]k=0; 1; 2; \ldots[/tex], т.е. за естествените числа, които не се делят нито на [tex]2[/tex], нито на [tex]3[/tex].
Проверка при [tex]n=5[/tex]: [tex]S_1=\binom{5}{1}+\binom{5}{4}=10[/tex], [tex]S_2=\binom{5}{2}=10[/tex], [tex]S_0=\binom{5}{3}=10[/tex]; при [tex]n=4[/tex]: [tex]S_1=\binom{4}{1}=4[/tex], но [tex]S_2=\binom{4}{2}=6[/tex].

Решение:
Да допуснем противното: всеки дядо има най-много [tex]13[/tex] внуци в селото. Вземаме произволно дете [tex]X[/tex] и нека [tex]A[/tex] и [tex]B[/tex] са двамата му дядовци. Всяко друго дете има общ дядо с [tex]X[/tex], затова всяко дете е внук на [tex]A[/tex] или на [tex]B[/tex].
Нека [tex]a[/tex] и [tex]b[/tex] са броят на внуците в селото съответно на [tex]A[/tex] и на [tex]B[/tex], а [tex]t[/tex] е броят на децата, които са внуци и на двамата. По принципа за включване и изключване
[tex]a+b-t=20\Rightarrow t=a+b-20\le 13+13-20=6[/tex]
Нека [tex]P[/tex] е множеството на децата, които са внуци на [tex]A[/tex], но не и на [tex]B[/tex], а [tex]Q[/tex] – множеството на децата, които са внуци на [tex]B[/tex], но не и на [tex]A[/tex]. Тогава
[tex]|P|=a-t=20-b\ge 7,\qquad |Q|=b-t=20-a\ge 7,\qquad |P|+|Q|=20-t\ge 14[/tex]
В частност и двете множества са непразни. Вземаме произволно [tex]Y\in P[/tex] с дядовци [tex]A[/tex] и [tex]C[/tex] (тук [tex]C\ne B[/tex]) и произволно [tex]Z\in Q[/tex] с дядовци [tex]B[/tex] и [tex]D[/tex] (тук [tex]D\ne A[/tex]). Децата [tex]Y[/tex] и [tex]Z[/tex] имат общ дядо. Той не е [tex]A[/tex], защото [tex]Z[/tex] не е внук на [tex]A[/tex], и не е [tex]B[/tex], защото [tex]Y[/tex] не е внук на [tex]B[/tex]. Следователно [tex]C=D[/tex].
Като фиксираме [tex]Z[/tex] и оставим [tex]Y[/tex] да пробяга [tex]P[/tex], виждаме, че всички деца от [tex]P[/tex] имат един и същ втори дядо [tex]D[/tex]; като фиксираме [tex]Y[/tex] и оставим [tex]Z[/tex] да пробяга [tex]Q[/tex], виждаме, че и всички деца от [tex]Q[/tex] имат дядо [tex]D[/tex]. Значи [tex]D[/tex] има поне [tex]|P|+|Q|\ge 14[/tex] внуци, което противоречи на допускането. Следователно има дядо с поне [tex]14[/tex] внуци в селото.