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

Всего \(6+5=11\) карточек, значит одну карточку можно выбрать \(11\) способами.

Для каждого из \(4\) супов есть \(3\) варианта второго блюда. Всего \(4\cdot3=12\) обедов.

Десятки выбираются \(5\) способами, единицы — \(4\) способами. Всего \(5\cdot4=20\).

Каждый элемент либо входит, либо не входит в подмножество, значит всего \(2^6=64\) подмножества. Пустое одно, поэтому непустых \(64-1=63\).

Число \(a\) может быть \(1,2,3,4,5,6\). После выбора \(a\) число \(b=7-a\) положительно и определяется однозначно. Ответ: \(6\).

Если последняя цифра \(0\), сотни выбираются \(5\) способами, десятки \(4\): \(20\). Если последняя \(2\) или \(4\), сотни нельзя выбрать \(0\) и нельзя выбрать последнюю цифру: \(4\) способа, десятки \(4\) способа. Для двух таких случаев \(2\cdot4\cdot4=32\). Всего \(52\).

Нужно расположить \(2\) шага вверх среди \(5\) шагов пути. Это можно сделать \(10\) способами: позиции двух шагов вверх выбираются из пяти.

Первая буква: \(3\) варианта. Каждая из следующих трёх букв: \(2\) варианта. Всего \(3\cdot2^3=24\).

Кратных \(3\): \(66\). Кратных \(5\): \(40\). Кратных обоим, то есть \(15\): \(13\). Ответ \(66+40-13=93\).

Председателя можно выбрать \(12\) способами, после этого секретаря \(11\) способами. Всего \(12\cdot11=132\).

Всего команд из \(7\) человек по \(3\): \(35\). Команд только из мальчиков: \(4\). Значит нужных команд \(35-4=31\).

Первую полосу выбираем \(4\) способами. Вторую — \(3\), третью — \(3\). Всего \(4\cdot3\cdot3=36\).

Если последняя цифра \(0\), первая выбирается \(7\) способами, затем \(6\) и \(5\): \(210\). Если последняя цифра \(5\), первая выбирается из \(1,2,3,4,6,7\): \(6\) способов, затем \(6\) и \(5\): \(180\). Всего \(390\).

Выбираем \(3\) позиции из \(10\) для единиц; остальные позиции заняты нулями. Получаем \(120\) строк.

Всего \(3^5=243\). Без \(A\): \(2^5=32\). Без \(B\): \(32\). Без обеих букв — только \(CCCCC\), один вариант. Ответ \(243-32-32+1=180\).

Всего путей \(35\): нужно выбрать позиции трёх шагов вверх среди семи. Через \((2,1)\): до этой точки \(3\) пути, после неё до \((4,3)\) — \(6\) путей. Запрещённых \(18\). Ответ \(35-18=17\).

Среди чисел от \(1\) до \(20\) есть \(10\) чётных и \(10\) нечётных. Пары с чётной суммой: оба чётные \(10\cdot10\) или оба нечётные \(10\cdot10\). Всего \(200\).

Нужно выбрать любые \(3\) цифры из \(1,2,\ldots,9\). После выбора они ставятся в единственном возрастающем порядке. Таких наборов \(84\).

После обязательного размещения остаётся \(2\) шара, которые можно распределить по \(3\) коробкам. Возможности: оба в одну коробку — \(3\) способа; по одному в две коробки — \(3\) способа. Всего \(6\).

В сетке \(4\) на \(5\) клеток есть \(5\) горизонтальных и \(6\) вертикальных линий. Выбираем \(2\) вертикальные линии и \(2\) горизонтальные: \(15\cdot10=150\).

В десятичной системе \(5\) чётных цифр и \(5\) нечётных. Для шести цифр сумма чётна, если нечётных цифр \(2\) или \(4\). При \(2\) нечётных наборах без нуля \(10\), с нулём \(40\); вклад \(10\cdot720+40\cdot600=31200\). При \(4\) нечётных наборах без нуля \(30\), с нулём \(20\); вклад \(30\cdot720+20\cdot600=33600\). Итого \(64800\).

Всего \(2^{20}\) подмножеств. Без чётных: можно выбирать только из \(10\) нечётных, \(2^{10}\). Без кратных \(5\): \(16\) доступных чисел, \(2^{16}\). Без чётных и без кратных \(5\): остаются \(8\) нечётных, не кратных \(5\), значит \(2^8\). Ответ: \(2^{20}-2^{10}-2^{16}+2^8\).

Если все \(5\) символов одинаковые, есть \(4\) строки. Если кратности \(3\) и \(2\), выбираем букву, которая встречается \(3\) раза: \(4\) способа, букву, которая встречается \(2\) раза: \(3\) способа, позиции для первой буквы: \(10\) способов. Получаем \(4+4\cdot3\cdot10=124\).

Рассмотрим \(7\) возможных запрещённых соседств. Если выбраны \(k\) соседств, они образуют \(c\) блоков подряд идущих рёбер в цепочке. Такие \(k\) рёбер можно выбрать \(C(k-1,c-1)C(8-k,c)\) способами. Каждый блок можно ориентировать \(2\) способами, значит ориентаций \(2^c\), а после склейки остаётся \(8-k\) объектов, которые можно переставить \((8-k)!\) способами. По включению-исключению получаем сумму \(40320-70560+51840-20400+4608-612+48-2=5242\).

