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

Решение:
Набор полностью определяется количествами [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].