Комбинаторика. Книга 2

Каждое ребро даёт вклад \(2\) в сумму степеней, значит сумма степеней равна \(2E\) и чётна. Сумма чётных степеней чётна, поэтому сумма нечётных степеней тоже чётна. Сумма нечётного количества нечётных чисел была бы нечётной, значит таких вершин чётное число.

Всего пар \((ученик, кружок)\), где ученик посещает кружок, равно \(120\cdot4=480\). Если бы каждый кружок имел не более \(31\) участника, пар было бы не более \(15\cdot31=465\), противоречие. Значит, некоторый кружок имеет хотя бы \(32\) участника.

Считаем пары \((клетка, линия)\), где линия — строка или столбец, содержащая отмеченную клетку. Каждая отмеченная клетка даёт \(2\) пары, всего \(140\). Линий \(24\). Среднее равно \(\frac{140}{24}>5\), значит некоторая линия содержит хотя бы \(6\) отмеченных клеток.

Правая часть \(2^n\) считает подмножества по независимому выбору: каждый элемент либо входит, либо не входит. Левая часть считает те же подмножества по размеру: сначала выбираем размер \(k\), затем само \(k\)-элементное подмножество. Это один и тот же набор объектов, значит тождество доказано.

Если сначала выбрать \(A\) размера \(k\), то отмеченный элемент \(x\in A\) выбирается \(k\) способами, получаем левую часть. Если сначала выбрать \(x\), есть \(n\) вариантов, а остальные элементы подмножества выбираются произвольно: \(2^{n-1}\) вариантов. Получаем \(n2^{n-1}\).

Число пар \((x,A)\), где \(x\in A\), не меньше \(18\cdot4=72\). Эти пары распределены между \(10\) элементами. Среднее число множеств на элемент не меньше \(7.2\), значит некоторый элемент входит хотя бы в \(8\) множеств.

Сумма степеней равна \(2E>(r-1)n\). Если бы все степени были не больше \(r-1\), сумма степеней была бы не больше \((r-1)n\), противоречие. Значит, есть вершина степени хотя бы \(r\).

Всего игр \(\binom n2\), и каждая игра даёт ровно одну победу. Среднее число побед на игрока равно \(\frac{\binom n2}{n}=\frac{n-1}{2}\). Поэтому кто-то имеет не меньше среднего, а кто-то не больше среднего.

Считаем пары \((A,\{x,y\})\), где \(A\subseteq[n]\) и \(x,y\in A\). Если сначала выбрать \(A\) размера \(k\), получаем \(\binom{k}{2}\binom nk\). Суммируем по \(k\). Если сначала выбрать \(\{x,y\}\), есть \(\binom n2\) способов, а остальные \(n-2\) элементов можно выбирать свободно: \(2^{n-2}\) способов.

Каждая строка с \(3\) отметками даёт \(\binom32=3\) пар столбцов. Всего таких появлений пар \(6\cdot3=18\). Всего пар столбцов \(\binom62=15\). Если бы каждая пара столбцов появлялась не более одного раза, появлений было бы не больше \(15\), противоречие. Значит, некоторая пара столбцов появляется хотя бы в двух строках.

Пусть \(d_i\) — число подмножеств, содержащих \(i\)-й элемент. Тогда \(\sum d_i=24\). Сумма размеров всех попарных пересечений равна \(\sum_{i=1}^5\binom{d_i}{2}\). При фиксированной сумме \(24\) эта величина минимальна при распределении \(5,5,5,5,4\), и равна \(46\). Если бы все попарные пересечения имели размер не больше \(1\), сумма была бы не больше \(\binom82=28\). Противоречие.

Всего решений не меньше \(30\cdot3=90\). Если каждую задачу решили не более \(14\) участников, всего решений было бы не больше \(6\cdot14=84\), противоречие. Значит, есть задача с хотя бы \(15\) решениями.

Каждое выбранное подмножество содержит \(\binom{k}{2}\) пар элементов, всего \(m\binom{k}{2}\) появлений пар. Но одна и та же пара элементов не может лежать в двух разных выбранных подмножествах, иначе эти два подмножества имели бы как минимум два общих элемента. Всего пар элементов в исходном множестве \(\binom n2\). Следовательно, \(m\binom{k}{2}\le\binom n2\).

Каждая строка даёт \(\binom r2\) пар отмеченных столбцов, всего \(n\binom r2\) появлений. По условию каждая пара столбцов появляется не более одного раза. Всего пар столбцов \(\binom n2\). Поэтому \(n\binom r2\le\binom n2\).

Зафиксируем среднюю вершину \(v_i\). Чтобы получить путь длины \(2\) с этой средней вершиной, надо выбрать две различные соседние вершины из \(d_i\) соседей: \(\binom{d_i}{2}\) способов. Каждый неупорядоченный путь длины \(2\) имеет ровно одну среднюю вершину, значит сумма по всем вершинам даёт точное число таких путей.

Пусть \(d_j\) — число учеников, решивших \(j\)-ю задачу. Тогда \(\sum d_j\ge21\cdot6=126\). Число троек \((\{u,v\}, задача)\), где оба ученика решили эту задачу, равно \(\sum_{j=1}^{10}\binom{d_j}{2}\). При сумме \(126\) по \(10\) задачам эта сумма минимальна при распределении \(13,13,13,13,13,13,12,12,12,12\), и равна \(6\binom{13}{2}+4\binom{12}{2}=732\). Пар учеников \(\binom{21}{2}=210\). Если бы каждая пара имела не более \(3\) общих задач, троек было бы не больше \(630\), противоречие. Значит, есть пара с не менее чем \(4\) общими задачами.

Если любые два выбранных подмножества пересекаются не более чем по одному элементу, то одна и та же пара элементов не может лежать в двух разных подмножествах. Тогда всего появлений пар не больше \(\binom{20}{2}=190\). Но каждое из \(30\) подмножеств размера \(6\) содержит \(\binom62=15\) пар, всего \(450\) появлений. Противоречие. Значит, два подмножества имеют хотя бы два общих элемента.

Каждое выбранное \(k\)-элементное множество содержит \(\binom{k}{t+1}\) подмножеств размера \(t+1\), всего \(m\binom{k}{t+1}\) появлений. Но одно и то же \((t+1)\)-элементное подмножество не может лежать в двух выбранных множествах: тогда эти два множества имели бы как минимум \(t+1\) общих элементов, что запрещено. Всего \((t+1)\)-подмножеств исходного множества \(\binom{n}{t+1}\). Получаем неравенство.

Число путей длины \(2\) равно \(\sum_i\binom{d_i}{2}\), где \(d_i\) — степени вершин. Функция \(\binom{x}{2}=\frac{x(x-1)}2\) выпукла, поэтому при фиксированной сумме \(\sum d_i=2m\) сумма \(\sum\binom{d_i}{2}\) не меньше \(n\binom{2m/n}{2}\). Если средняя степень \(\frac{2m}{n}>r\), то среднее значение \(\binom{d_i}{2}\) больше \(\binom r2\) в подходящем строгом смысле, значит некоторая вершина даёт больше \(\binom r2\) путей длины \(2\).

Сумма размеров всех попарных пересечений равна \(\sum_x\binom{d(x)}2\), потому что каждый элемент \(x\) вносит вклад в пары множеств, которые его содержат. При \(\sum d(x)\ge mr\) выпуклость даёт

\[\sum_x\binom{d(x)}2\ge n\binom{mr/n}{2}=\frac{mr(mr-n)}{2n}.\]

Пар множеств всего \(\binom m2\). Значит, средний размер попарного пересечения не меньше

\[\frac{\frac{mr(mr-n)}{2n}}{\binom m2}=\frac{r(mr-n)}{n(m-1)}.\]

Следовательно, одно из пересечений не меньше этого среднего.

По формуле включений-исключений получаем \(18+14-6=26\). Шесть учеников, изучающих оба языка, были посчитаны дважды, поэтому их надо вычесть один раз.

Чисел, делящихся на \(3\), ровно \(\left\lfloor\frac{200}{3}\right\rfloor=66\). Делящихся на \(5\) — \(40\). Делящихся на оба, то есть на \(15\), — \(13\). Ответ: \(66+40-13=93\).

Всего слов \(4^6\). Без буквы \(A\) каждую позицию можно заполнить \(3\) способами, всего \(3^6\). Ответ: \(4^6-3^6=4096-729=3367\).

Всего \(3^5\) слов. Если отсутствует выбранная буква, остаётся \(2^5\) слов, таких выборов \(3\). Если отсутствуют две выбранные буквы, остаётся \(1^5\) слово, таких выборов \(3\), и эти слова надо вернуть. Ответ: \(3^5-3\cdot2^5+3=150\).

По включениям-исключениям получаем \(4!-\binom41 3!+\binom42 2!-\binom43 1!+\binom44 0!=24-24+12-4+1=9\).

Чисел, делящихся хотя бы на одно из \(2,3,5\), равно \(500+333+200-166-100-66+33=734\). Поэтому не делящихся ни на одно из них \(1000-734=266\).

Всего функций \(3^6\). Вычитаем функции, пропускающие выбранное значение: \(3\cdot2^6\). Возвращаем функции, пропускающие два выбранных значения: \(\binom32\cdot1^6\). Ответ: \(3^6-3\cdot2^6+3=540\).

Без ограничений \(8!\). Если выбранные \(i\) из чисел \(1,2,3\) стоят на своих местах, остальные \(8-i\) элементов переставляются свободно. Ответ: \(8!-\binom31 7!+\binom32 6!-\binom33 5!=27240\).

Если выбраны \(i\) элементов, которые должны быть неподвижны, то остальные \(n-i\) элементов можно переставить \((n-i)!\) способами. По включениям-исключениям