Ответ \(5!=120\).

Если считать все \(4\) буквы различными, будет \(4!=24\). Каждое слово посчитано \(2!\cdot2!=4\) раза. Ответ \(24/4=6\).

Первого можно выбрать \(7\) способами, второго \(6\), третьего \(5\). Всего \(7\cdot6\cdot5=210\).

Фиксируем одного человека, чтобы убрать повороты. Остальных \(4\) рассаживаем \(4!=24\) способами.

Блок и ещё \(4\) человека — всего \(5\) объектов, их можно расставить \(5!\) способами. Внутри блока \(2\) порядка. Ответ \(2\cdot5!=240\).

Всего \(6!=720\). Рядом они стоят \(2\cdot5!=240\) способами. Значит ответ \(720-240=480\).

Всего \(6\) букв. Делим \(6!\) на \(3!\) для букв \(A\) и на \(2!\) для букв \(N\). Получаем \(6!/(3!\cdot2!)=60\).

Всего \(7!=5040\). Если двое рядом, склеиваем их: \(6!\cdot2=1440\). Ответ \(5040-1440=3600\).

Три предметных блока можно переставить \(3!\) способами. Внутри блоков: \(3!\), \(2!\), \(2!\). Всего \(3!\cdot3!\cdot2!\cdot2!=144\).

Пара образует блок. Итого \(5\) объектов на круге, их можно расположить \((5-1)!=24\) способами. Внутри блока \(2\) порядка. Ответ \(48\).

Всего \(24\). С одной указанной неподвижной точкой: \(3!\), таких точек \(4\). С двумя: \(2!\), таких пар \(6\). С тремя: \(1!\), таких наборов \(4\). С четырьмя: \(1\). Ответ \(24-4\cdot6+6\cdot2-4\cdot1+1=9\).

Всего \(5!=120\) перестановок. По симметрии ровно половина имеет \(1\) раньше \(2\). Ответ \(60\).

Мальчиков можно расставить \(5!\) способами. Вокруг них \(6\) промежутков: до первого, между соседними и после последнего. Выбираем \(4\) промежутка для девочек и расставляем девочек \(4!\) способами. Ответ \(5!\cdot15\cdot4!=43200\).

Всего \(6!/(2!2!2!)=90\). Если \(AA\) рядом, считаем блок \(AA\), \(B,B,C,C\): \(5!/(2!2!)=30\), таких букв \(3\). Если две пары рядом, например \(AA\) и \(BB\), получаем \(4!/2!=12\), таких выборов \(3\). Если все три пары рядом, \(3!=6\). Ответ \(90-3\cdot30+3\cdot12-6=30\).

Если последняя \(0\), первая цифра выбирается \(6\) способами, затем \(5\) и \(4\): \(120\). Если последняя \(5\), первая цифра не \(0\) и не \(5\): \(5\) способов, затем \(5\) и \(4\): \(100\). Всего \(220\).

Всего \((8-1)!=5040\). Если двое рядом, склеиваем их в блок: остаётся \(7\) объектов на круге, \((7-1)!=720\), внутри блока \(2\) порядка. Плохих \(1440\). Ответ \(5040-1440=3600\).

Всего \(8!\) расстановок. Относительные порядки книг \(A,B,C\) равновозможны, их \(3!=6\). Подходит один порядок, значит ответ \(8!/6=6720\).

Чётные числа \(2,4,6\) можно расставить по местам \(2,4,6\) в \(3!\) способах. Нечётные числа \(1,3,5,7\) занимают остальные места в \(4!\) способах. Ответ \(3!\cdot4!=144\).

Всего пар позиций для двух \(A\): \(10\). Соседних пар \(4\), значит несоседних \(6\). Остальные \(3\) позиции можно заполнить буквами \(B,C,D\) независимо: \(3^3=27\). Ответ \(6\cdot27=162\).

Зафиксируем Антона. Для Бориса есть \(2\) места на расстоянии два шага по кругу от Антона. Оставшихся \(3\) человек рассаживаем \(3!\) способами. Ответ \(2\cdot3!=12\).

Всего \(5!=120\). С хотя бы одной указанной неподвижной точкой считаем по включению-исключению: \(120-5\cdot4!+10\cdot3!-10\cdot2!+5\cdot1!-1=120-120+60-20+5-1=44\).

Мальчиков можно посадить по кругу \((6-1)!=120\) способами. Между ними образуется \(6\) промежутков, в которые нужно рассадить \(6\) девочек: \(6!\) способов. Ответ \(120\cdot720=86400\).

Числа \(4,5,6,7,8\) можно расставить \(5!\) способами. Они создают \(6\) промежутков, включая края. Нужно выбрать \(3\) промежутка для чисел \(1,2,3\) и расположить эти числа \(3!\) способами. Ответ \(5!\cdot20\cdot6=14400\).

Всего перестановок \(10!/(2!^5)=113400\). Если выбрать \(k\) букв, пары которых склеены, получаем \(C(5,k)(10-k)!/(2!^{5-k})\) расположений. По включению-исключению: \(113400-113400+50400-12600+1800-120=39480\).

Упорядоченно можно выбрать \(5\cdot4=20\) способами, но каждая пара посчитана дважды. Ответ \(10\).

