#12 Пробные олимпиады I

Для сотен \(5\) выборов, для десятков \(4\), для единиц \(3\). Итого \(5\cdot4\cdot3=60\).

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

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

Сумма степеней \(10\), значит ребер \(10/2=5\).

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

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

\(22\equiv2\pmod4\). Первый берет \(2\) камня и оставляет \(20\). Затем он дополняет ход соперника до \(4\).

Число партий равно числу пар игроков: \(\binom{7}{2}=21\).

По ученикам пар \(15\cdot2=30\). Если кружков \(k\), по кружкам пар \(5k\). Значит \(5k=30\), откуда \(k=6\).

При \(a_0=1\), \(a_1=2\) получаем \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\).

Есть \(8\) остатков по модулю \(8\), а чисел \(9\). По принципу Дирихле два числа имеют одинаковый остаток.

Минимум равен \(12-1=11\). Достигается на пути из \(12\) вершин.

Пусть \(S_k=a_1+\cdots+a_k\). Если какой-то \(S_k\) делится на \(8\), готово. Иначе \(8\) частичных сумм имеют только \(7\) ненулевых остатков, значит две имеют одинаковый остаток. Их разность - сумма подряд идущего блока - делится на \(8\).

Для \(a_n\) имеем \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=1\). Значения дают \(a_7=21\).

Первый прибавляет \(1\). Затем на ход соперника \(a\) отвечает \(7-a\). После ходов первого суммы \(1,8,15,\ldots,50\), значит первый выигрывает.

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

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

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

Первый берет \(6\) камней из кучи \(21\), оставляя две кучи по \(15\). Далее он повторяет ход соперника в другой куче. Такая стратегия приводит к последнему ходу первого.

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

Возьмем вершину \(v\) и \(5\) ее соседей. Если среди соседей есть ребро, получаем треугольник с \(v\). Если ребер между ними нет, то каждый из этих соседей соединен с \(v\) и максимум с тремя оставшимися вершинами, то есть имеет степень не больше \(4\), противоречие.

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

Всего путей \(\binom{8}{4}=70\). Плохие пути, впервые поднявшиеся выше диагонали, отражаются в пути из \((-1,1)\) в \((4,4)\), их \(\binom{8}{3}=56\). Поэтому хороших путей \(70-56=14\).

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