#11 Смешанные задачи I

Последняя цифра должна быть \(2\) или \(4\): \(2\) выбора. После этого сотни можно выбрать \(4\) способами, десятки \(3\) способами. Итого \(2\cdot4\cdot3=24\).

Можно взять \(4\) носка всех разных цветов. Следующий, пятый, обязательно совпадет по цвету с одним из них. Ответ: \(5\).

В начале минусов \(0\). При смене двух знаков число минусов меняется на \(-2\), \(0\) или \(2\), значит его четность сохраняется. Число \(3\) нечетно, поэтому получить ровно \(3\) минуса нельзя.

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

Сумма степеней равна \(12\), четность не запрещает. Построим явно. Назовем вершины \(A,B,C,D,E\). Соединим \(A\) со всеми остальными: у \(A\) степень \(4\), а у остальных пока степень \(1\). Теперь добавим ребра \(BC\) и \(BD\). Тогда степени равны: \(\deg A=4\), \(\deg B=3\), \(\deg C=2\), \(\deg D=2\), \(\deg E=1\). Значит такой граф существует.

Пусть \(a_n\) - число таких подмножеств для \(\{1,\ldots,n\}\). Тогда \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Получаем \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\).

Разобьем числа по остаткам при делении на \(10\). Остатков \(10\), чисел \(11\), значит два числа имеют одинаковый остаток. Их разность делится на \(10\).

Проигрышны кратные \(5\). Так как \(34\equiv4\pmod5\), первый берет \(4\) камня и оставляет \(30\). Затем он дополняет ход соперника до \(5\).

Нужно сделать \(3\) шага вправо и \(5\) вверх. Выбираем места для \(3\) шагов вправо: \(\binom{8}{3}=56\).

Нужно выбрать пару игроков из \(9\). Число партий равно \(\binom{9}{2}=36\).

Пусть \(a_n\) - число таких строк. Тогда \(a_0=1\), \(a_1=2\), \(a_n=a_{n-1}+a_{n-2}\). Получаем \(a_7=34\).

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

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

Пар \((ученик, кружок)\) по ученикам \(12\cdot3=36\). Если кружков \(k\), то по кружкам пар \(4k\). Значит \(4k=36\), откуда \(k=9\).

Второй после хода первого на \(a\) прибавляет \(8-a\). Тогда после ходов второго суммы будут \(8,16,24,\ldots,64\). Поэтому второй выигрывает.

Возможные числа знакомых: от \(0\) до \(9\). Но \(0\) и \(9\) не могут быть одновременно: если кто-то знаком со всеми, то никто не имеет \(0\) знакомых. Значит возможных разных значений не больше \(9\), а людей \(10\). По принципу Дирихле две степени совпадают.

Пусть \(a_n\) - число замощений. Тогда \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=1\). Получаем \(a_7=21\).

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

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

Всего путей \(\binom{8}{4}=70\). Через \((2,2)\): \(\binom{4}{2}\cdot\binom{4}{2}=36\). Значит ответ \(70-36=34\).

Пусть \(A\) - любой человек. У него есть как минимум \(6\) знакомых. Если среди этих знакомых есть знакомая пара, то вместе с \(A\) получаем тройку. Если знакомых пар среди них нет, то каждый из этих \(6\) людей знаком с \(A\) и может быть знаком только с тремя людьми вне этой шестерки и вне \(A\), значит его степень не больше \(4\). Это противоречит условию степени не меньше \(6\).

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

Пусть \(a_n\) - число строк. Тогда \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\), \(a_0=1\), \(a_1=2\), \(a_2=4\). Получаем \(a_3=7\), \(a_4=13\), \(a_5=24\), \(a_6=44\), \(a_7=81\), \(a_8=149\), \(a_9=274\).

Пусть числа равны \(a_1,\ldots,a_{20}\). Рассмотрим частичные суммы \(S_k=a_1+\cdots+a_k\) для \(k=1,\ldots,20\). Если какая-то \(S_k\) делится на \(20\), то подходит отрезок \(a_1,\ldots,a_k\). Если ни одна не делится на \(20\), то \(20\) частичных сумм имеют только \(19\) ненулевых остатков по модулю \(20\). Значит две из них, \(S_i\) и \(S_j\) при \(i