Всего \(2^4=16\) подмножеств. Пустое одно, значит непустых \(15\).

Получаем \(\binom{7}{3}=7\cdot6\cdot5/3!=35\).

Каждому выбору \(3\) элементов соответствует выбор \(7\) элементов, которые не вошли. Это взаимно однозначное соответствие, значит числа равны.

Нужно выбрать \(2\) позиции из \(6\). Ответ \(\binom{6}{2}=15\).

Девочек выбираем \(\binom{5}{2}=10\) способами, мальчика \(4\) способами. Всего \(40\).

Получаем \(\binom{5}{2}\binom{4}{2}+\binom{5}{3}\binom{4}{1}+\binom{5}{4}=10\cdot6+10\cdot4+5=105\).

Любые две вершины задают отрезок: \(\binom{12}{2}=66\). Из них \(12\) сторон. Значит диагоналей \(66-12=54\).

Всего \(\binom{10}{4}=210\). Без отличников выбираем \(4\) из оставшихся \(7\): \(\binom{7}{4}=35\). Ответ \(175\).

Пусть \(a_1

Строка состоит из \(8\) единиц и \(2\) перегородок, всего \(10\) символов. Выбираем позиции перегородок: \(\binom{10}{2}=45\).

Пусть \(x'=x-1\), \(y'=y-1\), \(z'=z-1\). Тогда \(x'+y'+z'=7\), где переменные неотрицательны. Ответ \(\binom{9}{2}=36\).

Считаем \(k\)-элементные подмножества \(n\)-элементного множества. Специальный элемент либо не выбран: \(\binom{n-1}{k}\), либо выбран: \(\binom{n-1}{k-1}\). Сумма этих двух непересекающихся случаев даёт все подмножества.

Команда из \(3\) человек может содержать \(3,2,1,0\) мальчиков. Эти случаи не пересекаются. В каждом случае выбираем нужное число мальчиков и девочек, получая указанную сумму.

Для выбранных \(a_1<\cdots

Всего \(\binom{20}{4}=4845\). Чисел, не кратных \(5\), \(16\), значит подмножеств без кратных \(5\): \(\binom{16}{4}=1820\). Ответ \(4845-1820=3025\).

Считаем случаи: \(3\) мальчика и \(2\) девочки: \(\binom{6}{3}\binom{5}{2}=200\); \(4\) мальчика и \(1\) девочка: \(\binom{6}{4}\binom{5}{1}=75\); \(5\) мальчиков: \(\binom{6}{5}=6\). Итого \(281\).

Нужно выбрать \(3\) вершины из \(9\). Ответ \(\binom{9}{3}=84\).

Пусть \(x'=x-2\), \(y'=y-3\). Тогда \(x'+y'+z=7\), все переменные неотрицательны. Число решений равно \(\binom{9}{2}=36\).

Случаи: \(3\) красных и \(2\) синих: \(\binom{10}{3}\binom{8}{2}=3360\); \(4\) красных и \(1\) синий: \(\binom{10}{4}\binom{8}{1}=1680\); \(5\) красных: \(\binom{10}{5}=252\). Итого \(5292\).

Рассмотрим все \((r+1)\)-элементные подмножества множества \(\{1,\ldots,n+1\}\). Их \(C(n+1,r+1)\). Если наибольший элемент равен \(t+1\), где \(r\le t\le n\), то остальные \(r\) элементов выбираются из первых \(t\) элементов: \(C(t,r)\) способов. Суммируя по \(t\), получаем левую часть.

После выбора \(1\) нужно выбрать ещё \(4\) числа из \(\{3,\ldots,15\}\) без соседства. Это отрезок длины \(13\). Число способов выбрать \(4\) несоседних элементов из \(13\) равно \(\binom{13-4+1}{4}=\binom{10}{4}=210\).

Возможны только \(2\) мальчика и \(4\) девочки, \(3\) и \(3\), \(4\) и \(2\). Получаем \(\binom{8}{2}\binom{7}{4}+\binom{8}{3}\binom{7}{3}+\binom{8}{4}\binom{7}{2}=28\cdot35+56\cdot35+70\cdot21=4410\).

Достаточно разбить все подмножества на \(6\) цепочек, потому что тогда \(7\) выбранных подмножеств по принципу Дирихле попадут в одну цепочку дважды. Например, можно взять цепочки: \(\varnothing\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\subset\{1,2,3,4\}\); \(\{2\}\subset\{2,3\}\subset\{2,3,4\}\); \(\{3\}\subset\{1,3\}\subset\{1,3,4\}\); \(\{4\}\subset\{1,4\}\subset\{1,2,4\}\); одиночные цепочки \(\{2,4\}\) и \(\{3,4\}\). В одной цепочке любые два множества сравнимы по включению.

Каждое рукопожатие соответствует паре людей. Пар \(10\cdot9/2=45\).

Всего \(20\cdot2=40\) пар.

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

Каждое из \(12\) слов даёт \(5\) позиций. Всего \(12\cdot5=60\) пар.

Нужно выбрать \(2\) вершины из \(6\): \(6\cdot5/2=15\).

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

Среднее число учеников в кружке равно \(60/8=7.5\). Если бы во всех кружках было не более \(7\), всего было бы не более \(56\), противоречие. Значит в некотором кружке хотя бы \(8\).

Каждый из \(5\) элементов входит ровно в половину всех подмножеств, то есть в \(2^4=16\) подмножеств. Сумма размеров равна числу пар \((S,x)\), значит \(5\cdot16=80\).

Элемент \(x\) выбирается \(6\) способами. Для каждого \(x\) остальные \(5\) элементов либо входят в \(S\), либо нет: \(2^5\) способов. Всего \(6\cdot2^5=192\).

Среднюю вершину \(B\) выбираем \(6\) способами. Конец \(A\) — \(5\) способами, конец \(C\) — \(4\) способами. Всего \(6\cdot5\cdot4=120\).

Из каждой из \(n\) вершин выходит \(n-3\) диагоналей, значит концов диагоналей \(n(n-3)\). Каждая диагональ имеет два конца, поэтому диагоналей \(n(n-3)/2\).

Если бы каждый решил не более \(3\) задач, всего было бы не более \(25\cdot3=75\), что меньше \(100\). Значит кто-то решил не менее \(4\) задач.

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

Выберем \(3\)-элементное подмножество из \(\{1,\ldots,n+1\}\). Если наибольший элемент равен \(t+1\), то остальные два выбираются из \(1,\ldots,t\), то есть \(C(t,2)\) способами. Сумма по \(t=2,\ldots,n\) даёт левую часть, а всего таких подмножеств \(C(n+1,3)\).

Всего членств \(40\cdot2=80\). Если бы в каждом кружке было не более \(15\) учеников, всего было бы не более \(5\cdot15=75\), противоречие. Значит некоторый кружок имеет не менее \(16\) учеников.

Каждый элемент либо не входит в \(B\), либо входит в \(B\), но не входит в \(A\), либо входит в оба множества. Три независимых состояния для каждого из \(n\) элементов дают \(3^n\) пар.

Нужно выбрать \(2\) точки из \(12\). Получаем \(12\cdot11/2=66\) отрезков.

Всего партий \(n(n-1)/2\), и каждая даёт ровно одну победу. Среднее число побед на игрока равно \((n(n-1)/2)/n=(n-1)/2\). Значит некоторый игрок имеет не меньше среднего.

В сетке \(5\) на \(6\) клеток есть \(6\) горизонтальных и \(7\) вертикальных линий. Прямоугольник задаётся выбором двух вертикальных и двух горизонтальных линий. Ответ \(C(7,2)C(6,2)=21\cdot15=315\).

Всего членств \(12\cdot5=60\). Среднее число комитетов на человека равно \(60/20=3\). Значит некоторый человек входит не менее чем в \(3\) комитета.

Построим граф знакомств. Сумма степеней не меньше \(15\cdot7=105\). Каждая пара знакомых даёт два вклада в сумму степеней, значит число рёбер не меньше \(105/2=52.5\). Так как оно целое, оно не меньше \(53\).

По размеру \(S=k\) получаем \(k^2\) способов выбрать упорядоченную пару \((x,y)\), значит левая часть. Теперь считаем по \((x,y)\). Если \(x=y\), выбираем этот элемент \(n\) способами, остальные элементы \(S\) произвольны: \(2^{n-1}\). Если \(x e y\), выбираем упорядоченную пару \(n(n-1)\) способами, остальные \(n-2\) элементов произвольны: \(2^{n-2}\). Итого \(n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}\).

По прямым инцидентностей \(9\cdot5=45\). Если точек \(N\), то по точкам инцидентностей \(3N\). Значит \(3N=45\), откуда \(N=15\).

Предположим, что любые две выбранные тройки имеют не более одного общего элемента. Тогда никакая пара элементов не может входить в две разные тройки, иначе эти две тройки имели бы общую пару, то есть два общих элемента. Каждая тройка содержит \(3\) пары, поэтому \(17\) троек содержали бы \(51\) различную пару элементов. Но всего пар в \(10\)-элементном множестве \(10\cdot9/2=45\). Противоречие. Значит две тройки имеют не менее двух общих элементов.

Есть \(12\) месяцев и \(13\) человек. По принципу Дирихле в каком-то месяце родились хотя бы двое.

Ящики — последние цифры \(0,1,\ldots,9\). Чисел \(11\), значит два попали в один ящик.

Предположим, что нет трёх одного цвета. Тогда каждого цвета не более \(2\), всего не более \(4\), но носков \(5\). Противоречие.

Остатков по модулю \(n\) всего \(n\). Среди \(n+1\) чисел два имеют одинаковый остаток. Их разность делится на \(n\).

Пары: \((1,10),(2,9),(3,8),(4,7),(5,6)\). Выбрано \(6\) чисел, пар \(5\), значит из одной пары выбраны оба числа. Их сумма \(11\).

Есть \(8\) классов остатков. Если в каждом не более \(2\) чисел, всего не более \(16\), но чисел \(17\). Значит в каком-то классе не менее \(3\).

У каждого человека число знакомых от \(0\) до \(5\). Если есть человек с \(0\) знакомых, то нет человека с \(5\) знакомых; если есть с \(5\), то нет с \(0\). Значит реально возможны не более \(5\) значений для \(6\) человек. По принципу Дирихле два значения совпадают.

Каждое число имеет вид \(2^k m\), где \(m\) нечётно. Возможных нечётных частей в диапазоне \(1,\ldots,18\) всего \(9\). У \(10\) выбранных чисел две нечётные части совпадают. Тогда эти числа имеют вид \(2^a m\) и \(2^b m\), и меньшее делит большее.

Есть \(100\) остатков по модулю \(100\). Среди \(101\) чисел два имеют одинаковый остаток, значит их разность делится на \(100\).

Есть \(10\) пар, каждая имеет сумму \(21\). Выбрано \(11\) чисел, значит одна пара выбрана полностью.

После разбиения на \(4\) единичных квадрата \(5\) точек дают две точки в одном маленьком квадрате. Расстояние между любыми двумя точками единичного квадрата не больше его диагонали \(\sqrt{2}\).

Пусть \(s_i\) — сумма первых \(i\) чисел. Если какой-то \(s_i\) делится на \(10\), готово. Иначе \(10\) частичных сумм имеют только \(9\) ненулевых остатков, значит две имеют одинаковый остаток. Их разность — сумма подряд идущего блока, кратная \(10\).

Рассмотрим \(s_1,\ldots,s_n\). Если некоторый \(s_i\equiv0\pmod n\), то сумма первых \(i\) чисел подходит. Иначе все \(s_i\) имеют один из \(n-1\) ненулевых остатков. Две суммы имеют одинаковый остаток; их разность является суммой непустого подряд идущего блока и делится на \(n\).

Есть \(6\) ящиков остатков: \(0\), \(5\), пары противоположных остатков. Семь чисел дают два в одном ящике. Если остатки равны, разность делится на \(10\). Если они противоположны, сумма делится на \(10\).

Каждая точка имеет тип чётности \((x\bmod2,y\bmod2)\), всего \(4\) типа. Среди \(5\) точек две имеют одинаковый тип. Тогда суммы их \(x\)-координат и \(y\)-координат чётны, значит середина имеет целые координаты.

Выберем человека \(A\). Среди остальных \(5\) либо есть \(3\) знакомых с \(A\), либо \(3\) незнакомых с \(A\). В первом случае, если среди этих троих есть знакомая пара, вместе с \(A\) получаем троих попарно знакомых; если нет, эти трое попарно незнакомы. Второй случай аналогичен: если среди трёх незнакомых с \(A\) есть незнакомая пара, вместе с \(A\) получаем троих попарно незнакомых; иначе эти трое попарно знакомы.

Соединим середины сторон и получим \(4\) маленьких равносторонних треугольника со стороной \(1\). Пять точек дают две в одном маленьком треугольнике. Расстояние между любыми двумя точками такого треугольника не больше \(1\).

Есть \(50\) пар соседних чисел. Выбрано \(51\) число, значит в одной паре выбраны оба числа. Они последовательные.

Остатков по модулю \(5\) всего \(5\). Среди \(6\) чисел два имеют одинаковый остаток, поэтому их разность делится на \(5\).

Непустых подмножеств \(2^{10}-1=1023\). Сумма любого подмножества лежит от \(1\) до \(1000\), то есть возможных сумм не более \(1000\). По принципу Дирихле две разные непустые группы имеют одинаковую сумму.

Непустых подмножеств \(1023\). Их суммы лежат от \(1\) до \(990\), возможных сумм не более \(990\). Значит есть два разных непустых подмножества с равной суммой. Удалим из них общие элементы. Оставшиеся части имеют равные суммы; они не обе пусты, иначе исходные подмножества совпадали бы. Получили две непустые непересекающиеся группы с равной суммой.

Выберем произвольного человека \(A\). Среди остальных \(9\) каждый либо знаком с \(A\), либо не знаком. Два ящика: знакомые и незнакомые. По усиленному принципу Дирихле в одном из них не менее \(\lceil9/2 ceil=5\) человек. Значит у \(A\) есть \(5\) знакомых или \(5\) незнакомых.

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

Для каждого числа \(a_i\) запишем пару \((u_i,d_i)\), где \(u_i\) — максимальная длина возрастающей подпоследовательности, начинающейся с \(a_i\), а \(d_i\) — максимальная длина убывающей, начинающейся с \(a_i\). Если нет монотонной подпоследовательности длины \(4\), то \(u_i,d_i\in\{1,2,3\}\), всего \(9\) пар. Для \(10\) чисел две пары совпадают: пусть \(iu_j\), противоречие равенству пар. Если \(a_i>a_j\), аналогично \(d_i>d_j\). Противоречие.

Начальное число чётно, и прибавление \(2\) сохраняет чётность. Число \(99\) нечётно, значит получить его нельзя.

Число орлов меняется на \(-2\), \(0\) или \(2\), значит его чётность сохраняется. Было \(9\) орлов, должно стать \(0\). Нечётность не может стать чётностью.

В начале всего \(15\) камней, в требуемом состоянии \(20\). Так как перенос камня не меняет сумму, получить такое состояние нельзя.

Остаток по модулю \(3\) сохраняется. \(5\equiv2\pmod3\), а \(100\equiv1\pmod3\). Значит получить \(100\) нельзя.

При смене двух знаков число минусов меняется на \(-2\), \(0\) или \(2\). Чётность числа минусов сохраняется. В начале \(0\), в конце должно быть \(3\), невозможно.

Смена двух знаков умножает произведение на \((-1)^2=1\). В начале произведение \(+1\). При \(7\) минусах произведение \(-1\). Значит нельзя.

В начале всего \(14\) фишек, в конце \(15\). Перекладывание фишки сохраняет общее число, поэтому состояние невозможно.

Если среди перевёрнутых \(h\) орлов, число орлов меняется на \(4-2h\), то есть на чётное число. Чётность сохраняется. Было \(15\) орлов, нечётно; \(2\) орла — чётно. Нельзя.

В начале сумма \(11\), в конце сумма \(15\). Операция сохраняет сумму, значит получить нельзя.

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

Смена \(4\) знаков умножает произведение на \((-1)^4=1\). В начале произведение \(+1\), а при одном минусе \(-1\). Нельзя.

За ход сумма меняется на \(1+1-2=0\). Значит сумма вообще сохраняется, а тем более сохраняется её остаток по модулю \(3\).

Если среди выбранных \(h\) включённых ламп, то число включённых меняется на \(100-2h\), чётное число. В начале включённых \(0\), чётно; в конце должно быть \(2025\), нечётно. Нельзя.

За ход общее число фишек меняется на \(4-1=3\), значит остаток суммы по модулю \(3\) не меняется.

В исходной доске \(32\) чёрных и \(32\) белых клетки. Противоположные углы одного цвета, значит после удаления остаётся \(30\) клеток одного цвета и \(32\) другого. Домино всегда покрывает одну чёрную и одну белую клетку, поэтому покрытие невозможно.

Каждый ход меняет \(4\) знака, значит произведение всех \(16\) знаков умножается на \((-1)^4=1\). В начале произведение \(+1\). При ровно одном минусе произведение \(-1\). Нельзя.

Сумма \(1+2+\cdots+10=55\) нечётна. Замена знака у числа \(a\) меняет сумму на \(-2a\), то есть на чётное число. Поэтому чётность суммы сохраняется и остаётся нечётной. Ноль чётен, значит невозможно.

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

Чётность числа сохраняется, потому что прибавляются чётные числа. Начальное число \(1\) нечётно, а \(100\) чётно. Получить нельзя.

Каждый ход увеличивает \(x+y\) на \(3\). Значит остаток \(x+y\) по модулю \(3\) сохраняется и равен \(0\). В точке \((10,10)\) сумма координат \(20\equiv2\pmod3\). Попасть нельзя.

Произведение всех \(36\) чисел сохраняется: за ход оно умножается на \((-1)^6=1\). В начале произведение \(1\). В таблице с одной \(-1\) произведение \(-1\). Значит такая таблица недостижима.

Каждый ход коня меняет цвет клетки. После \(15\) ходов, поскольку \(15\) нечётно, конь окажется на клетке противоположного цвета. Исходная клетка чёрная, значит вернуться на неё нельзя.

За ход сумма меняется на \(2+2-1=3\), значит её остаток по модулю \(3\) сохраняется. В начале сумма \(3\equiv0\pmod3\). В конце сумма \(30\equiv0\pmod3\), этот инвариант не запрещает. Попробуем сумму квадратов по модулю \(3\): числа \(1\) и \(10\) сравнимы по модулю \(3\), а операция меняет остатки двух чисел на \(-1\) и одного на \(-1\), то есть все три остатка уменьшаются на \(1\). После каждого хода все три числа остаются равными по модулю \(3\). В начале они все \(1\), в конце \(10\equiv1\), инвариант тоже не запрещает. Значит по этим инвариантам запрета нет; действительно, состояние достижимо: применим ход три раза, каждый раз вычитая из разной координаты, все координаты увеличатся на \(3\). Повторив три таких цикла, получим \((10,10,10)\).

Число инверсий в начале равно \(0\). Каждый соседний обмен меняет чётность числа инверсий. После \(27\) ходов чётность инверсий должна быть нечётной. Но в строке \(87654321\) число инверсий равно \(C(8,2)=28\), оно чётно. Противоречие, значит ровно за \(27\) ходов получить нельзя.

Площадь доски равна \(25\), а площадь каждого домино равна \(2\). Суммарная площадь домино всегда четна, поэтому покрыть область площади \(25\) невозможно.

В полной доске \(6\times6\) черных и белых клеток поровну. После удаления двух клеток одного цвета равенство нарушается. Но каждое домино покрывает одну черную и одну белую клетку, значит, любое домино-покрытие закрывает одинаковое число клеток двух цветов. Противоречие.

На доске \(7\times7\) угловой цвет встречается \(25\) раз, другой цвет - \(24\) раза. Домино закрывают равные количества клеток двух цветов. Значит, после покрытия домино должна остаться клетка того цвета, которого было на одну больше, то есть углового цвета.

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

В раскраске по остатку \(i+j\pmod3\) каждое прямое тримино покрывает по одной клетке каждого цвета. На доске \(5\times5\) цветов \(0,1,2\) соответственно \(9,8,8\). Клетка \((1,1)\) имеет цвет \(2\), значит после удаления получаются числа \(9,8,7\). Они не равны, поэтому покрытия нет.

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

В шахматной раскраске клетка \((i,i)\) всегда имеет один и тот же цвет, потому что \(i+i\) четно. Значит, удалены \(8\) клеток одного цвета. В полной доске цветов было поровну, а после удаления равенство нарушилось. Домино покрывают цвета поровну, поэтому замощение невозможно.

Покрасим столбцы попеременно в два цвета. Горизонтальное домино покрывает одну клетку каждого столбцового цвета, а вертикальное домино покрывает две клетки одного столбцового цвета. На всей доске обоих цветов по \(18\) клеток. Горизонтальные домино не меняют баланс, поэтому вертикальные домино должны дать одинаковое число клеток двух цветов. Это означает, что вертикальных домино в столбцах первого и второго цвета должно быть поровну. Но всего их \(5\), что невозможно.

В раскраске \((i,j)\mapsto i+j\pmod3\) каждое прямое тримино покрывает по одной клетке каждого цвета. На доске \(7\times7\) цветов \(0,1,2\) соответственно \(16,16,17\). Клетка \((1,2)\) имеет цвет \(0\), поэтому после удаления остаются количества \(15,16,17\). Они не равны, следовательно, покрыть оставшуюся часть прямыми тримино невозможно.

В раскраске по \(i+j\pmod4\) каждое прямое тетрамино покрывает по одной клетке каждого из четырех цветов. На доске \(5\times5\) количества цветов \(0,1,2,3\) равны \(6,6,7,6\). Клетка \((1,2)\) имеет цвет \(3\), поэтому после удаления остаются количества \(6,6,7,5\). Они не равны, значит покрытия быть не может.

Противоположные углы доски \(4\times4\) имеют один цвет. Но ход коня меняет цвет, поэтому после \(15\) ходов, то есть после нечетного числа ходов, конь должен оказаться на клетке противоположного цвета. Следовательно, закончить в противоположном углу он не может.

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

В шахматной раскраске все клетки главной диагонали имеют один цвет. В полной доске \(10\times10\) цветов поровну, а после удаления \(10\) клеток одного цвета равенство нарушается. Домино всегда покрывает одну клетку каждого цвета, поэтому покрытие невозможно.

При раскраске \((i,j)\mapsto i+j\pmod3\) каждое тримино покрывает по одной клетке каждого цвета. Значит, \(21\) тримино покрывают по \(21\) клетке каждого цвета. На доске \(8\times8\) цветов \(0,1,2\) соответственно \(22,21,21\). Поэтому отдельная клетка обязана иметь цвет \(0\). Но \((1,1)\) имеет цвет \(2\), а \((8,8)\) имеет цвет \(16\equiv1\pmod3\). Значит, ни одна из этих клеток не подходит.

Покрасим столбцы попеременно. Горизонтальное домино всегда покрывает одну клетку каждого столбцового цвета. Вертикальное домино покрывает две клетки одного цвета. Так как на доске цветов поровну, вертикальные домино должны распределиться поровну между столбцами двух цветов. Их число должно быть четным. Число \(17\) нечетно, значит такое покрытие невозможно.

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

На доске \(9\times9\) угловой цвет встречается \(41\) раз, другой цвет - \(40\) раз. Все домино вместе закрывают одинаковое число клеток двух цветов. Оставшаяся одна клетка, покрытая мономино, должна быть клеткой цвета, которого было больше, то есть углового цвета.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Прямое тетрамино покрывает по одной клетке каждого цвета. На полной доске \(8\times8\) каждого цвета \(16\) клеток. На главной диагонали цвета чередуются только между \(0\) и \(2\): удаляются по \(4\) клетки цветов \(0\) и \(2\), а цвета \(1\) и \(3\) не удаляются. Остаются количества \(12,16,12,16\), не все равны. Поэтому покрытия нет.

При раскраске по \(i+j\pmod3\) каждое прямое тримино покрывает по одной клетке каждого цвета. Значит, \(16\) тримино покрывают по \(16\) клеток каждого цвета. На доске \(7\times7\) количества цветов равны \(16,16,17\), причем лишний цвет - это \(2\). Поэтому мономино обязано стоять на клетке цвета \(2\), то есть на клетке с \(i+j\equiv2\pmod3\).

В полной доске \(8\times8\) по \(32\) клетки каждого цвета. Домино покрывают равные количества черных и белых клеток. Значит, после удаления всех покрытых домино клеток остаток тоже должен иметь равные изменения относительно двух цветов: если одна непокрытая клетка черная и одна белая, покрытые клетки были бы \(31\) черная и \(31\) белая, что возможно. Значит утверждение в такой формулировке неверно: две непокрытые клетки могут быть разных цветов. Например, можно оставить две соседние клетки и покрыть остальное. Следовательно, правильный вывод: по раскраске нельзя доказать одинаковый цвет; условие недостаточно.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Каждое прямое тетрамино закрывает по одной клетке каждого цвета. На полной доске \(8\times8\) каждого цвета по \(16\). Углы имеют цвета \(2,1,1,0\), поэтому после удаления остаются числа \(15,14,15,16\). Они не равны, а значит область не может быть разбита на фигуры, каждая из которых берет один цвет каждого вида.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Каждое прямое тетрамино покрывает по одной клетке каждого цвета, поэтому \(20\) тетрамино покрывают по \(20\) клеток каждого цвета. На доске \(9\times9\) количества цветов \(0,1,2,3\) равны \(20,20,21,20\). Следовательно, единственная клетка, покрытая мономино, должна быть лишней клеткой цвета \(2\).

Покрасим столбцы попеременно. Как и раньше, горизонтальные домино покрывают по одной клетке двух цветов, а вертикальные - две клетки одного цвета. Так как на всей доске цветов поровну, вертикальные домино должны распределиться поровну между двумя типами столбцов. Значит, их общее число четно. Поэтому нечетное число вертикальных домино невозможно. Пример с \(16\): в первых четырех столбцах положим все домино вертикально, получим \(16\) вертикальных домино; оставшиеся четыре столбца можно покрыть горизонтальными домино по строкам.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Любое прямое тетрамино покрывает по одной клетке каждого из четырех цветов. На полной доске \(10\times10\) количества цветов \(0,1,2,3\) равны \(25,24,25,26\). На главной диагонали \((i,i)\) цвета чередуются между \(2\) и \(0\), поэтому удаляются \(5\) клеток цвета \(0\) и \(5\) клеток цвета \(2\). На побочной диагонали \((i,11-i)\) сумма индексов равна \(11\), значит все эти \(10\) клеток имеют цвет \(3\). После удаления остаются количества \(20,24,20,16\). Они не равны. Но замощение прямыми тетрамино требовало бы равного числа клеток каждого цвета. Противоречие.

При ходах \(1\) или \(2\) проигрышны позиции \(0,3,6,9,12,\ldots\). Из кратного \(3\) любой ход оставляет не кратное \(3\), а из любого другого остатка можно оставить кратное \(3\). Так как \(14\equiv2\pmod3\), первый берет \(2\) камня и оставляет \(12\). Затем он дополняет ход соперника до \(3\) камней.

Проигрышны кратные \(4\). Число \(20\) кратно \(4\), значит первый игрок в проигрышной позиции. Что бы он ни взял, второй берет столько, чтобы за два хода было взято \(4\) камня. Поэтому второй сделает последний ход.

Первый игрок сначала прибавляет \(1\). После хода соперника на \(a\), где \(1\le a\le4\), первый прибавляет \(5-a\). Тогда после ходов первого суммы будут \(1,6,11,16,21\). Поэтому первый выигрывает.

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

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

Так как можно взять от \(1\) до \(4\), проигрышны кратные \(5\). Число \(37\) дает остаток \(2\) по модулю \(5\). Первый берет \(2\) камня и оставляет \(35\). После этого на ход соперника \(a\) первый отвечает \(5-a\), снова оставляя кратное \(5\).

Если остался \(1\) камень, игрок на ходе проигрывает. Далее проигрышные позиции повторяются через \(4\): \(1,5,9,\ldots\). Число \(28\equiv0\pmod4\), поэтому первый берет \(3\) камня и оставляет \(25\equiv1\pmod4\). Затем он дополняет ход соперника до \(4\), пока сопернику не останется один камень.

Так как \(50\equiv1\pmod7\), первый начинает с \(1\). Если второй прибавил \(a\), первый прибавляет \(7-a\). Тогда после ходов первого сумма каждый раз увеличивается на \(7\): \(1,8,15,22,29,36,43,50\). Первый выигрывает.

Второй разбивает числа на пары \((1,20),(2,19),\ldots,(10,11)\). Каждый раз, когда первый берет число из пары, второй берет второе число этой пары. В каждой паре сумма равна \(21\), и каждому игроку достается ровно одно число из каждой пары. Поэтому итоговые суммы равны.

После хода первого второй кладет домино в клетки, центрально-симметричные занятым. На доске \(6\times6\) ни одно домино не совпадает со своим центральным отражением, а отражение соседних клеток снова соседние клетки. Если отраженные клетки были бы заняты раньше, то по симметрии были бы заняты и клетки хода первого, что невозможно. Значит ответ всегда легален, и второй делает последний ход.

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

В начале есть \(1\) кусок, а в конце должно быть \(24\) единичных квадратика. Каждый ход увеличивает число кусков ровно на \(1\). Поэтому всего будет \(24-1=23\) хода. Нечетный ход делает первый игрок, значит он выигрывает.

Позиции с равными кучами проигрышны: соперник может копировать ход в другой куче. Поэтому первый должен уменьшить кучу \(17\) до \(12\), взяв \(5\) камней. После этого на любой ход второго первый отвечает таким же ходом в другой куче и выигрывает.

Кратные \(3\) проигрышны: из них ходы \(1,2,4\) ведут к остаткам \(2,1,2\) по модулю \(3\), а из любого не кратного \(3\) можно взять \(1\) или \(2\), чтобы оставить кратное \(3\). Так как \(30\) кратно \(3\), первый игрок проигрывает при правильной игре.

Проверим позиции с остатками \(0\) и \(2\) по модулю \(7\). Из них ходы \(1,3,4\) не ведут снова к остаткам \(0\) или \(2\). Из любого другого остатка можно попасть в \(0\) или \(2\): из \(1\) взять \(1\), из \(3\) взять \(1\), из \(4\) взять \(4\), из \(5\) взять \(3\), из \(6\) взять \(4\). Значит проигрышны позиции \(0\) и \(2\) по модулю \(7\). Так как \(31\equiv3\pmod7\), первый берет \(1\) камень и оставляет \(30\equiv2\pmod7\).

Второй игрок после каждого хода первого на \(a\) прибавляет \(10-a\). Тогда после ходов второго суммы будут \(10,20,30,\ldots,100\). Поэтому второй игрок достигнет \(100\) и выиграет.