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

Решение:
Една колекция се определя напълно от броя [tex]a,b,c,d\ge 0[/tex] на монетите от [tex]1[/tex], [tex]5[/tex], [tex]10[/tex] и [tex]20[/tex] евроцента, като
[tex]a+b+c+d=15[/tex]
Кодираме такава четворка с редица от [tex]15[/tex] звездички и [tex]3[/tex] черти: [tex]a[/tex] звездички, черта, [tex]b[/tex] звездички, черта, [tex]c[/tex] звездички, черта, [tex]d[/tex] звездички. Това е биекция между колекциите и редиците от [tex]18[/tex] символа с точно [tex]3[/tex] черти, а такава редица се определя от местата на чертите:
[tex]\binom{18}{3}=\frac{18\cdot 17\cdot 16}{6}=816[/tex]
(Това са комбинации с повторение от [tex]4[/tex] елемента от [tex]15[/tex]-ти клас: [tex]\binom{4+15-1}{15}=\binom{18}{3}[/tex].)

Решение:
Нека [tex]N\gt 3{,}6\cdot 10^9[/tex] е броят на хората. Най-много [tex]0{,}01N[/tex] от тях са на възраст над [tex]100[/tex] години, затова хората на възраст не повече от [tex]100[/tex] години са поне
[tex]0{,}99N\gt 0{,}99\cdot 3{,}6\cdot 10^9=3\,564\,000\,000[/tex]
Възрастта на всеки от тях в навършени години е най-много [tex]100[/tex], т.е. всеки от тях е живял по-малко от [tex]101[/tex] години, следователно всички те са родени през последните [tex]101[/tex] години. Период от [tex]101[/tex] години съдържа най-много [tex]101\cdot 366[/tex] дни, така че продължителността му в секунди е най-много
[tex]101\cdot 366\cdot 24\cdot 3600=3\,193\,862\,400[/tex]
Дори като отчетем и непълните секунди в двата му края, този период обхваща най-много [tex]3\,193\,862\,401[/tex] различни секунди (по часовника).
Да разгледаме тези секунди като кутии и да поставим всеки от тези хора в кутията на секундата, в която е роден. Хората са повече от [tex]3\,564\,000\,000[/tex], а кутиите са най-много [tex]3\,193\,862\,401[/tex], така че според принципа на Дирихле в някоя кутия има поне двама души, т.е. тези двама души са родени в една и съща секунда.

Решение:
Думата има [tex]6[/tex] букви: О и С се срещат по два пъти, а К и М – по веднъж. Без ограничения броят на подрежданията (пермутации с повторение) е
[tex]\frac{6!}{2!\cdot 2!}=180[/tex]
Нека [tex]A[/tex] е множеството на подрежданията, в които двете букви О са съседни, а [tex]B[/tex] – множеството на тези, в които двете букви С са съседни. Като слепим двете букви О в един блок, подреждаме [tex]5[/tex] обекта, сред които С се среща два пъти; аналогично за [tex]B[/tex]. Ако слепим и двете двойки, подреждаме [tex]4[/tex] различни обекта:
[tex]|A|=\frac{5!}{2!}=60,\quad |B|=60,\quad |A\cap B|=4!=24[/tex]
Според принципа за включване и изключване броят на „лошите“ подреждания е
[tex]|A\cup B|=60+60-24=96[/tex]
Следователно търсеният брой е [tex]180-96=84[/tex].

Решение:
Без ограничения на всяко от шестте места може да стои коя да е от трите букви, така че думите са [tex]3^6=729[/tex].
Нека [tex]A_1, A_2, A_3[/tex] са множествата от думи, в които не участва съответно първата, втората и третата буква. Тогава [tex]|A_i|=2^6=64[/tex]; при [tex]i\ne j[/tex] множеството [tex]A_i\cap A_j[/tex] съдържа само думата, съставена от оставащата буква, т.е. [tex]|A_i\cap A_j|=1[/tex]; освен това [tex]A_1\cap A_2\cap A_3=\varnothing[/tex].
Според принципа за включване и изключване броят на думите, в които липсва поне една буква, е
[tex]|A_1\cup A_2\cup A_3|=3\cdot 64-3\cdot 1+0=189[/tex]
Следователно думите, които съдържат и трите букви, са [tex]729-189=540[/tex].