\[D_n=\sum_{i=0}^n(-1)^i\binom ni(n-i)!=n!\sum_{i=0}^n\frac{(-1)^i}{i!}.\]

Сначала выбираем \(2\) неподвижные точки: \(\binom72=21\). Остальные \(5\) элементов должны не иметь неподвижных точек, их можно переставить \(D_5=44\) способами. Ответ: \(21\cdot44=924\).

Всего строк \(10^8\). Если отсутствует одна из трёх цифр, остаётся \(9^8\) строк; таких запретов \(3\). Если отсутствуют две из них, остаётся \(8^8\) строк; таких пар \(3\). Если отсутствуют все три, \(7^8\). Ответ: \(10^8-3\cdot9^8+3\cdot8^8-7^8\).

По включениям-исключениям:

\[6!-\binom41 5!+\binom42 4!-\binom43 3!+\binom44 2!=720-480+144-24+2=362.\]

Всего функций \(m^n\). Если выбраны \(i\) значений, которые не используются, то все \(n\) элементов области должны перейти в оставшиеся \(m-i\) значений: \((m-i)^n\) функций. Выбрать такие \(i\) значений можно \(\binom mi\) способами. Чередуя знаки по включениям-исключениям, получаем формулу.

Выбираем \(k\) элементов, которые будут неподвижными: \(\binom nk\) способов. Остальные \(n-k\) элементов должны не иметь неподвижных точек среди своих позиций, иначе неподвижных точек было бы больше \(k\). Это можно сделать \(D_{n-k}\) способами. Получаем \(\binom nkD_{n-k}\).

В беспорядке элемент \(1\) переходит на место \(j\ne1\), \(n-1\) вариантов. Рассмотрим элемент \(j\). Если \(j\) переходит на место \(1\), то остальные \(n-2\) элементов образуют беспорядок: \(D_{n-2}\) способов. Если \(j\) не переходит на место \(1\), то после объединения мест \(1\) и \(j\) задача сводится к беспорядку \(n-1\) элементов: \(D_{n-1}\) способов. Итого \(D_n=(n-1)(D_{n-1}+D_{n-2})\).

Всего \(5!=120\). Одно нарушение фиксирует одну клетку, даёт \(4!\) перестановки; таких нарушений \(3\), вычитаем \(72\). Два нарушения совместимы только для пар \((1,2)\) с \((2,1)\) и \((1,1)\) с? Условия \((1,1)\) и \((1,2)\) несовместимы, потому что \(\pi(1)\) не может быть сразу \(1\) и \(2\). Условия \((1,1)\) и \((2,1)\) тоже несовместимы, потому что два значения не могут попасть в \(1\). Совместима только пара \((1,2),(2,1)\), она даёт \(3!\) перестановок. Тройное нарушение невозможно. Ответ: \(120-3\cdot24+6=54\).

В формуле для \(|A_1\cup\cdots\cup A_m|\) объект, лежащий ровно в \(r\) множествах, учитывается \(\binom r1\) раз в одиночных суммах, \(\binom r2\) раз в попарных пересечениях, и так далее. Его общий вклад равен \(\binom r1-\binom r2+\cdots+(-1)^{r+1}\binom rr\). Это равно \(1-(1-1)^r=1\). Значит, каждый объект объединения учитывается ровно один раз.

Пусть \(A_j\) — событие, что элемент \(j\) стоит на своём месте, для \(j=1,\ldots,r\). Если выбраны \(i\) таких событий, то \(i\) элементов фиксированы, а остальные \(n-i\) можно переставить \((n-i)!\) способами. По включениям-исключениям число перестановок без этих \(r\) событий равно \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).

Каждое распределение — функция из множества шаров в множество коробок. Требование, чтобы каждая коробка была непуста, означает сюръективность. По формуле включений-исключений получаем

\[\sum_{i=0}^{m}(-1)^i\binom mi(m-i)^n.\]

Здесь \(i\) — число выбранных коробок, которые объявлены пустыми.

Применим включения-исключения к запрещённым событиям: “элемент фиксирован” и “пара образует транспозицию”. Если выбраны \(i\) фиксированных элементов и \(j\) непересекающихся транспозиций, то сначала выбираем эти элементы и пары: \(\frac{n!}{i!\,j!\,2^j\,(n-i-2j)!}\) способов для структуры запретов. Остальные \(n-i-2j\) элементов переставляются произвольно: \((n-i-2j)!\) способов. Вклад имеет знак \((-1)^{i+j}\). Поэтому число равно

\[\sum_{\substack{i,j\ge0\\ i+2j\le n}}(-1)^{i+j}\frac{n!}{i!\,j!\,2^j}.\]

Подмножеству \(A\) сопоставим строку \(a_1\ldots a_n\), где \(a_i=1\), если \(i\in A\), и \(a_i=0\), если \(i\notin A\). По такой строке однозначно восстанавливается \(A=\{i:a_i=1\}\). Значит, это биекция. Бинарных строк длины \(n\) ровно \(2^n\).

Каждый путь состоит ровно из \(5\) шагов \(R\) и \(4\) шагов \(U\). Последовательность шагов задаёт слово длины \(9\), и обратно любое такое слово задаёт путь. Поэтому путей \(\binom{9}{4}=126\).

Решение соответствует строке из \(10\) звёздочек и \(2\) перегородок: количества звёздочек в трёх промежутках равны \(x_1,x_2,x_3\). Обратно, любая такая строка даёт решение. Всего \(\binom{12}{2}=66\) строк.

Так как \(x_i\ge1\), положим \(y_i=x_i-1\ge0\). Тогда \(y_1+y_2+y_3+y_4=13\). По stars and bars число решений равно \(\binom{13+4-1}{4-1}=\binom{16}{3}=560\).

Каждому \(k\)-подмножеству \(A\subseteq[n]\) сопоставим \([n]\setminus A\). Оно имеет \(n-k\) элементов. Обратное отображение — снова взятие дополнения, поэтому это биекция.

Зафиксируем элемент \(a\). Каждому подмножеству \(S\) сопоставим \(S\triangle\{a\}\): если \(a\) был в \(S\), удаляем его, если не был — добавляем. Размер меняется на \(1\), значит чётность размера меняется. Операция обратна сама себе, поэтому это биекция между чётными и нечётными подмножествами.

Все \(k\)-подмножества множества \([n]\) делятся на два класса. Если подмножество не содержит \(n\), оно является \(k\)-подмножеством \([n-1]\): \(\binom{n-1}{k}\) вариантов. Если содержит \(n\), то остальные \(k-1\) элементов выбираются из \([n-1]\): \(\binom{n-1}{k-1}\) вариантов. Эти классы не пересекаются и покрывают все объекты.

Путь до \((3,2)\) содержит \(3\) шагов \(R\) и \(2\) шагов \(U\), таких путей \(\binom{5}{2}=10\). От \((3,2)\) до \((7,5)\) нужно \(4\) шага \(R\) и \(3\) шага \(U\), таких путей \(\binom{7}{3}=35\). Части выбираются независимо, поэтому ответ \(10\cdot35=350\).

Положим \(y_1=x_1-2\), \(y_2=x_2-4\), \(y_3=x_3\), \(y_4=x_4-5\). Тогда \(y_i\ge0\), а сумма равна \(30-2-4-5=19\). Число неотрицательных решений \(y_1+\cdots+y_4=19\) равно \(\binom{19+4-1}{3}=\binom{22}{3}=1540\).

Условие отсутствия соседних даёт \(a_{i+1}\ge a_i+2\). Тогда \(b_i=a_i-i+1\) образуют обычное \(5\)-подмножество множества \(\{1,\ldots,14\}\). Обратно, из \(b_1<\cdots

Разбиение не более чем на \(k\) частей изображается диаграммой с не более чем \(k\) строками. Транспонируем диаграмму: строки становятся столбцами. Теперь длина каждой строки не превосходит \(k\), то есть каждая часть нового разбиения не больше \(k\). Обратное преобразование — снова транспонирование, значит это биекция.

Запишем \(n\) единиц в ряд. Чтобы разбить их на \(k\) непустых групп, нужно выбрать \(k-1\) промежутков из \(n-1\) промежутков между соседними единицами и поставить там перегородки. Размеры групп и будут слагаемыми. Обратно, любая композиция задаёт такие перегородки. Ответ \(\binom{n-1}{k-1}\).

Всего путей \(\binom{2n}{n}\). Плохой путь впервые попадает выше диагонали шагом \(U\), в точку с \(y=x+1\). Отразим начальную часть до этого шага относительно прямой \(y=x+1\). Получается биекция плохих путей с путями из \((-1,1)\) в \((n,n)\), которых \(\binom{2n}{n-1}\). Значит, хороших путей

\[\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}.\]

Всего слов \(\binom{p+q}{q}\). Классическая отражательная биекция показывает, что число плохих слов равно \(\binom{p+q}{q-1}\): плохое слово впервые достигает равенства после начального преимущества \(A\), и отражение соответствующей начальной части меняет один \(A\) в лишний \(B\). Поэтому хороших слов

\[\binom{p+q}{q}-\binom{p+q}{q-1}=\frac{p-q}{p+q}\binom{p+q}{q}.\]

Возьмём открывающую скобку как шаг \(R\), закрывающую как шаг \(U\). В правильной скобочной последовательности в каждом префиксе открывающих скобок не меньше, чем закрывающих, то есть число \(U\) не превосходит числа \(R\). Это ровно условие \(y\le x\). Всего открывающих и закрывающих скобок по \(n\), значит путь идёт в \((n,n)\). Обратно, путь с \(y\le x\) даёт последовательность, в каждом префиксе которой открывающих не меньше закрывающих, то есть правильную скобочную последовательность.

