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

Решение:
Каждое натуральное число единственным образом записывается в виде [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]b[/tex] делится на [tex]a[/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\in P[/tex], видим, что у всех детей из [tex]P[/tex] один и тот же второй дед [tex]D[/tex]; зафиксировав [tex]Y[/tex] и перебирая все [tex]Z\in Q[/tex], видим, что и у всех детей из [tex]Q[/tex] есть дед [tex]D[/tex]. Значит, у [tex]D[/tex] не менее [tex]|P|+|Q|\ge 14[/tex] внуков, что противоречит предположению. Следовательно, есть дед, у которого в деревне не менее [tex]14[/tex] внуков.