Решение:
Тъй като [tex]2187=3^7[/tex], всяка цифра е делител на [tex]3^7[/tex]. Цифрата [tex]0[/tex] е невъзможна (произведението не е [tex]0[/tex]), затова единствените възможни цифри са [tex]1[/tex], [tex]3[/tex] и [tex]9[/tex] ([tex]27[/tex] не е цифра).
Нека числото съдържа [tex]a[/tex] тройки, [tex]b[/tex] деветки и [tex]5-a-b[/tex] единици. Тогава
[tex]3^a\cdot 9^b=3^{a+2b}=3^7\Rightarrow a+2b=7,\quad a+b\le 5[/tex]
Като заместим [tex]a=7-2b[/tex], получаваме [tex]7-b\le 5[/tex], т.е. [tex]b\ge 2[/tex], а от [tex]a\ge 0[/tex] следва [tex]b\le 3[/tex].
При [tex]b=2[/tex], [tex]a=3[/tex] цифрите са [tex]3; 3; 3; 9; 9[/tex] и те могат да се подредят по [tex]\frac{5!}{3!\cdot 2!}=10[/tex] начина.
При [tex]b=3[/tex], [tex]a=1[/tex] цифрите са [tex]9; 9; 9; 3; 1[/tex] и те могат да се подредят по [tex]\frac{5!}{3!}=20[/tex] начина.
Нито една цифра не е [tex]0[/tex], така че всяко подреждане дава петцифрено число. Общо числата са [tex]10+20=30[/tex].

Решение:
Общият член е
[tex]T_{k+1}=\binom{n}{k}\left(\sqrt{x}\right)^{n-k}\left(\frac{1}{2\sqrt[4]{x}}\right)^{k}=\frac{1}{2^k}\binom{n}{k}x^{\frac{n-k}{2}-\frac{k}{4}}[/tex]
като степенният показател на [tex]x[/tex] намалява при нарастване на [tex]k[/tex]. За да има три члена, е нужно [tex]n\ge 2[/tex]. Коефициентите на първите три члена ([tex]k=0; 1; 2[/tex]) са
[tex]1; \quad \frac{n}{2}; \quad \frac{1}{4}\binom{n}{2}=\frac{n(n-1)}{8}[/tex]
Те образуват аритметична прогресия точно когато
[tex]2\cdot \frac{n}{2}=1+\frac{n(n-1)}{8}\iff 8n=8+n^2-n\iff n^2-9n+8=0[/tex]
с корени [tex]n=1[/tex] и [tex]n=8[/tex]. Коренът [tex]n=1[/tex] отпада, защото тогава развитието има само два члена. При [tex]n=8[/tex] коефициентите са [tex]1; 4; 7[/tex], които наистина образуват аритметична прогресия. Следователно [tex]n=8[/tex].

Решение:
Заради [tex]\lg x[/tex] трябва [tex]x\gt 0[/tex]. Общият член на [tex]\left(a+b\right)^5[/tex] е [tex]T_{k+1}=\binom{5}{k}a^{5-k}b^k[/tex]; тук [tex]a=x^{\lg x}[/tex], [tex]b=x[/tex], а третият член съответства на [tex]k=2[/tex]:
[tex]T_3=\binom{5}{2}\left(x^{\lg x}\right)^3x^2=10\,x^{3\lg x+2}[/tex]
Условието [tex]T_3=100[/tex] дава [tex]x^{3\lg x+2}=10[/tex]. Двете страни са положителни, затова можем да логаритмуваме при основа [tex]10[/tex]:
[tex]\left(3\lg x+2\right)\lg x=1[/tex]
При [tex]u=\lg x[/tex] получаваме
[tex]3u^2+2u-1=0\Rightarrow u=\frac{1}{3}\text{ или }u=-1[/tex]
Следователно [tex]x=10^{\frac{1}{3}}=\sqrt[3]{10}[/tex] или [tex]x=10^{-1}=\frac{1}{10}[/tex]; и двете стойности са положителни, значи и двете са допустими.
Проверка: при [tex]x=\frac{1}{10}[/tex] имаме [tex]x^{\lg x}=10[/tex] и [tex]T_3=10\cdot 10^3\cdot \frac{1}{100}=100[/tex]; при [tex]x=\sqrt[3]{10}[/tex] имаме [tex]T_3=10\cdot 10^{\frac{1}{3}}\cdot 10^{\frac{2}{3}}=100[/tex].

