\olymp{СЕНЬОРОВ}{ЛИЧНАЯ}{

\centerline{\it Довывод}

\q1. Кубический дом $1000\times 1000\times 1000$ разбит на комнаты $1\times 1\times 1$; в некоторых комнатах живёт по одному человеку, а остальные пусты. Назовём \emph{общительностью} человека количество занятых комнат, имеющих с его комнатой общую грань. Оказалось, что у чётного числа жителей общительность равна 4, а у каждого из остальных она равна 2. Докажите, что общее количество жителей чётно.
%Куб $1000 \times 1000 \times 1000$ разбит на единичные кубики, некоторые из них отмечены. Назовём \emph{общительнрстью} отмеченного кубика количество отмеченных кубиков, имеющих с ним общую грань. Оказалось, что у чётного числа отмеченных кубиков общительность равна это количество равно 4, а у каждого из остальных оно равно 2. Докажите, что всего отмечено чётное число кубиков.
\source М. Югов, модификация

\q2. Пусть $ABC$~--- треугольник, в котором $\angle ACB = 90^\circ$ и $\angle A > \angle B$. Касательная в точке $C$ к описанной окружности треугольника $ABC$, пересекает прямую $AB$ в точке $D$. Точка $E$~--- середина отрезка $CD$, а точка $F$ лежит на прямой $EB$ так, что $AF \parallel CD$. Докажите, что прямые $AB$ и $CF$ перпендикулярны.
\source Австралия, 2020

\q3. Дано простое число $p>3$. Для каждого натурального $n<p$ обозначим через 
$x_n$ наименьшее натуральное число, для которого $nx_n$ даёт при делении на $p$ 
остаток 1. Какой остаток даёт при делении на $p$ число $$\sum\limits_{n=1}^{p-1} n\left[\frac{nx_n}{p}\right]?$$ 
\source Олимпиада Юго-Восточного Китая, 2021 



\q4. Анна и Боб играют в игру с колодой из $2025$ карт, пронумерованных числами $1,2,\dots,2025$. Изначально колода как-то перетасована, оба игрока знают порядок карт в ней. Анна и Боб ходят по очереди, начинает Анна. За ход игрок сначала смотрит на верхнюю карту. Если её номер $k$, он каким-то образом  перетасовывает верхние $k$ карт (показывая другому игроку, как именно он их перетасовал). Если после этого карта $k$ по-прежнему лежит наверху, игрок, сделавший ход, проиграл, иначе ход переходит к другому игроку. Назовём перетасованную колоду \emph{интересной}, если в игре, начинающейся с этой колоды, Боб может добиться того, чтобы Анна проиграла. Каких интересных колод больше --- тех, в которых вторая сверху карта имеет номер 28, или тех, в которых она имеет номер 29?
\source MEMO 2022, модифицировано
% 109

}

\olymp{СЕНЬОРОВ}{ЛИЧНАЯ}{

\centerline{\it Вывод}

\q5. \emph{Совершенным паросочетанием} в графе называется набор рёбер такой, что из каждой вершины выходит ровно одно ребро этого набора. В двудольном графе с долями $S$ и $T$ есть хотя бы одно совершенное паросочетание. Докажите, что можно расставить на рёбрах графа попарно различные действительные числа так, что
\begin{itemize}
    \item если в каждой вершине доли $S$ выбрать по ребру с наименьшим числом, то получится совершенное паросочетание;
    \item если в каждой вершине доли $T$ выбрать по ребру с наибольшим числом, то получится совершенное паросочетание. 
\end{itemize}
\source Олимпиада им. Миклоша Швейцера, 2024

\q6. Отрезки $BE$ и $CF$~--- биссектрисы углов $B$ и $C$ остроугольного неравнобедренного треугольника $ABC$, пересекающиеся в точке $I$. Точка $N$~--- середина меньшей дуги $BC$ описанной окружности $\Omega$ треугольника $ABC$. Точка $X$ на дуге $BAC$ окружности $\Omega$ такова, что $NX \perp EF$. Пусть точки $P$ и $Q$ являются серединами дуг $XB$ и $XC$, содержащих вершины $C$ и $B$ соответственно. Докажите, что описанная окружность треугольника $IEF$ касается $\Omega$ тогда и только тогда, когда прямые $BP$, $CQ$ и $EF$ пересекаются в одной точке или параллельны.
\source Я. Щербатов


\q7. Определим многочлены $f_n(x)$ формулами $$f_1(x)=x^2+x,\qquad f_{n+1}(x)=f_n(x)\cdot \bigl(f_n(x)+2^{2^{n-1}-1}\bigr).$$ Докажите, что при любом $n\geq 3$  многочлен  $$f_n(x)+2^{2^{n-1}-1}$$ раскладывается в произведение двух многочленов с целыми коэффициентами одинаковой степени.
\source R. Stanley, D. Grinberg, M. Alexeyev

\noindent\phantom{11}{\bf Замечание.} Функция $f_n(x)$ возникает во время изучения количества циклов в перестановках некоторых подгрупп группы перестановок. 

}