Из разбиения на нечётные части сгруппируем одинаковые нечётные части \(q\). Если \(q\) встречается \(m\) раз, запишем \(m\) в двоичной системе: \(m=\sum 2^s\). Заменим эти \(m\) копий \(q\) на части \(2^s q\). Для каждого \(q\) получаются различные степени \(2^s q\), а для разных нечётных \(q\) части тоже различны. Получаем разбиение на различные части.

Обратно, каждую различную часть единственным образом записываем как \(2^s q\) с нечётным \(q\), и заменяем её на \(2^s\) копий \(q\). Это даёт разбиение на нечётные части. Две операции обратны.

Сумма считает чётные подмножества со знаком \(+\) и нечётные со знаком \(-\). Зафиксируем элемент \(1\). Отображение \(S\mapsto S\triangle\{1\}\) меняет чётность размера и является обратным самому себе. Значит, каждое чётное подмножество спарено с нечётным, и вклад пар сокращается. Сумма равна \(0\).

Из дерева строим последовательность длины \(n-2\): пока осталось больше двух вершин, удаляем лист с наименьшей меткой и записываем метку его соседа. Обратно, по последовательности \(c_1,\ldots,c_{n-2}\) восстанавливаем дерево: на каждом шаге берём наименьшую метку, которой нет в текущей последовательности, соединяем её с \(c_1\), затем удаляем эту метку из набора вершин и удаляем \(c_1\) из последовательности. В конце соединяем две оставшиеся вершины.

Эти процедуры обратны: удалённый на каждом шаге лист именно та наименьшая метка, которая больше не появится в коде. Поэтому деревья биективны последовательностям длины \(n-2\) над алфавитом из \(n\) меток. Таких последовательностей \(n^{n-2}\).

Фиксируем сторону многоугольника. В любой триангуляции есть единственный треугольник, прилегающий к этой стороне; его третья вершина делит многоугольник на две меньшие части. Аналогично правильная скобочная последовательность единственно записывается как \((A)B\), где \(A\) и \(B\) — правильные последовательности. Сопоставим третью вершину так, чтобы число пар в \(A\) равнялось числу треугольников в левой части, а \(B\) — в правой. Рекурсивно применяя то же правило, получаем взаимно однозначное соответствие. База \(n=0\) очевидна.

Всего путей \(\binom{a+b}{b}\). Плохой путь впервые нарушает условие шагом в точку на прямой \(y=x+1\). Отразим начальную часть до этого шага относительно прямой \(y=x+1\). Получится путь из \((-1,1)\) в \((a,b)\). Такой путь должен иметь \(a+1\) шагов \(R\) и \(b-1\) шагов \(U\), поэтому плохих путей \(\binom{a+b}{b-1}\). Следовательно, хороших путей

\[\binom{a+b}{b}-\binom{a+b}{b-1}=\frac{a-b+1}{a+1}\binom{a+b}{b}.\]

Пусть \(M\) — максимальный элемент множества. По условию число \(f(M)\) принадлежит тому же множеству и \(f(M)>M\). Но это противоречит максимальности \(M\). Следовательно, такого соответствия не существует.