Решение:
Нечетните числа заемат нечетните места, следователно четните числа [tex]2, 4, 6, 8, 10[/tex] заемат четните места [tex]2, 4, 6, 8, 10[/tex] и никое от тях не стои на своето място. Значи трябва да намерим броя [tex]D_5[/tex] на пермутациите на [tex]5[/tex] елемента, в които нито един елемент не е на своето място.
Прилагаме принципа за включване и изключване: [tex]m[/tex] числа, които задължително остават на местата си, могат да се изберат по [tex]\binom{5}{m}[/tex] начина, а останалите [tex]5-m[/tex] числа могат да се наредят по [tex](5-m)![/tex] начина. Следователно
[tex]D_5=5!-\binom{5}{1}\cdot 4!+\binom{5}{2}\cdot 3!-\binom{5}{3}\cdot 2!+\binom{5}{4}\cdot 1!-\binom{5}{5}\cdot 0![/tex]
[tex]D_5=120-120+60-20+5-1=44[/tex]

Решение:
Записваме сумата в обратен ред, като използваме [tex]\binom{n}{k}=\binom{n}{n-k}[/tex]:
[tex]S=(n+1)\binom{n}{0}+n\binom{n}{1}+\ldots+(n+1-k)\binom{n}{k}+\ldots+1\cdot \binom{n}{n}[/tex]
Събираме двата израза почленно: коефициентът пред всяко [tex]\binom{n}{k}[/tex] става [tex](k+1)+(n+1-k)=n+2[/tex], а от Нютоновия бином [tex]\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=(1+1)^n=2^n[/tex]:
[tex]2S=(n+2)\left(\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}\right)=(n+2)\cdot 2^n\ \Rightarrow\ S=(n+2)\cdot 2^{n-1}[/tex]

Решение:
Въвеждаме координати така, че точките да са [tex]\left(x; y\right)[/tex], където [tex]x\in\{0; 1; 2; 3; 4\}[/tex], [tex]y\in\{0; 1; 2\}[/tex]. Три точки са върхове на триъгълник точно когато не лежат на една права. Броят на всички тройки точки е
[tex]\binom{15}{3}=455[/tex]
От този брой изваждаме тройките точки, лежащи на една права. Тройките върху един ред са [tex]3\cdot \binom{5}{3}=30[/tex].
Всяка друга права не е хоризонтална, затова пресича всеки ред в най-много една точка и тройка точки върху нея съдържа по една точка от всеки ред. Тъй като ординатите им са [tex]0, 1, 2[/tex], средната точка е среда на отсечката между другите две, т.е. точките са [tex]\left(a; 0\right), \left(a+d; 1\right), \left(a+2d; 2\right)[/tex], където [tex]0\le a\le 4[/tex] и [tex]0\le a+2d\le 4[/tex]. Това дава [tex]5[/tex] тройки при [tex]d=0[/tex] (стълбовете), по [tex]3[/tex] тройки при [tex]d=\pm 1[/tex] и по [tex]1[/tex] тройка при [tex]d=\pm 2[/tex] (случаят [tex]\left|d\right|\ge 3[/tex] е невъзможен), т.е.
[tex]5+2\cdot 3+2\cdot 1=13[/tex]
Следователно тройките точки, лежащи на една права, са [tex]30+13=43[/tex], а броят на триъгълниците е
[tex]455-43=412[/tex]

Решение:
Разлагаме основата на множители:
[tex]1+x+\frac{1}{x^2}+\frac{1}{x^3}=(1+x)+\frac{1}{x^3}(x+1)=(1+x)\left(1+x^{-3}\right)[/tex]
Следователно изразът е равен на
[tex](1+x)^6\left(1+x^{-3}\right)^6=\left(\sum_{i=0}^{6}\binom{6}{i}x^i\right)\left(\sum_{j=0}^{6}\binom{6}{j}x^{-3j}\right)[/tex]
Произведение на два члена дава [tex]x^0[/tex] точно когато [tex]i=3j[/tex]. Тъй като [tex]0\le i\le 6[/tex], възможните двойки са [tex]\left(i; j\right)=\left(0; 0\right), \left(3; 1\right), \left(6; 2\right)[/tex], следователно свободният член е
[tex]\binom{6}{0}\binom{6}{0}+\binom{6}{3}\binom{6}{1}+\binom{6}{6}\binom{6}{2}=1+20\cdot 6+15=136[/tex]

