\documentclass[a4paper,10pt]{article}                
\usepackage{amssymb}                        
\usepackage{amsmath}                        
\usepackage[utf8]{inputenc}   
\usepackage[T1,T2A]{fontenc}   
\usepackage[russian]{babel}   
\usepackage{pict2e} 
\usepackage[e]{esvect}

\pagestyle{empty}                           
\hoffset=-1in %всю страницы влево
\voffset=-1in %всю страницу вверх
\headheight=0in %высота колонтитула
\headsep=0in %отступ от колонтитула
\textheight=282truemm	                 
\textwidth=195truemm          
\oddsidemargin=7.5mm %отступ от левого края
\topmargin=7.5mm %отступ от верхнего края

\long\def\q#1. #2\par #3{%
\smallskip\noindent\phantom{1}{\bf #1.} {\it #2}\par \smallskip #3 \par \smallskip}
\def\ans#1\par{\if*#1 \relax\else\noindent\phantom{1}{\bf Ответ: } #1 \fi}
% если написать в заготовке \ans* то просто будет пустое место
\def\sol#1 {\noindent\phantom{1}\ifcat1#1{\bf Решение #1. } \else{\bf Решение.} #1 \fi}
% можно писать \sol \sol1 \sol2 ... \sol9 все корректно обработает
\def\r {\smallskip\noindent\phantom{1}$\blacklozenge$ }

\newcommand{\divby}{\mathrel{\smash{\lower.5ex\hbox{$\,\vdots\,$}}}}
\newcommand{\ndivby}{\centernot\divby}
\newcommand{\overarc}[1]{\ooalign{\hfil\scalebox{0.9}{$#1$}\hfil\cr\hfil\raisebox{12pt}{\rotatebox{-90}{\scalebox{1}{$)$}}}\hfil\cr}}

\let\leq\leqslant
\let\geq\geqslant


\begin{document}



\sloppy

\centerline{LXIII УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 27.10--02.11.2024}\par
\medskip \par
\centerline{\bf Решения задач командной олимпиады 8 класса}\par



\q1.  При каких натуральных $n$ из чисел $n$, $n+1$, \dots, $n^2$ можно 
выбрать четыре разных числа $a$, $b$, $c$, $d$ так, что $ab=cd$? 
% Чехия, 2004/05, категория C, школьный этап 
% тч, 41

{\ans При всех $n \geq 3$. \sol Заметим, что если $n \geq 6$, то среди чисел от $n$ до $n^2$ найдутся числа $n, 2n, 3n$ и $6n$, для которых верно $n \cdot 6n = 2n \cdot 3n$. То есть все $n \geq 6$ подходят. Для $n = 5$ и $n = 4$ можно взять числа $8, 10, 12, 15$, для которых $8 \cdot 15 = 10 \cdot 12$. Для $n=3$ можно взять числа $3, 4, 6, 8$, для которых $3 \cdot 8 = 6 \cdot 8$. Для $n = 1$ и для $n = 2$ нетрудно показать, что такой четверки чисел не найдется. }

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

%Беларусь-2022, 3 этап, 11 класс.

\ans Второй.

\sol Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Поэтому будем следить только за суммой цифр. Кроме того, заменим каждую цифру на её остаток от деления на 3. Тогда на доске записано 12 нулей, 12 двоек и 11 единиц. Следовательно, изначально сумма имеет остаток 2 от деления на 3. Стратегия за второго: если первый вычеркивает 0, то второй тоже вычеркивает 0, если первый вычеркивает 1, то второй вычеркивает 2. Заметим, что второй всегда сможет играть по такой стратегии, так как нулей четное число и двоек больше, чем единиц. Кроме того, после хода второго сумма цифр всегда имеет остаток 2 от деления на 3, поэтому если первый зачеркивает 2, то проигрывает. Второй всегда может не проиграть, игра конечна, следовательно, проиграет первый.

\q3. На стороне $AB$ четырёхугольника $ABCD$, в котором $\angle A = 45^\circ$, $\angle B = 90^\circ$ и $\angle C = 135^\circ$, нашлась такая точка $E$, что $BC = CD= AE$. Докажите, что треугольник $BDE$ --- равнобедренный.
%А. Кузнецов
% гео из 7го

{\sol Продлим $AB$ и $DC$ до пересечения в точке $F$, тогда $\angle{AFD}=45^{\circ}$. Треугольники $AFD$ и $BFC$ --- прямоугольные равнобедренные, отсюда $BF=BC=AE$ и $AD=DF$. Треугольники $ADE$ и $BDF$ равны по первому признаку, значит $DE=DB$.
}

\q4. Найдите наименьшее натуральное число $N$ такое, что в любой таблице $2 \times 2024$, заполненной числами $1,2, \ldots, 4048$, можно выбрать по одному числу в каждом столбце так, чтобы в каждой строчке было выбрано $1012$ чисел и сумма выбранных чисел была не меньше $N$.
%Финал Абельконкуррансен 2024, Норвежский MO
% комби 198

{\ans $\frac{1+2+\ldots+4048}2 = 1012\cdot 4047 = 4\, 095\, 564$.

\sol Докажем, что всегда можно выбрать числа с суммой хотя бы $2024\cdot 4047$. Пусть $A$ это сумма первых 2024 чисел в первой строке и последних 2024 чисел во второй строке. А $B$ сумма всех остальных чисел. Тогда выборы чисел $A$ и $B$ подходят под условие и $A+B = 1+2+\ldots+4048 = 2024\cdot 4047$. Значит, одно из них хотя бы $1012\cdot 4047$. 

Теперь приведём пример таблицы, для которой больше не получится. Расставим в первой строке слева направо числа $1,3,5, \ldots, 4047$, а во второй строке слева направо числа $2,4,\ldots, 4048$. Пусть $A$ это сумма выбранных чисел из условия. Тогда взяв в каждом столбце другое число, то сумма чисел не изменится, так как в каждой строке мы выбрали поровну чисел, в каждом столбце нижнее число на 1 больше. Значит, мы получили, что $2A = 1+2+\ldots+4048$, то есть $A = 1012 \cdot 4047$.}

\q5. На доске написаны по одному разу все натуральные числа от 2 до 2025. Каждую 
минуту Вася выбирает на доске какие-нибудь два числа $x$ и $y$, стирает 
их, а вместо них пишет число $xy\over xy+(1-x)(1-y)$. Через 2023 минуты 
на доске останется одно число. Найдите все возможные значения этого числа. 
% Испания, местный этап, 2023 
% алг, 165

{\ans $-\frac1{2025}$

\sol Пусть на доске написаны числа $x_1,x_2,\ldots, x_n$. Докажем, что при каждой операции произведение $(1-\frac1{x_1})(1-\frac1{x_2})\ldots(1-\frac1{x_n})$ не меняется по модулю, но меняет знак. Действительно, пусть мы заменили числа $x$ и $y$. Тогда до операции их <<вклад>> в произведение был $(1-\frac1{x})(1-\frac1{y}) = \frac{(x-1)(y-1)}{xy}$. А после операции <<вклад>> новой переменной равен $1-\frac{xy+(1-x)(1-y)}{xy} = -\frac{(x-1)(y-1)}{xy}$, то есть произведение скобок вида $(1-\frac1{x_i})$ поменяет знак. Всего операций $2023$. Значит, знак сменится нечётное число раз, и последнее число равно $-(1-\frac1{2})(1-\frac1{3})\ldots(1-\frac1{2025}) = -\frac12\cdot \frac23\cdot \ldots \cdot \frac{2024}{2025} = -\frac1{2025}$. }

\q6. Дан полный граф $K_n$ на $n$ вершинах и натуральное число $k<n$. В графе $K_n$ заданы направления ребер так, что для любого набора $A$ из $k$ вершин этого графа можно найти вершину $v\notin A$, для которой все ребра $va$, $a\in A$, направлены от $v$ к $a$.  Докажите, что $n\geq 2^{k+1}-1$.
%25вес-КК  Вопрос от Эрдеша. 
%On a Problem in Graph Theory
%P. Erdos The Mathematical Gazette, Vol. 47, No. 361 (Oct., 1963), pp. 220-223 (4 pages) https://doi.org/10.2
%https://www.jstor.org/stable/3613396
%Индукция по $k$. Элементарно, но напрягает.
% комби 6

{\sol Докажем утверждение задачи индукцией по $k$. База. При $k = 1$ двух вершин не хватит. То есть вершин должно быть хотя бы $2^2-1 = 3$. Переход. Суммарно ориентированных рёбер $\frac{n(n-1)}2$. Значит, из какой-то вершины выходит не менее $\frac{n-1}2$ рёбер. Пусть $v$ --- вершина наибольшей степени, $A$ --- это все вершины, из которых ведут рёбра в $v$, а $B$ --- это все вершины, в которые ведут рёбра из $v$. Из доказанного следует, что $|B| \geq \frac{n-1}2$, а $|A| \leq \frac{n-1}2$. Заметим, что $|A| > k-1$. Действительно, если это не так, то для вершин $A \cup v$ не найдется вершины, из которой все рёбра направлены к $A \cup v$, так как из других вершин нет рёбер, ведущих в $v$. Но $|A \cup v| \leq k$, противоречие.

Пусть $X$ --- произвольное множество из $k-1$ вершины графа $A$. В изначальном графе для вершин $X \cup v$ существовала вершина $a$, из которой все рёбра были направлены к $X \cup v$. Так как из $B$ рёбра не ведут в вершину $v$, то $a \in A$. Значит, для любого множества $X$ из $k-1$ вершины в $A$ найдется такая вершина $a \in A$, что все рёбра между $a$ и $X$ направлены в $X$. По предположению индукции $|A| \geq 2^k-1$. Следовательно, $|A\cup v \cup B| \geq (2^k-1)+1+(2^k-1) \geq 2^{k+1}-1$. Индукционный переход доказан.}


\q7. На стороне $BC$ параллелограмма $ABCD$ отмечена точка $P$, а на отрезке $PC$ --- точка $Q$. На отрезке $AP$ отмечена точка $R$, а на отрезке $DQ$ --- точка $S$, причем $BR$ параллельно $DQ$ и $AP$ параллельно $CS$. На стороне $AD$ выбрана точка $T$ так, что углы $ATR$ и $DTS$ равны. Докажите, что $PS + QR > RT+TS$.

{\sol Заметим, что $APQD$~--- трапеция $AD \parallel PQ$, тогда $RPQS$~--- выпуклый четырёхугольник, а значит $RQ + PS > PR + QS$. Тогда $RQ > RP$ или $SP > SQ$. Пусть без ограничения общности $RQ > RP$. Тогда $PS + QR > PS + PR$. Отметим $O$~--- центр параллелограмма $ABCD$. Заметим, что при симметрии относительно $O$ точки $A$ и $C$ меняются местами, точки $B$ и $D$ меняются местами и в силу паралельностей $BR \parallel DS$ и $AR \parallelо CS$ точки $R$ и $S$ тоже меняются местами. Отразим точку $P$ относительно $O$ и получим точку $P'$, лежащую на стороне $AD$. Тогда $PS + QR > PS + PR = P'S + P'R$. Пусть $S'$~--- точка симметричная $S$ относительно прямой $AD$. Тогда $\angle ATR = \angle DTS = \angle DTS'$, а значит точки $R$, $T$ и $S'$ лежат на одной прямой. Тогда $PS + QR > P'S + P'R = P'R + P'S' \geq RS' = RT + TS' = RT + TS$.}


\q8. Дано натуральное $b>2$. Оказалось, что существует натуральное $n$, такое что число $n^2+1$ можно представить в виде суммы слагаемых вида $b^k-1$ с натуральными~$k$, использовав каждое слагаемое не более $b-1$ раз. Докажите, что таких $n$ бесконечно много. 
% Индия, 2025 
% https://artofproblemsolving.com/community/c6h3483098p33764203

{\sol Если $n^2 + 1 = \sum_{i = 1}^m a_i (b^i - 1)$, то $n^2 + 1 \divby b - 1$, а значит $-1$~--- квадратичный вычет по модулю $b - 1$. Тогда рассмотрим $0 \leq r < b$~--- такое число, что $r^2 + 1 \divby b - 1$. В качестве такого $r$ например можно взять остаток при делении $n$ на $b$. Без ограничения общности можно считать, что $r \leq b / 2$, ведь иначе можно рассмотреть $b - r$. Тогда $a = \frac{r^2 + 1}{b - 1} \leq \frac{b^2 + 4}{4(b - 1)} = b - \frac{3b^2 - 4b - 4}{4(b - 1)} = b - \frac{(b - 3)(3b + 5) + 11}{4(b - 1)} < b$. То есть $a \leq b - 1$. Теперь заметим, что для любого натурального $k > 1$ выполнено равенство $(b^k + r - 1)^2 + 1 = (b^{2k} - 1) + 2(r - 1)(b^k - 1) + a(b - 1)$, причем $2(r - 1) \leq b - 1$ и $a \leq b - 1$, а значит число $(b^k + r - 1)^2 + 1$ представимо в необходимом нам виде.

}

\end{document}



\qзапас. По кругу стоят $n$ работников компании, которые хотят выбрать директора. Сначала каждый голосует за соседа справа. Затем происходит $n$ раундов переголосования. За один раунд все работники в некотором порядке меняют свои голоса: если сейчас меняет свой голос работник $A$ и текущей его голос за $B$, а сейчас $B$ голосует за $C$, то $A$ свой голос отдает за $C$. В каждом раунде может быть свой порядок голосования, но каждый голосует один раз. Докажите, что через $n$ раундов все единогласно будут голосовать за одного и того же человека.
% Канада, юниоры, 2025

Пусть раунд $0$ будет начальным состоянием (до любого обновления голосов). Определим $G_i$ как ориентированный граф, в котором $n$ игроков являются вершинами, а ориентированные рёбра представляют голоса после раунда $i$ для всех $i \in \{0,1,\dots,n\}$.

$\textbf{Лемма:}$ $G_i$ содержит единственный цикл, и длина этого цикла не превосходит $n - i$. Кроме того, любая вершина вне цикла является частью ориентированного пути длины не более $n - i$.

$\textbf{Доказательство:}$ Проведём индукцию по $i$.

$\textbf{База индукции:}$ $i = 0$ (тривиально).

$\textbf{Предположение индукции:}$ Предположим, что лемма верна для всех $i < k \leq n$.

$\textbf{Шаг индукции:}$ Пусть $v_1, v_2, \dots, v_t$ — вершины цикла в $G_{k-1}$ такие, что $v_i \to v_{i+1}$ и $v_{t+1} = v_1$, где $v_1$ — первая вершина, обновляющая свой голос в раунде $k$.

Заметим, что теперь $v_1 \to v_3$, то есть $v_2$ больше не входит в цикл в $G_k$. Отметим, что единственный способ, по которому вершина $v_j$ может покинуть цикл и стать частью ориентированного пути (т.е. больше не находиться ни в каком цикле), — это если существует вершина $w$ в цикле, такая, что $w$ голосует за $v_j$, а $v_j$ ранее принадлежала циклу...($\alpha$).

Теперь проверим, что любой ориентированный путь вне цикла имеет длину не больше $n - k$. По предположению индукции, все такие пути в $G_{k-1}$ имеют длину не больше $n - k + 1$. В каждом раунде длина каждого пути уменьшается по крайней мере на $2$ от самой внешней вершины по направлению к циклу, в то время как она увеличивается не более чем на $1$ на конце, примыкающем к циклу (согласно ($\alpha$)). Следовательно, длина любого пути не больше $n - k$.

На этом индукция завершена. Применяя лемму к $G_n$, заключаем, что все $n$ игроков в конечном итоге будут голосовать за одного и того же человека. $_\blacksquare$