Начнём с произвольной точки \(v_1\) и каждый раз будем переходить по стрелке: \(v_1,v_2,v_3,\ldots\). Точек конечное число, поэтому какая-то точка повторится: \(v_i=v_j\) при \(i

Тогда отрезок последовательности \(v_i,v_{i+1},\ldots,v_{j-1},v_j=v_i\) образует цикл по стрелкам. Значит, такой цикл существует.

Предположим, что вершина \(v_k\) соединена с вершиной \(u\), которая не входит в путь. Тогда последовательность \(v_1v_2\ldots v_k u\) является путём и имеет на одну вершину больше.

Это противоречит выбору исходного пути как максимального по длине. Значит, все соседи \(v_k\) лежат на пути.

Выберем в дереве путь максимальной длины \(v_1v_2\ldots v_k\). Если у вершины \(v_k\) есть сосед, не лежащий на пути, путь можно продолжить, что невозможно.

Если \(v_k\) соединена с какой-то более ранней вершиной пути, кроме \(v_{k-1}\), то возникнет цикл. В дереве циклов нет. Значит, единственный сосед \(v_k\) — это \(v_{k-1}\), и степень \(v_k\) равна \(1\).

Пусть \([a,b]\) — отрезок с минимальным правым концом \(b\). Рассмотрим любой другой отрезок \([c,d]\). По выбору \(b\) имеем \(b\le d\).

Так как \([a,b]\) и \([c,d]\) пересекаются, не может быть \(b

Рассмотрим все связные подграфы, содержащие все вершины исходного графа. Среди них выберем подграф \(H\) с минимальным числом рёбер. Такой подграф существует, так как исходный граф входит в рассмотрение.

Если в \(H\) есть цикл, удалим одно ребро этого цикла. Между его концами всё ещё есть путь по остальной части цикла, поэтому связность не нарушается. Получается связный остовный подграф с меньшим числом рёбер, противоречие.

Значит, циклов в \(H\) нет. Искомый граф получен удалением лишних рёбер.

Выберем самый длинный путь \(v_1v_2\ldots v_k\). Все соседи вершины \(v_k\) лежат на этом пути, иначе путь можно было бы продолжить.

Так как степень \(v_k\) не меньше \(2\), кроме соседа \(v_{k-1}\) у неё есть ещё один сосед среди вершин пути. Пусть это \(v_i\), где \(i

В каждой паре \(\{i,2n+1-i\}\) нельзя взять оба числа, потому что их сумма равна \(2n+1\). Значит, из каждой пары взято не более одного числа.

Предположим, из некоторой пары не взято ни одного числа. Тогда можно добавить в \(A\) одно из чисел этой пары: его единственный партнёр по сумме \(2n+1\) тоже отсутствует. Условие не нарушится, что противоречит максимальности по включению.

Следовательно, из каждой пары взято ровно одно число.

Предположим, что непокрытые вершины \(x\) и \(y\) соединены ребром \(xy\). Так как обе вершины не покрыты, ребро \(xy\) не имеет общих концов ни с одним выбранным ребром.

Тогда \(xy\) можно добавить к выбранному множеству, и рёбра всё ещё будут попарно не иметь общих концов. Это противоречит условию, что добавить ребро нельзя. Значит, такого ребра нет.

Имеем \(8=3+5\), \(9=3+3+3\), \(10=5+5\). Предположим, что существуют контрпримеры, и пусть \(n\) — наименьший из них.

Так как \(8,9,10\) представимы, то \(n\ge 11\). Тогда \(n-3\ge 8\), и по минимальности \(n\) число \(n-3\) представимо: \(n-3=3a+5b\).

Следовательно, \(n=3(a+1)+5b\), что противоречит тому, что \(n\) — контрпример. Значит, утверждение верно для всех \(n\ge 8\).

Инверсией назовём пару позиций \(i

Если меняются соседние числа \(x>y\), то пара \((x,y)\) перестаёт быть инверсией. Отношения этих двух чисел со всеми остальными числами не меняют общего числа инверсий, потому что они соседние. Поэтому число инверсий уменьшается на \(1\).

Оно не может уменьшаться бесконечно, значит, процесс завершится. В конце нет соседних чисел в неправильном порядке. Тогда вся последовательность возрастает.

Ответ: \(n-2\). Сначала покажем, что \(n-1\) невозможно. Если \(n-1\) человек знакомы со всеми, то оставшийся человек знаком с каждым из этих \(n-1\) людей. Значит, он тоже знаком со всеми, что противоречит условию.

Покажем достижимость. Пусть два человека \(A\) и \(B\) не знакомы друг с другом, а все остальные знакомы со всеми. Тогда ровно \(n-2\) человек знакомы со всеми остальными, а \(A\) и \(B\) не знакомы со всеми. Условие выполнено.

Выберем направленный путь максимальной длины \(v_1\to v_2\to\cdots\to v_k\). Предположим, что есть вершина \(u\), не лежащая на пути.

Если \(u\to v_1\), то можно поставить \(u\) перед \(v_1\), получив более длинный путь. Поэтому \(v_1\to u\). Если \(v_k\to u\), то можно поставить \(u\) после \(v_k\), значит, \(u\to v_k\).

Идя слева направо, найдём первый индекс \(j\), для которого \(u\to v_j\). Тогда \(j>1\), а по минимальности \(j\) имеем \(v_{j-1}\to u\). Следовательно, можно вставить \(u\) между \(v_{j-1}\) и \(v_j\): \(v_1\to\cdots\to v_{j-1}\to u\to v_j\to\cdots\to v_k\). Это более длинный путь, противоречие.

Значит, внешней вершины нет, и путь содержит все вершины.

Пусть две соседние невыбранные клетки \(i\) и \(i+1\) имеют разные цвета. Тогда пара \((i,i+1)\) подходит по условию и не пересекается ни с одной выбранной парой, потому что обе клетки не выбраны.

Её можно добавить к текущему множеству пар, сохранив все условия. Это противоречит максимальности по включению. Следовательно, таких соседних невыбранных клеток нет.

Выберем самый длинный путь \(v_1v_2\ldots v_m\). Все соседи вершины \(v_m\) лежат на этом пути, иначе путь можно было бы продолжить.

У вершины \(v_m\) не меньше \(k\) соседей среди вершин \(v_1,\ldots,v_{m-1}\). Пусть \(v_i\) — самый ранний из этих соседей на пути. Тогда среди вершин \(v_i,v_{i+1},\ldots,v_{m-1}\) находится не меньше \(k\) соседей вершины \(v_m\), поэтому \(m-i\ge k\).

Рёбра пути от \(v_i\) до \(v_m\) вместе с ребром \(v_m v_i\) образуют цикл \(v_i v_{i+1}\ldots v_m v_i\). В нём \(m-i+1\ge k+1\) вершин.

Пусть сумма всех чисел из \(A\) равна \(S\). У множества \(A\) есть \(2^k\) подмножеств, если считать и пустое. По условию суммы различных непустых подмножеств различны; сумма пустого подмножества равна \(0\) и не совпадает с ними, потому что все числа положительны.

Значит, получаются \(2^k\) различных целых сумм. Каждая из них лежит между \(0\) и \(S\), а в этом промежутке ровно \(S+1\) целых чисел. Поэтому \(S+1\ge 2^k\), откуда \(S\ge 2^k-1\).

Рассмотрим единственный путь от \(A\) к \(B\). Если степень \(A\) больше \(1\), то у \(A\) есть сосед \(C\), отличный от следующей вершины на пути к \(B\).

В дереве путь от \(C\) к \(B\) проходит через \(A\), поэтому расстояние \(CB\) на \(1\) больше расстояния \(AB\). Это противоречит максимальному выбору пары \(A,B\). Значит, степень \(A\) равна \(1\). Аналогично степень \(B\) равна \(1\).

Для каждого места \(i\) обозначим через \(p_i\) длину наибольшей возрастающей подпоследовательности, заканчивающейся на \(a_i\), а через \(q_i\) — длину наибольшей убывающей подпоследовательности, заканчивающейся на \(a_i\).

Предположим, что нет ни возрастающей, ни убывающей подпоследовательности длины \(n+1\). Тогда все пары \((p_i,q_i)\) принимают значения из множества \(\{1,\ldots,n\}\times\{1,\ldots,n\}\), то есть возможны только \(n^2\) пар.

Покажем, что пары для разных \(i\) различны. Если \(ip_i\). Если \(a_i>a_j\), то аналогично \(q_j>q_i\). В обоих случаях пары различны.

Но элементов \(n^2+1\), а различных пар не больше \(n^2\). Противоречие. Значит, нужная подпоследовательность существует.

Выберем вершину \(v\) с максимальной исходящей степенью. Пусть \(u\) — вершина, в которую нет дуги из \(v\). Тогда в турнире обязательно \(u\to v\).

Предположим, что ни один исходящий сосед \(w\) вершины \(v\) не имеет дуги \(w\to u\). Тогда для каждого такого \(w\) дуга направлена \(u\to w\). Кроме того, \(u\to v\). Значит, \(u\) побеждает всех, кого побеждает \(v\), и ещё саму вершину \(v\). У \(u\) исходящих дуг больше, чем у \(v\), противоречие.

Следовательно, найдётся исходящий сосед \(w\) вершины \(v\), для которого \(w\to u\). Тогда \(v\to w\to u\). Для вершин, которые \(v\) побеждает напрямую, путь имеет длину \(1\). Поэтому \(v\) достигает всех вершин за не более чем \(2\) шага.

Пусть два пути максимальной длины \(P\) и \(Q\) не имеют общих вершин. Обозначим их длину через \(L\). Так как граф связен, существует путь, соединяющий некоторую вершину \(x\) пути \(P\) с некоторой вершиной \(y\) пути \(Q\). Выберем такой соединяющий путь кратчайшим; тогда его внутренняя часть не пересекает \(P\) и \(Q\).

Вершина \(x\) делит путь \(P\) на две части, суммы длин которых равна \(L\). Одна из этих частей имеет длину не меньше \(\frac{L}{2}\). Аналогично, вершина \(y\) делит путь \(Q\) на две части, и одна часть имеет длину не меньше \(\frac{L}{2}\).

Возьмём более длинную часть пути \(P\), затем соединяющий путь от \(x\) к \(y\), затем более длинную часть пути \(Q\). Получается простой путь: внутренние вершины соединяющего пути не лежат на \(P\) и \(Q\), а сами \(P\) и \(Q\) не пересекаются.

Его длина не меньше \(\frac{L}{2}+1+\frac{L}{2}=L+1\), потому что соединяющий путь имеет положительную длину. Это больше максимальной длины \(L\), противоречие. Следовательно, два самых длинных пути должны иметь общую вершину.

При одном ходе число чёрных монет либо увеличивается на \(2\), либо уменьшается на \(2\), либо не меняется. Поэтому его чётность сохраняется.

В начале число чёрных монет равно \(1\), то есть нечётно. В целевом положении оно равно \(0\), то есть чётно. Инвариант не совпадает, значит, такое положение недостижимо.

При шахматной раскраске каждое домино \(1\times2\) покрывает одну чёрную и одну белую клетку. Поэтому любая фигура, покрытая домино, содержит поровну чёрных и белых клеток.

В полной доске \(8\times8\) чёрных и белых клеток поровну. После удаления двух клеток одного цвета равенство нарушается. Значит, покрытие домино невозможно.

Будем считать \(+\) числом \(1\), а \(-\) числом \(-1\). Один ход меняет знаки у двух чисел, поэтому произведение всех трёх чисел умножается на \((-1)^2=1\).

Сначала произведение равно \(1\). Для состояния \(-,-,-\) произведение равно \(-1\). Инвариант различен, значит, такое состояние невозможно.

Каждый ход изменяет координату на число, кратное \(5\). Поэтому остаток координаты по модулю \(5\) сохраняется.

Начальная координата имеет остаток \(0\), а \(2026\equiv 1\pmod 5\). Следовательно, точка \(2026\) недостижима.

После хода размеры куч станут \(a-1\) и \(b+1\). Разность старой и новой сумм квадратов равна

\[a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1).\]

Так как \(a\ge b+2\), правая часть положительна. Значит, сумма квадратов строго уменьшается.

Обозначим числа красных, синих и зелёных камней через \(r,b,g\). При ходе, например, \(r\) и \(b\) уменьшаются на \(1\), а \(g\) увеличивается на \(2\). Разность \(r-b\) не меняется, а разности \(b-g\) и \(g-r\) меняются на кратные \(3\). Поэтому остатки всех попарных разностей по модулю \(3\) сохраняются.

В начале \(r-b=20-21=-1\), то есть \(r-b\equiv 2\pmod 3\). Если бы все камни стали одного цвета, то две из величин \(r,b,g\) были бы равны \(0\), а третья — \(63\), поэтому разности были бы кратны \(3\). Противоречие.

При замене пары \((a,b)\) на \((a-b,b)\) при \(a\ge b\) НОД не меняется: \(\gcd(a,b)=\gcd(a-b,b)\). То же верно при замене \(b\) на \(b-a\).

В начале \(\gcd(84,30)=6\). У пары \(7,7\) НОД равен \(7\). Поскольку НОД является инвариантом, такая пара недостижима.

Один ход меняет ровно два знака, значит, произведение всех знаков умножается на \((-1)^2=1\). Поэтому произведение является инвариантом.

В начале произведение равно \(-1\), так как отрицательный знак один. В состоянии, где все знаки положительны, произведение равно \(1\). Инвариант различен, значит, такое состояние недостижимо.

Раскрасим доску в шахматном порядке. Каждый ход коня переводит его на клетку противоположного цвета.

Если путь по всем \(25\) клеткам был бы замкнутым, то он образовал бы цикл нечётной длины \(25\), в котором цвета должны строго чередоваться. Но в замкнутом цикле с чередованием цветов длина должна быть чётной. Противоречие.

Рассмотрим чётность числа чёрных клеток в каждой строке. Один ход затрагивает две клетки в одной выбранной строке и две клетки в другой выбранной строке. Значит, чётность числа чёрных клеток в каждой строке сохраняется. Аналогично сохраняется чётность в каждом столбце.

В начале во всех строках и столбцах чётность равна \(0\). Если есть ровно одна чёрная клетка, то её строка и её столбец имеют нечётную чётность. Это невозможно.

Инверсией называется пара чисел, где большее стоит левее меньшего. Число инверсий — неотрицательное целое число.

Обмен соседней неправильной пары уменьшает число инверсий ровно на \(1\): эта пара перестаёт быть инверсией, а отношения этих двух чисел с остальными числами не меняют общего количества инверсий.

Значит, число инверсий строго убывает и не может убывать бесконечно. Процесс завершится.

Пусть \(S\) — сумма номеров клеток, в которых лежат камни, считая камни с кратностью. Каждый ход увеличивает \(S\) ровно на \(1\).

Если всего камней \(m\), то \(S\le mn\), потому что ни один камень не может оказаться правее \(n\)-й клетки. Значит, \(S\) строго возрастает, но ограничена сверху. Бесконечно много ходов невозможно.

Необходимость: один ход меняет два знака, поэтому чётность числа отрицательных знаков сохраняется. Если в конце отрицательных знаков \(0\), то в начале их должно быть чётное число.

Докажем достаточность. Возьмём остовное дерево графа и выберем в нём корень. Будем обрабатывать листья, кроме корня. Если в листе стоит минус, применим ход к ребру, соединяющему лист с его родителем; знак в листе станет плюсом, а знак родителя изменится. Если в листе плюс, ничего не делаем. После этого лист можно больше не трогать.

Так мы сделаем положительными все вершины, кроме, возможно, корня. Чётность числа отрицательных знаков сохранялась, а перед последним шагом вне корня отрицательных знаков нет. Поэтому корень тоже положителен. Значит, все знаки можно сделать положительными.

Нумеруем строки \(1,\ldots,10\), столбцы \(1,\ldots,14\). Пусть чёрными считаются клетки, для которых \(i+j\) нечётно. Обозначим через \(x_{ij}\) число \(0\) или \(1\), показывающее, отмечена ли клетка.

По модулю \(2\) число отмеченных чёрных клеток равно

\[\sum_{i,j}(i+j)x_{ij}=\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

В каждой строке и в каждом столбце сумма отметок нечётна, то есть равна \(1\) по модулю \(2\). Поэтому искомая чётность равна

\[\sum_{i=1}^{10} i+\sum_{j=1}^{14} j=55+105=160\equiv 0\pmod 2.\]

Значит, отмеченных чёрных клеток чётное число.

В начальной раскраске в каждой строке и каждом столбце чёрных клеток \(0\), то есть чётное число.

Один ход выбирает две строки и две колонки. В каждой выбранной строке меняются цвета ровно двух клеток, поэтому чётность числа чёрных клеток в этой строке сохраняется. В остальных строках ничего не меняется. То же рассуждение верно для столбцов.

Следовательно, после любого числа ходов все строки и столбцы сохраняют чётность \(0\).

Рассмотрим сумму квадратов размеров всех куч. Если камень перекладывается из кучи размера \(a\) в кучу размера \(b\), где \(a\ge b+2\), то вклад этих двух куч меняется с \(a^2+b^2\) на \((a-1)^2+(b+1)^2\). Как было вычислено, старая сумма больше новой на \(2(a-b-1)>0\).

Сумма квадратов — неотрицательное целое число, поэтому она не может строго убывать бесконечно. Процесс закончится.

Если в конечном состоянии две кучи отличались бы хотя бы на \(2\), ход всё ещё был бы разрешён. Значит, в конце любые две кучи отличаются не более чем на \(1\).

НОД пары не меняется при замене \((a,b)\) на \((a-b,b)\) или \((a,b-a)\), потому что общие делители сохраняются в обе стороны.

Если числа не равны, то один ход уменьшает сумму \(a+b\): большее число заменяется на положительно меньшее число. Сумма — положительное целое число, поэтому процесс не может продолжаться бесконечно.

Когда ходов больше нет, числа равны: пусть это \(c,c\). НОД всё время сохранялся, значит, \(c=\gcd(c,c)=\gcd(a,b)=d\). Итак, конечная пара равна \(d,d\).

Необходимость: один ход меняет две клетки в каждой из двух соседних строк и две клетки в каждом из двух соседних столбцов. Поэтому чётность числа чёрных клеток в каждой строке и каждом столбце сохраняется. В начале все эти чётности равны \(0\).

Докажем достаточность. Пусть целевая раскраска имеет чётные строки и столбцы. Будем строить её из белой доски. Для \(i=1,\ldots,m-1\) и \(j=1,\ldots,n-1\) идём по клеткам слева направо, сверху вниз. Если в текущий момент клетка \((i,j)\) отличается от целевой, применяем ход к блоку с левым верхним углом \((i,j)\). После этого клетка \((i,j)\) совпадает с целью, и дальнейшие ходы уже не будут её менять, потому что они начинаются не выше и не левее неё.

После такой процедуры все клетки вне последней строки и последнего столбца совпадают с целью. Остаётся проверить последнюю строку и последний столбец. В каждой строке и каждом столбце текущей доски чётность чёрных клеток чётна, и у целевой доски тоже. Поэтому в каждой уже почти заполненной строке последняя клетка вынуждена совпадать с целевой. Аналогично совпадают клетки последней строки. Значит, вся раскраска достижима.

Нумеруем строки \(1,\ldots,14\), столбцы \(1,\ldots,18\). Пусть белыми считаются клетки, для которых \(i+j\) чётно. Обозначим через \(x_{ij}\) индикатор отмеченности клетки.

Число отмеченных белых клеток по модулю \(2\) равно

\[\sum_{i,j}(1+i+j)x_{ij}.\]

Раскрывая сумму по модулю \(2\), получаем

\[\sum_{i,j}x_{ij}+\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

Общее число отмеченных клеток имеет чётность \(14\), потому что в каждой из \(14\) строк отмечено нечётное число клеток; значит, этот вклад равен \(0\). Строчные и столбцовые суммы отметок нечётны, поэтому остаётся

\[\sum_{i=1}^{14}i+\sum_{j=1}^{18}j=105+171=276\equiv0\pmod2.\]

Следовательно, отмеченных белых клеток чётное число.

Обозначим цвет клетки числом \(0\) для белой и \(1\) для чёрной. Если мы переключали строки с параметрами \(r_i\in\{0,1\}\) и столбцы с параметрами \(c_j\in\{0,1\}\), то цвет клетки \((i,j)\) равен \(r_i+c_j\pmod2\).

Для углов прямоугольника \((i,j),(i,l),(k,j),(k,l)\) сумма цветов равна

\[(r_i+c_j)+(r_i+c_l)+(r_k+c_j)+(r_k+c_l)\equiv0\pmod2.\]

Значит, чёрных углов всегда чётное число.

Докажем обратное. Пусть раскраска \(a_{ij}\) имеет это свойство. Выберем \(r_i=a_{i1}\) для каждой строки и \(c_j=a_{1j}+a_{11}\) для каждого столбца. Тогда для клетки \((i,j)\) прямоугольное условие, применённое к строкам \(1,i\) и столбцам \(1,j\), даёт

\[a_{ij}+a_{i1}+a_{1j}+a_{11}\equiv0\pmod2.\]

Отсюда \(a_{ij}=r_i+c_j\pmod2\). Значит, достаточно переключить все строки с \(r_i=1\) и все столбцы с \(c_j=1\). Раскраска достижима.

Если красных рёбер не больше \(2\) и синих рёбер не больше \(2\), то всего рёбер не больше \(4\). Но их \(5\). Значит, хотя бы один цвет встречается не менее \(3\) раз.

У треугольника \(3\) ребра и только \(2\) цвета. По принципу Дирихле два ребра имеют один цвет.

Выберем вершину \(v\). Из неё выходят \(3\) ребра двух цветов. По принципу Дирихле два из них одного цвета, скажем \(va\) и \(vb\).

Тогда \(a-v-b\) — путь из двух рёбер одного цвета.

Расположим вершины как правильный пятиугольник. Пять сторон покрасим в красный цвет, пять диагоналей — в синий.

Красный граф является циклом длины \(5\), поэтому красного треугольника нет. Синий граф тоже является циклом длины \(5\), поэтому синего треугольника нет.

Если красных рёбер не больше \(m-1\) и синих не больше \(m-1\), то всего рёбер не больше \(2m-2\). Но рёбер \(2m-1\). Значит, один цвет встречается хотя бы \(m\) раз.

Выберем вершину \(v\). Из неё выходит \(5\) рёбер, поэтому хотя бы \(3\) из них одного цвета. Пусть это красные рёбра к вершинам \(a,b,c\).

Если хотя бы одно из рёбер \(ab,bc,ca\) красное, то вместе с \(v\) оно образует красный треугольник. Если ни одно из этих рёбер не красное, то все они синие, и вершины \(a,b,c\) образуют синий треугольник.

Построим граф на \(6\) вершинах: вершины — люди. Ребро красное, если люди знакомы, и синее, если не знакомы.

По задаче о \(K_6\) в такой раскраске есть одноцветный треугольник. Красный треугольник означает \(3\) попарно знакомых людей, синий — \(3\) попарно незнакомых.

Из задачи о \(K_6\) следует, что при \(6\) вершинах одноцветный треугольник неизбежен, значит, \(R(3,3)\le6\).

С другой стороны, рёбра \(K_5\) можно раскрасить так: стороны пятиугольника красные, диагонали синие. Тогда каждый цвет образует цикл длины \(5\), и одноцветного треугольника нет. Значит, \(R(3,3)>5\).

Итак, \(R(3,3)=6\).

Возьмём вершину \(v\). Если из неё выходят три красных ребра к \(a,b,c\), то среди \(a,b,c\) не может быть красного ребра, иначе возникнет красный треугольник с \(v\). Значит, все рёбра между \(a,b,c\) синие, и получается синий треугольник. Противоречие.

Следовательно, красная степень любой вершины не больше \(2\). Аналогично синяя степень не больше \(2\). Но всего из вершины выходит \(n-1\) рёбер, значит, \(n-1\le4\), откуда \(n\le5\).

Из любой вершины выходит \(2m-1\) рёбер. По усиленному принципу Дирихле среди этих рёбер есть хотя бы \(m\) рёбер одного цвета. Поэтому подходит даже произвольная вершина.

Покажем, что \(t\) вершин достаточно. В красно-синей раскраске \(K_t\), если есть красное ребро, то есть красный \(K_2\). Если красных рёбер нет, то все рёбра синие, и все \(t\) вершин образуют синий \(K_t\).

Меньше \(t\) вершин недостаточно: покрасим все рёбра в синий цвет. Тогда красного \(K_2\) нет, а синего \(K_t\) тоже нет, потому что вершин меньше \(t\). Значит, \(R(2,t)=t\).

Среди выбранных \(6\) человек по факту \(R(3,3)=6\) уже есть либо \(3\) попарно знакомых, либо \(3\) попарно незнакомых. Значит, среди всех \(7\) человек такая тройка тоже есть.

Число \(7\) не является точным порогом, потому что тот же результат гарантирован уже для \(6\) человек.

Пусть \(N=R(s-1,t)+R(s,t-1)\), и рёбра \(K_N\) покрашены в красный и синий цвета. Выберем вершину \(v\). Остальные \(N-1\) вершин делятся на красных соседей \(v\) и синих соседей \(v\).

Если красных соседей не меньше \(R(s-1,t)\), то внутри них есть либо красный \(K_{s-1}\), либо синий \(K_t\). В первом случае вместе с \(v\) получаем красный \(K_s\), во втором уже есть синий \(K_t\).

Если красных соседей меньше \(R(s-1,t)\), то синих соседей не меньше \(R(s,t-1)\). Тогда внутри них есть либо красный \(K_s\), либо синий \(K_{t-1}\), который вместе с \(v\) даёт синий \(K_t\).

Во всех случаях нужная структура существует.

По рекурсии Рамсея имеем

\[R(3,4)\le R(2,4)+R(3,3).\]

Из \(R(2,4)=4\) и \(R(3,3)=6\) получаем \(R(3,4)\le10\). Значит, в любой красно-синей раскраске рёбер \(K_{10}\) есть либо красный \(K_3\), либо синий \(K_4\).

Переведём это на язык людей: красное ребро — знакомство, синее — незнакомство. Получаем либо \(3\) попарно знакомых, либо \(4\) попарно незнакомых.

По рекурсии Рамсея

\[R(4,4)\le R(3,4)+R(4,3).\]

По симметрии \(R(4,3)=R(3,4)\). Так как \(R(3,4)\le10\), получаем

\[R(4,4)\le10+10=20.\]

Покрасим ребро между двумя людьми в красный цвет, если они знакомы, и в синий, если не знакомы. По оценке \(R(4,4)\le20\) в \(K_{20}\) есть либо красный \(K_4\), либо синий \(K_4\).

Красный \(K_4\) означает \(4\) попарно знакомых людей, синий \(K_4\) — \(4\) попарно незнакомых.

Если красный граф связен, всё доказано. Пусть он не связен. Тогда его вершины разбиваются на несколько красных компонент.

Любое ребро между двумя разными красными компонентами не может быть красным, иначе эти компоненты соединились бы. Значит, все такие рёбра синие.

Покажем, что синий граф связен. Если две вершины лежат в разных красных компонентах, между ними есть синее ребро. Если они лежат в одной красной компоненте, возьмём вершину из другой красной компоненты; обе связи с ней синие, поэтому есть синий путь длины \(2\). Следовательно, синий граф связен.

Переведём задачу в раскраску рёбер \(K_9\): красный цвет — знакомство, синий — незнакомство. Предположим, что нет красного треугольника и нет синего \(K_4\). Рассмотрим красный граф \(G\).

Граф \(G\) не содержит треугольников. Кроме того, в нём нет независимого множества из \(4\) вершин, потому что такое множество соответствовало бы синему \(K_4\).

Покажем, что степень любой вершины в \(G\) не больше \(3\). Действительно, если у вершины \(v\) есть \(4\) красных соседа, то между этими соседями не может быть красных рёбер, иначе возникнет красный треугольник с \(v\). Значит, эти \(4\) соседа образуют независимое множество в \(G\), то есть синий \(K_4\). Противоречие.

Если бы степень каждой вершины была ровно \(3\), сумма степеней равнялась бы \(9\cdot3=27\), что невозможно, потому что сумма степеней графа чётна. Значит, есть вершина \(v\) степени не больше \(2\).

Рассмотрим вершины, не смежные с \(v\) в красном графе. Их не меньше \(9-1-2=6\). В индуцированном на них красном графе также нет красного треугольника. По факту \(R(3,3)=6\), среди этих \(6\) вершин найдутся либо красный треугольник, либо независимая тройка. Красного треугольника нет, значит, есть независимая тройка.

Эта независимая тройка вместе с \(v\) образует независимое множество из \(4\) вершин в красном графе, то есть синий \(K_4\). Противоречие. Следовательно, нужная группа людей существует.

Выберем вершину \(v\). Из неё выходит \(16\) рёбер трёх цветов, поэтому по принципу Дирихле хотя бы \(6\) из них имеют один цвет. Пусть это красные рёбра к множеству \(A\) из \(6\) вершин.

Если внутри \(A\) есть красное ребро, то оно вместе с \(v\) образует красный треугольник. Если красных рёбер внутри \(A\) нет, то все рёбра внутри \(A\) покрашены двумя оставшимися цветами.

По факту \(R(3,3)=6\) в двухцветной раскраске рёбер на \(6\) вершинах есть одноцветный треугольник. Он будет одноцветным в одном из двух оставшихся цветов. Значит, в исходной трёхцветной раскраске одноцветный треугольник тоже существует.

Докажем, что красный или синий граф связен. Если красный граф связен, то в нём есть остовное дерево, и оно красное.

Пусть красный граф не связен. Тогда его вершины разбиваются на красные компоненты. Любое ребро между разными красными компонентами синее, иначе эти компоненты были бы одной компонентой. Поэтому синий граф связен: между разными красными компонентами есть синие рёбра, а две вершины внутри одной красной компоненты соединяются синим путём длины \(2\) через вершину из другой компоненты.

Значит, синий граф связен, а в любом связном графе есть остовное дерево. Это дерево будет синим и проходит через все вершины.

При подсчёте суммы степеней каждое ребро учитывается ровно два раза: по одному разу у каждого своего конца. Поэтому сумма степеней равна \(2m\).

Сумма степеней равна \(2m\), значит, она чётна. Сумма степеней вершин чётной степени чётна. Поэтому сумма степеней вершин нечётной степени тоже чётна. Сумма нечётных чисел чётна только тогда, когда их количество чётно.

Выберем самый длинный простой путь в дереве. Если у его конечной вершины есть сосед вне пути, путь можно продолжить. Если она соединена с другой вершиной пути, кроме соседней, возникнет цикл. Значит, её степень равна \(1\). То же верно для другого конца пути. Получаем два листа.

В любом связном графе есть остовное дерево. Остовное дерево содержит все \(n\) вершин и имеет ровно \(n-1\) рёбер. Исходный граф содержит все рёбра этого дерева и, возможно, ещё рёбра. Поэтому в нём не меньше \(n-1\) рёбер.

Пусть новое ребро соединяет вершины \(u\) и \(v\). В дереве между \(u\) и \(v\) был ровно один простой путь. Этот путь вместе с новым ребром образует цикл.

Другого цикла быть не может: любой цикл, появившийся после добавления, обязан использовать новое ребро, потому что раньше циклов не было. Тогда оставшаяся часть цикла была бы другим путём между \(u\) и \(v\) в дереве, что невозможно.

Пусть компоненты имеют \(n_1,n_2,\ldots,n_c\) вершин. Каждая компонента — дерево, поэтому в ней \(n_i-1\) рёбер. Всего рёбер

\[\sum_{i=1}^c(n_i-1)=\sum_{i=1}^c n_i-c=n-c.\]

Пусть удаляемое ребро соединяет \(u\) и \(v\). Так как оно лежит на цикле, после удаления этого ребра на оставшейся части цикла всё ещё есть путь из \(u\) в \(v\).

Любой путь в исходном графе, использовавший ребро \(uv\), можно заменить: вместо \(uv\) пройти по этому обходному пути. Значит, связность не нарушается.

Предположим, что в графе есть цикл. Удалим одно ребро этого цикла; связность сохранится. Тогда получим связный граф на \(n\) вершинах с \(n-2\) рёбрами.

Но связный граф на \(n\) вершинах имеет не меньше \(n-1\) рёбер. Противоречие. Значит, циклов нет, и граф является деревом.

Возьмём остовное дерево графа. В нём \(n-1\) рёбер, значит, в исходном графе есть ровно одно ребро сверх остовного дерева. Добавление одного ребра к дереву создаёт ровно один цикл.

Любой цикл исходного графа должен использовать это единственное лишнее ребро, потому что в дереве циклов нет. Поэтому цикл ровно один.

Пусть граф разбит на доли \(A\) и \(B\), и каждое ребро соединяет вершину из \(A\) с вершиной из \(B\). При движении по циклу вершины по очереди попадают то в \(A\), то в \(B\). После нечётного числа шагов мы оказались бы в другой доле, а для замыкания цикла нужно вернуться в исходную вершину и исходную долю. Значит, длина цикла чётна.

Покрасим вершины с чётным расстоянием от \(v\) в одну долю, а с нечётным — в другую. Нужно доказать, что ребро не соединяет вершины одной доли.

Пусть ребро \(xy\) соединяет две вершины одинаковой чётности расстояний. Возьмём кратчайшие пути от \(v\) к \(x\) и от \(v\) к \(y\). У этих путей есть общий начальный участок; после его удаления остаются два пути одинаковой чётности суммарной длины. Добавив ребро \(xy\), получаем нечётный цикл. Это запрещено. Значит, каждое ребро соединяет разные доли.

Если путь не замкнут, то у каждой промежуточной вершины использованные рёбра разбиваются на пары: вошли и вышли. Поэтому промежуточные вершины имеют чётные степени. Нечётными могут быть только начало и конец пути.

Если путь замкнут, то у начальной вершины входы и выходы тоже образуют пары, поэтому все степени чётны. Значит, нечётных вершин либо \(0\), либо \(2\).

Пусть \(x\) — лист, а \(y\) — его единственный сосед. В совершенном паросочетании вершина \(x\) должна быть покрыта каким-то ребром. Единственное ребро, инцидентное \(x\), — это \(xy\). Следовательно, ребро \(xy\) обязательно входит в паросочетание.

Предположим, что существует ребро \(uv\), оба конца которого не являются концами выбранных рёбер. Тогда \(uv\) не пересекается ни с одним ребром паросочетания, поэтому его можно добавить. Это противоречит максимальности по включению.

Значит, каждое ребро имеет хотя бы один конец среди концов выбранных рёбер.

Каждое ребро имеет один конец в \(A\) и один конец в \(B\). Считая рёбра по вершинам доли \(A\), получаем \(d|A|\). Считая по вершинам доли \(B\), получаем \(d|B|\). Это одно и то же число рёбер, значит, \(d|A|=d|B|\). Так как \(d>0\), имеем \(|A|=|B|\).

Начнём из любой вершины и идём по неиспользованным рёбрам, пока можем. Так как степени чётны, застрять в вершине, отличной от начальной, невозможно: каждый вход требует ещё один выход. Поэтому получим замкнутый обход.

Выберем замкнутый обход с максимальным числом рёбер. Если он использует не все рёбра, то из связности найдётся вершина обхода, из которой выходит неиспользованное ребро в ещё неиспользованную часть. Начиная с неё и двигаясь по неиспользованным рёбрам, снова получим замкнутый обход, который можно вставить в первый. Это увеличит число использованных рёбер, противоречие.

Значит, максимальный обход использует все рёбра.

Пусть \(f\) — число граней. По формуле Эйлера \(n-m+f=2\). Так как граф простой и \(n\ge3\), каждая грань ограничена не менее чем тремя рёбрами. При суммировании длин границ граней каждое ребро считается дважды, значит, \(3f\le2m\).

Тогда \(f\le\frac{2m}{3}\), и \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Отсюда \(m\le3n-6\).

Необходимость доказана через пары вход-выход: нечётными могут быть только начало и конец незамкнутого эйлерова пути, а у цикла нечётных вершин нет.

Докажем достаточность. Если нечётных вершин нет, то по лемме о чётных степенях в связном графе есть эйлеров цикл.

Если нечётных вершин ровно две, обозначим их \(a\) и \(b\). Добавим новое ребро \(ab\). Теперь все степени стали чётными, поэтому в новом графе есть эйлеров цикл. Удалим из этого цикла добавленное ребро. Оставшаяся последовательность рёбер является эйлеровым путём исходного графа от \(a\) к \(b\).

Пусть \(f\) — число граней. По формуле Эйлера \(n-m+f=2\). В двудольном графе нет нечётных циклов, в частности нет треугольников. Поэтому граница каждой грани имеет длину хотя бы \(4\).

Сумма длин границ граней равна \(2m\), значит, \(4f\le2m\), то есть \(f\le\frac{m}{2}\). Тогда \(2=n-m+f\le n-m+\frac{m}{2}=n-\frac{m}{2}\). Отсюда \(m\le2n-4\).

В дереве нет циклов, значит, нет нечётных циклов. Поэтому дерево двудольно: его вершины можно разбить на две доли \(A\) и \(B\), так что каждое ребро идёт между долями.

Внутри каждой доли рёбер нет, значит, каждая доля является независимым множеством. Из двух чисел \(|A|\) и \(|B|\), сумма которых равна \(n\), одно не меньше \(\lceil n/2\rceil\). Эта большая доля и даёт нужное независимое множество.

Любые два ребра звезды имеют общий центр, поэтому в паросочетание нельзя взять два ребра. Одно ребро взять можно. Ответ: \(1\).

Рёбра паросочетания не имеют общих концов. Поэтому \(a\) покрытых левых вершин соединены с \(a\) различными вершинами правой доли. Значит, справа есть хотя бы \(a\) вершин.

Каждая вершина из \(S\) покрыта своим ребром паросочетания. Эти рёбра ведут в разные вершины правой доли, и все эти вершины лежат в \(N(S)\). Поэтому в \(N(S)\) есть как минимум \(|S|\) вершин.

Например, можно выбрать \(1\in A_1\), \(2\in A_2\), \(3\in A_3\). Все представители различны, значит, это система различных представителей.

Если две непокрытые вершины соединены ребром, это ребро не имеет общих концов с выбранными рёбрами. Его можно добавить к паросочетанию, противоречие.

Для одного кружка вариантов \(2\). Для любых двух кружков объединение списков содержит все три имени или хотя бы два имени. Для трёх кружков объединение равно \(\{a,b,c\}\), имеет размер \(3\). Условие Холла выполнено, значит, существует система различных представителей. Например, \(A_1\to a\), \(A_2\to b\), \(A_3\to c\).

Возьмём любое \(S\) в левой доле. Из \(S\) выходит не меньше \(3|S|\) рёбер. Все они входят в \(N(S)\), а каждая вершина из \(N(S)\) принимает не больше \(3\) таких рёбер. Значит, \(3|S|\le3|N(S)|\), откуда \(|N(S)|\ge |S|\).

Условие Холла выполнено, следовательно, есть паросочетание, покрывающее левую долю.

Для любого \(S\) слева из него выходит ровно \(d|S|\) рёбер. Все они входят в \(N(S)\), и каждая вершина из \(N(S)\) имеет степень \(d\), значит, принимает не больше \(d\) этих рёбер. Поэтому \(d|S|\le d|N(S)|\), откуда \(|N(S)|\ge |S|\). По теореме Холла нужное паросочетание существует.

Удалим произвольный элемент \(x\). Возьмём любые \(k\) множеств. До удаления их объединение имело размер не меньше \(k+1\). После удаления \(x\) размер объединения уменьшится не более чем на \(1\), значит, останется не меньше \(k\) элементов.

Условие Холла выполнено для нового семейства, поэтому система различных представителей существует.

Удалим из паросочетания выбранные рёбра этого пути и добавим невыбранные рёбра пути. Так как путь чередуется, общих концов у новых выбранных рёбер не появится.

Путь начинается и заканчивается непокрытыми вершинами, поэтому невыбранных рёбер на пути на одно больше, чем выбранных. Следовательно, размер паросочетания увеличится на \(1\).

Построим двудольный граф: слева доклады, справа дни, ребро означает, что доклад можно поставить в этот день. Условие задачи говорит, что для любого набора \(S\) докладов множество соседних дней имеет размер не меньше \(|S|\). По теореме Холла есть паросочетание, покрывающее все доклады. Оно и задаёт расписание.

Если представители выбраны, то любые \(k\) секций имеют \(k\) разных представителей, все они лежат в объединении этих секций. Поэтому объединение содержит не меньше \(k\) школьников.

Обратно, условие про объединения — это условие Холла для множеств школьников, соответствующих секциям. По теореме Холла существует система различных представителей.

Удалим две правые вершины. Для любого непустого \(S\subseteq A\) его множество соседей потеряет не больше двух вершин. Поэтому новый размер соседства не меньше \(|S|+2-2=|S|\).

Условие Холла сохраняется, значит, существует паросочетание, покрывающее левую долю.

Для любого \(S\) слева из него выходит не меньше \(5|S|\) рёбер. Все эти рёбра входят в \(N(S)\), а каждая правая вершина принимает не больше \(4\) таких рёбер. Значит, \(5|S|\le4|N(S)|\), откуда \(|N(S)|\ge \frac54|S|\ge |S|\).

По теореме Холла есть паросочетание, покрывающее левую долю.

Пусть доли \(A\) и \(B\). Считая рёбра по долям, получаем \(d|A|=d|B|\), значит, \(|A|=|B|\).

По задаче о регулярном двудольном графе есть паросочетание, покрывающее \(A\). Так как доли равны, оно покрывает и \(B\). Следовательно, паросочетание совершенное.

Построим двудольный граф: экзамен соединён с днём, если его можно провести в этот день. Проверим условие Холла.

Для одного экзамена доступно хотя бы \(n-1\) дней, а при \(n\ge2\) это не меньше \(1\). Если взято \(k\ge2\) экзаменов, то любой день доступен хотя бы одному из них: ведь один день может быть запрещён не более чем для одного экзамена. Значит, объединение доступных дней равно всем \(n\) дням, а \(n\ge k\).

Условие Холла выполнено для любого набора экзаменов. Следовательно, существует расписание с разными днями.

По определению увеличивающий путь начинается и заканчивается непокрытыми вершинами, а рёбра на нём чередуются. Переключение статуса рёбер вдоль пути сохраняет свойство быть паросочетанием и добавляет на одно ребро больше, чем удаляет. Значит, размер паросочетания увеличивается на \(1\). Следовательно, исходное паросочетание не было максимальным по размеру.

Если увеличивающий путь есть, то размер паросочетания можно увеличить, значит, оно не максимально.

Обратно, пусть существует паросочетание \(M'\) большего размера, чем \(M\). Рассмотрим граф, состоящий из рёбер, которые входят ровно в одно из \(M\) и \(M'\). В этом графе степени вершин не превосходят \(2\), поэтому его компоненты — пути и циклы, где рёбра из \(M\) и \(M'\) чередуются.

Так как \(|M'|>|M|\), в какой-то компоненте рёбер из \(M'\) больше, чем рёбер из \(M\). Цикл имеет поровну рёбер обоих типов, значит, это путь. Он начинается и заканчивается рёбрами из \(M'\), а его концы не покрыты \(M\). Следовательно, это увеличивающий путь относительно \(M\). Противоречие отсутствию увеличивающих путей.

В \(d\)-регулярном двудольном графе есть совершенное паросочетание. Удалим его рёбра. У каждой вершины степень уменьшится на \(1\), поэтому оставшийся граф будет \((d-1)\)-регулярным и двудольным.

Повторяем рассуждение: находим совершенное паросочетание, удаляем его. Через \(d\) шагов все рёбра будут удалены, а найденные паросочетания попарно не пересекаются и покрывают все рёбра.

Возьмём любые \(k\) множеств. В них суммарно не меньше \(rk\) вхождений элементов, потому что каждое множество имеет размер не меньше \(r\). Каждый элемент из их объединения может быть посчитан не более \(r\) раз, так как он принадлежит не более чем \(r\) множествам всего.

Если размер объединения равен \(u\), то \(rk\le ru\), значит, \(u\ge k\). Условие Холла выполнено для любых \(k\) множеств. Следовательно, система различных представителей существует.

В произведении \((1+x)^9\) каждый из девяти множителей дает выбор: взять \(1\) или \(x\). Степень \(4\) получается тогда и только тогда, когда \(x\) выбран ровно из четырех множителей. Поэтому коэффициент равен \(\binom{9}{4}=126\). Он считает число четырехэлементных подмножеств девятиэлементного множества.

Искомое число равно коэффициенту при \(x^{14}\) в \(\frac{1}{(1-x)^3}\). Так как \(\frac{1}{(1-x)^3}=\sum_{n\ge 0}\binom{n+2}{2}x^n\), получаем \(\binom{16}{2}=120\).

Без верхней границы решений \(\binom{11}{2}=55\). Если \(a\ge 5\), то \(a'=a-5\) дает \(a'+b+c=4\), откуда \(\binom{6}{2}=15\) решений. Таких переменных три, а две переменные не могут одновременно быть не меньше \(5\), потому что сумма была бы хотя бы \(10\). Ответ: \(55-3\cdot 15=10\).

Нужен коэффициент при \(x^8\) в \(\prod_{i=1}^7(1+x^i)\). Сумма \(8\) получается так: \(1+7\), \(2+6\), \(3+5\), \(1+2+5\), \(1+3+4\). Других вариантов нет: если \(4\) выбран с \(2\), то остается \(2\), но повторять \(2\) нельзя; если выбран \(6\), то остается только \(2\), и так далее. Ответ: \(5\).

С одной стороны, \((1+x)^r(1+x)^s=(1+x)^{r+s}\), поэтому коэффициент при \(x^n\) равен \(\binom{r+s}{n}\). С другой стороны, чтобы получить \(x^n\), можно взять \(x^k\) из первого множителя и \(x^{n-k}\) из второго. Это дает сумму \(\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}\). Коэффициенты одного и того же многочлена равны, значит, тождество доказано.

Производящая функция равна \(\frac{1}{(1-x^2)^4}\). Нужно найти коэффициент при \(x^{18}\), то есть коэффициент при \(y^9\) в \(\frac{1}{(1-y)^4}\). Он равен \(\binom{9+3}{3}=\binom{12}{3}=220\).

Число строк с \(k\) единицами равно \(\binom{n}{k}\). Поэтому нужно найти сумму коэффициентов при четных степенях в \((1+x)^n\). Она равна \(\frac{(1+1)^n+(1-1)^n}{2}\). При \(n\ge 1\) получаем \(\frac{2^n+0}{2}=2^{n-1}\).

Пустая композиция для \(0\) дает \(c_0=1\). Для \(n\ge 2\) первая часть равна \(1\) или \(2\), значит, \(c_n=c_{n-1}+c_{n-2}\), причем \(c_1=1\). Для ряда получаем \(C(x)=1+xC(x)+x^2C(x)\), откуда \(C(x)=\frac{1}{1-x-x^2}\). Если \(F_0=0\), \(F_1=1\), то \(c_n=F_{n+1}\).

Без ограничений решений \(\binom{24}{4}=10626\). Если одна коробка содержит хотя бы \(7\), после вычитания \(7\) остается сумма \(13\), что дает \(\binom{17}{4}=2380\) решений; таких коробок \(5\). Если две коробки содержат хотя бы \(7\), остается сумма \(6\), что дает \(\binom{10}{4}=210\) решений; пар коробок \(\binom{5}{2}=10\). Три коробки уже невозможны. Ответ: \(10626-5\cdot 2380+10\cdot 210=826\).

Разложение \(\frac{1}{(1-x)^2(1-x^3)}=(1+x+x^2+\cdots)^2(1+x^3+x^6+\cdots)\) показывает, что коэффициент равен числу троек \((a,b,c)\) таких, что \(a+b+3c=10\). При \(c=0,1,2,3\) получаем соответственно \(11,8,5,2\) решений для \(a+b\). Сумма равна \(11+8+5+2=26\).

Каждое слагаемое \(i\) можно взять либо один раз, либо не брать, поэтому производящая функция равна \(\prod_{i=1}^{11}(1+x^i)\). Перечислим разбиения: \(11\), \(10+1\), \(9+2\), \(8+3\), \(8+2+1\), \(7+4\), \(7+3+1\), \(6+5\), \(6+4+1\), \(6+3+2\), \(5+4+2\), \(5+3+2+1\). Их \(12\).

Коэффициент \(c_k\) равен числу наборов \((a_1,\ldots,a_n)\) таких, что \(0\le a_i\le m\) и \(a_1+\cdots+a_n=k\). Каждому такому набору сопоставим \((m-a_1,\ldots,m-a_n)\). Все новые числа также лежат от \(0\) до \(m\), а их сумма равна \(mn-k\). Это обратимое соответствие, значит, \(c_k=c_{mn-k}\).

Пусть \(b_i=a_i-1\). Тогда \(b_1+\cdots+b_6=18\) и \(0\le b_i\le 6\). Без верхней границы решений \(\binom{23}{5}=33649\). Если один \(b_i\ge 7\), остается сумма \(11\), значит, \(\binom{16}{5}=4368\) решений; таких переменных \(6\). Если два \(b_i\ge 7\), остается сумма \(4\), значит, \(\binom{9}{5}=126\) решений; пар \(\binom{6}{2}=15\). Три переменные не могут быть не меньше \(7\), потому что сумма стала бы отрицательной после вычитания. Ответ: \(33649-6\cdot 4368+15\cdot 126=9331\).

Без верхней границы решений \(\binom{19}{7}=50388\). Если выбранная переменная не меньше \(4\), после вычитания \(4\) остается сумма \(8\), что дает \(\binom{15}{7}=6435\) решений; таких переменных \(8\). Для двух переменных остается сумма \(4\), что дает \(\binom{11}{7}=330\) решений; пар \(\binom{8}{2}=28\). Для трех переменных остается сумма \(0\), что дает \(1\) решение; троек \(\binom{8}{3}=56\). Четыре переменные невозможны. Искомый коэффициент равен

\[50388-8\cdot 6435+28\cdot 330-56=8092.\]

Пусть выбраны \(i_1<\cdots

Если в покрытии ровно \(k\) домино, то оставшихся одиночных клеток \(n-2k\). Сожмем каждое домино в один блок. Тогда всего блоков \(k+(n-2k)=n-k\), и нужно выбрать, какие \(k\) из них являются домино. Это можно сделать \(\binom{n-k}{k}\) способами. Обратное восстановление однозначно: выбранные блоки разворачиваются в домино, остальные остаются одиночными клетками.

Разбиения на различные части кодируются произведением \(\prod_{i\ge 1}(1+x^i)\), потому что каждую часть \(i\) можно взять не больше одного раза. Используем тождество \(1+x^i=\frac{1-x^{2i}}{1-x^i}\):

\[\prod_{i\ge 1}(1+x^i)=\frac{\prod_{i\ge 1}(1-x^{2i})}{\prod_{i\ge 1}(1-x^i)}.\]

В знаменателе есть множители для всех положительных \(i\), а в числителе сокращаются все четные множители. Остается \(\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}\), то есть производящая функция разбиений на нечетные части. Коэффициенты при \(x^n\) равны.

Положим \(y_i=5-x_i\). Тогда \(0\le y_i\le 5\), \(y_1+\cdots+y_8=10\). Условие \(x_1+x_2+x_3\) четно эквивалентно тому, что \(15-(y_1+y_2+y_3)\) четно, то есть \(y_1+y_2+y_3\) нечетно.

Пусть \(A_3(t)\) - число троек от \(0\) до \(5\) с суммой \(t\), а \(A_5(u)\) - число пятерок от \(0\) до \(5\) с суммой \(u\). Нужно сложить \(A_3(t)A_5(10-t)\) по нечетным \(t\). Коэффициенты из \((1+x+\cdots+x^5)^3\) и \((1+x+\cdots+x^5)^5\) дают:

\[3\cdot 540+10\cdot 305+21\cdot 126+27\cdot 35+25\cdot 5=8386.\]

Ответ: \(8386\).

Пусть \(\omega\ne 1\) - кубический корень из единицы, так что \(1+\omega+\omega^2=0\). Если \(F(t)=\prod_{j=1}^{3m}(1+t^j)\), то число коэффициентов со степенью, делящейся на \(3\), равно

\[\frac{F(1)+F(\omega)+F(\omega^2)}{3}.\]

Имеем \(F(1)=2^{3m}\). Среди чисел \(1,\ldots,3m\) по \(m\) чисел каждого остатка \(0,1,2\) по модулю \(3\). Поэтому

\[F(\omega)=(1+1)^m(1+\omega)^m(1+\omega^2)^m=2^m((1+\omega)(1+\omega^2))^m.\]

Но \((1+\omega)(1+\omega^2)=1+\omega+\omega^2+\omega^3=1\), значит, \(F(\omega)=2^m\). Аналогично \(F(\omega^2)=2^m\). Получаем \(\frac{2^{3m}+2^m+2^m}{3}=\frac{2^{3m}+2^{m+1}}{3}\).

Пусть \(a_i\in\{0,1,2,3\}\) - сколько грузов веса \(2^i\) взято. Нужно решить \(\sum_{i=0}^{m-1}a_i2^i=2^m-1\), то есть получить двоичную запись из \(m\) единиц.

Считаем слева направо по разрядам снизу вверх. Пусть перед очередным разрядом перенос равен \(0\) или \(1\). Если перенос \(0\), чтобы получить единицу в разряде, нужно взять \(a_i=1\) и оставить перенос \(0\), либо \(a_i=3\) и создать перенос \(1\). Если перенос \(1\), нужно взять \(a_i=0\) и получить перенос \(0\), либо \(a_i=2\) и оставить перенос \(1\). Поэтому после каждого из \(m\) разрядов число способов прийти в состояние переноса \(0\) равно числу способов прийти в состояние переноса \(1\), и оба равны сумме двух предыдущих состояний.

После первого разряда получаем по \(1\) способу в состояниях \(0\) и \(1\). После \(m\) разрядов в каждом состоянии \(2^{m-1}\) способов. В конце перенос должен быть \(0\), иначе сумма превысит \(2^m-1\). Значит, ответ \(2^{m-1}\).