Решение:
Номерираме хоризонталните линии на мрежата с [tex]0, 1, \ldots, n[/tex] от основата нагоре. Линия [tex]j[/tex] съдържа [tex]n-j+1[/tex] възела, които номерираме с [tex]0, 1, \ldots, n-j[/tex] отляво надясно (възел [tex]0[/tex] лежи на лявата страна на големия триъгълник).
Триъгълник „нагоре“ със страна [tex]s[/tex] се определя от долния си ляв връх. Ако той е възел [tex]i[/tex] от линия [tex]j[/tex], то долният десен връх е възел [tex]i+s[/tex] от същата линия, а горният връх е възел [tex]i[/tex] от линия [tex]j+s[/tex]. Триъгълникът лежи в мрежата точно когато
[tex]i+s\le n-j\iff i+j\le n-s, \quad i, j\ge 0[/tex]
Броят на тези двойки [tex]\left(i; j\right)[/tex] е [tex]1+2+\ldots+(n-s+1)=\binom{n-s+2}{2}[/tex]. Сумираме по [tex]s=1, 2, \ldots, n[/tex] и използваме [tex]\binom{k}{2}=\binom{k+1}{3}-\binom{k}{3}[/tex] (събираемите се унищожават последователно):
[tex]N=\binom{n+1}{2}+\binom{n}{2}+\ldots+\binom{2}{2}=\binom{n+2}{3}=\frac{n(n+1)(n+2)}{6}[/tex]

Решение:
Всяко от написаните числа е делител на [tex]64=2^6[/tex], т.е. е от вида [tex]2^a[/tex], където [tex]a\ge 0[/tex] е цяло число. Редицата [tex]2^{a_1}, 2^{a_2}, \ldots, 2^{a_5}[/tex] има произведение [tex]64[/tex] точно когато
[tex]a_1+a_2+a_3+a_4+a_5=6, \quad a_i\ge 0[/tex]
Всяко такова наредено решение съответства на подреждане в редица на [tex]6[/tex] единици и [tex]4[/tex] прегради, затова броят на възможните редици е
[tex]\binom{6+4}{4}=\binom{10}{4}=210[/tex]
Ако изберем [tex]4\cdot 210+1=841[/tex] ученици, то по принципа на Дирихле някоя редица е написана от поне [tex]5[/tex] от тях.
[tex]840[/tex] ученици не са достатъчни: възможно е всяка от [tex]210[/tex]-те редици да е написана от поне [tex]4[/tex] ученици (за това са нужни [tex]840\le 999[/tex] ученици) и ако изберем точно по [tex]4[/tex] ученици за всяка редица, сред избраните [tex]840[/tex] няма петима с еднакви редици. Отговорът е [tex]841[/tex].

Решение:
Нека кандидат има [tex]c[/tex] верни и [tex]w[/tex] грешни отговора, където [tex]c, w\ge 0[/tex] и [tex]c+w\le 40[/tex]; тогава точките му са [tex]s=4c-w[/tex]. При фиксирано [tex]c[/tex] числото [tex]w[/tex] приема всички стойности от [tex]0[/tex] до [tex]40-c[/tex], следователно [tex]s[/tex] приема всички цели стойности в интервала
[tex]\left[5c-40; 4c\right][/tex]
Интервалите за [tex]c[/tex] и [tex]c+1[/tex] не оставят празнина помежду си точно когато [tex]5(c+1)-40\le 4c+1[/tex], т.е. [tex]c\le 36[/tex]. Следователно стойностите [tex]c=0, 1, \ldots, 37[/tex] заедно дават всички цели числа от [tex]-40[/tex] до [tex]4\cdot 37=148[/tex], т.е. [tex]189[/tex] резултата. Останалите стойности на [tex]c[/tex] дават
[tex]c=38:\ 150, 151, 152\qquad c=39:\ 155, 156\qquad c=40:\ 160[/tex]
Резултатите [tex]149, 153, 154, 157, 158, 159[/tex] са невъзможни, така че броят на възможните резултати е
[tex]189+3+2+1=195[/tex]
При [tex]390=2\cdot 195[/tex] кандидати може всеки от възможните резултати да е получен от точно двама кандидати и тогава няма трима с равен брой точки. При [tex]391\gt 2\cdot 195[/tex] кандидати по принципа на Дирихле някой резултат е получен от поне трима от тях. Отговорът е [tex]391[/tex].