\documentclass[a4paper,12pt]{article}
%Убираем нумерацию страниц
\pagestyle{empty}
%Кодировка, на которую пока-что почему-то ругается overleaf
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[russian]{babel}
\usepackage{graphicx}


\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.9}
\usepackage{mathrsfs}
\usepackage{wrapfig}


\usepackage[a4paper, top=0.8cm,bottom=0.6cm,left=0.8cm,right=0.8cm,
marginparwidth=1.75cm]{geometry}               
\renewcommand{\baselinestretch}{0.99}   
% \usepackage{amsfonts} %Границы отступов печати
% \usepackage[a4paper, top=0.5cm,bottom=0.5cm,left=1cm,right=1cm,
% marginparwidth=1.70cm]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{pdflscape}
\usepackage{multicol}

\def\vec{\overrightarrow}

\def\geq{\geqslant}
\def\ge{\geqslant}
\def\leq{\leqslant}
\def\le{\leqslant}
\def\vec{\overrightarrow}
\def\ol{\overline}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\kratno{\mathrel{\smash{\lower.2ex\hbox{$\vdots$}}}}
\def\ep{\varepsilon}                     
\renewcommand{\baselinestretch}{0.95}   

\newcounter{zadacha}



\newif\ifPrintSolutions
\PrintSolutionstrue
 %\PrintSolutionsfalse %закоментировать, чтобы были решения
\large
\long\def\q#1. #2\par #3 \par{%
\ifPrintSolutions
\par\smallskip\noindent\phantom{1}{\textbf{#1.}} {\it #2}\par #3 \par\smallskip %
\else%
\noindent\phantom{1}{\textbf{#1.}} {#2}\par\medskip  %
\fi}

\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\name#1\par#2\par{
\ifPrintSolutions \noindent\phantom{1}{#2}
\else
\noindent\phantom{1}{#1}
\fi}
      
\begin{document}                            	
%\begin{landscape}
%\setlength{\columnsep}{10mm} 
%\begin{multicols}{2}




\centerline{LXV УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. ПОКРОВСКОЕ, 26\,--\,31.10.2025}
\medskip



\large

\centerline{\bf КОМАНДНАЯ ОЛИМПИАДА. МЛАДШАЯ ГРУППА.}


\medskip

\q1.  Найдите все такие пары простых чисел $p$ и $q$, для которых остаток от деления $p^2$ на $q$ равен неполному частному.
%А. Кузнецов

{\ans $p=2; q=3$. \sol Обозначив неполное частное и остаток за $x$, получим равенство $p^2=qx+x=x(q+1)$. Тогда $q+1$~--- делитель числа $p^2$. Если $p=2$ --- чётно, то подойдёт только $q+1=4$, т.е. $q=3$. Подставив, получим верное равенство $2^2=3\cdot 1+1$. Если $p$ --- нечётно, то нечётно и $q+1$, т.е. $q=2$. Тогда может быть только $p=3$, но подстановкой можно убедиться, что остаток $x$ окажется больше делителя.
}


\q2. Робот-альпинист поднимается в гору со скоростью 2 км/ч, а спускается
--- со скоростью 3 км/ч. На середине его маршрута расположена вертолётная площадка, а в другом месте вдоль его маршрута --- базовый лагерь.
Робот поднялся с подножия горы до её вершины, а затем спустился до базового лагеря, причём подъём занял на 12 часов больше времени, чем спуск (по пути робот не делает остановок). Далее робот должен был спуститься к подножию горы, однако из-за возможного ухудшения погоды было решено эвакуировать его на вертолёте. Чтобы добраться до вертолётной площадки от базового лагеря, роботу потребовался 1 час. Сколько времени занял бы у робота спуск от базового лагеря до подножия горы?
%А. Кузнецов
% Либо 5:40, либо 6:30. (Паша)

{\ans 5 часов 40 минут либо 6 часов 30 минут. \sol Пусть длина всего маршрута от подножия до вершины равна $S$ километров. В конце всех передвижений робот оказывается ровно посередине маршрута, т.е. на расстоянии $\frac{S}{2}$ от вершины. Это расстояние равно $3\left(\frac{S}{2}-12\right)-2$ либо $3\left(\frac{S}{2}-12\right)+3$ километрам, в зависимости от того, куда направился робот для эвакуации (первое выражение --- вверх, второе --- вниз). В первом случае $S=38$ км, а роботу осталось преодолеть $\frac{S}{2}-2=17$ км со скоростью $3$ км/ч, на что требуется 5 часов 40 минут. Во втором случае $S=33$ км, а роботу осталось $\frac{S}{2}+3=19.5$ км, на что требуется 6 часов 30 минут.

}

\q3. Саша посчитал, сколькими способами можно выбрать несколько (хотя бы одно) различных натуральных чисел, меньших миллиона, таким образом, чтобы как произведение, так и сумма выбранных чисел были чётны. На какую цифру оканчивается результат?
%6.4 MODIF

{\ans $6$. \sol Раз произведение чётно, то выбрано хотя бы одно чётное число. Всего чётных чисел, меньших миллиона, 499999. Следовательно, способов выбрать чётные числа $2^{499999}-1$. Чтобы сумма выбранных чисел была чётна, нужно выбрать чётное число нечётных чисел. Способов сделать это $2^{499999}$, так как для каждого способа взять или не взять каждое из чисел $1$, $3$, \ldots, $999997$, есть ровно один способ взять или не взять $999999$, чтобы в итоге было выбрано чётное число нечётных чисел. Числа $2^{499999}$ и $2^{499999}-1$ оканчиваются соответственно на $8$ и $7$. Тогда последняя цифра числа $2^{499999}\cdot (2^{499999}-1)$ равна 6.
}

%\q3old. В двух углах доски $n \times n$ расположены белый и чёрный ферзь, а остальные клетки доски заполнены зелёными фигурами. За ход разрешается съесть фигуру другого цвета. Игрок побеждает, если он съедает фигуру соперника или если соперник не может сделать ход. При каких значениях $n$ первый игрок имеет выигрышную стратегию?
% https://artofproblemsolving.com/community/c6h3621571p35493047, India-Iran-Singapore-Taiwan Friendly Contest 2025 Problem 1
%очень тупая комбинаторика. Игра+хрень
%может быть сложно отличать решение от не решения?


\q4. Найдите все такие натуральные числа $a$, $b$, $c$, что $ab-1$ делится на $bc+1$ и $bc-1$ делится на $ac+1$.
%А. Кузнецов
% Все единицы?
%поправил
% $abc^2+1$ делится на $ac+1$ и $acb^2+1$ делится на $bc+1$


%\q4alt. По кругу выписаны $n$ целых чисел. Оказалось, что между каждыми двумя числами можно вписать целое число так, что каждое старое число было равно сумме своих соседей. Затем новые числа стерли, а старые переставили. При каких натуральных $n$ всегда можно снова вписать новые числа с тем же свойством?

{\ans $a$ --- любое нечётное число, $b = 1$, $c=1$.

\sol Если $ab-1$ делится на $bc+1$, то и $ab-1+bc+1 = b(a+c)$ делится на $bc+1$. Но $b$ взаимно просто с $bc+1$, поэтому $a+c$ делится на $bc+1$. Из аналогичных рассуждений получаем, что $a+b$ делится на $ac+1$. Сначала рассмотрим случай $c \geq 2$. Тогда $a+b \geq 2a+1$, откуда $b \geq a+1$. Но с другой стороны $a+c \geq bc+1$, откуда $a \geq c(b-1)+1 \geq 2b-1 \geq 2(a+1)-1 = 2a+1$~--- противоречие. 

Осталось разобрать случай $c = 1$. Тогда $a+1$ делится на $b+1$, и кроме того $a+b$ делится на $a+1$. То есть $a+b$ в частности делится на $b+1$. Но тогда и $(a+b)-(a+1) = b-1$ делится на $b+1$, откуда $b = 1$. Осталось лишь заметить, что в качестве $a$ можно взять любое нечётное число. 

}

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

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

\centerline{\includegraphics[width=150pt]{pic/65_kom.pdf}}
}

\q6. Дано натуральное число $k$. В стране 2025 городов. Некоторые пары городов (но не все!) соединены двусторонними авиалиниями. Оказалось, что для любых двух городов, между которыми нет прямого авиасообщения, суммарное количество исходящих из них авиалиний равно $k$. Чему может быть равно $k$?
% Надо точно добавить, что граф не является полным

{\ans Все чётные $k$ от 0 до 4046 и нечётные $k$ от 2023 до 4045. \sol Рассмотрим граф, в котором города --- вершины, авиалинии --- рёбра. Степени двух несмежных вершин графа не превосходят 2023, поэтому $k\leq 4046$. Пусть $k<2023$ --- нечётно. Тогда для двух несмежных вершин $A$ и $B$ найдётся вершина $C$, с которой они тоже не соединены. Степени каких-то двух из них имеют одинаковую чётность, потому их суммарная степень не равна $k$. Противоречие. Для всех остальных $0\leq k\leq 4046 $ построим пример. \\  
Для $k=0$ подойдёт страна без авиалиний. \\ 
Для чётных $k=2m+2$, где $m\geq 0$, выберем столицу, соединим её со всеми городами, а остальные города разобьём на две доли из 1012 городов. Обозначим города одной доли за $a_i$, второй --- за $b_i$. Каждый город $a_i$ соединим с городами $b_{i+1}, \ldots, b_{i+m}$ (индексы берутся по модулю 1012). Тогда степени всех именованных вершин будут равны $m+1$, и для любых двух несмежных вершин сумма их степеней будет равна $k$. \\
Для нечётных $k=2023+2m$, где $m\geq 0$, выберем город $A$ и ещё $2024-2m$ городов, отличных от $A$. Соединим все пары городов, кроме пар, состоящих из $A$ и выбранного города. Тогда из выбранных городов выходит 2023 авиалинии, а из $A$ выходит $2024-(2024-2m)=2m$ авиалиний, что в сумме даёт $k$.
}


\q7. Натуральное число $N$ имеет ровно 2025 различных простых делителей. Все его делители выписали в строчку в порядке возрастания $1 = d_1 < d_2 < \ldots < d_k = N$. Могло ли оказаться, что число $d_2/d_1 + d_3/d_2 +  \ldots  + d_k/d_{k-1}$ целое?
% Does there exist a positive integer $N$ which is divisible by at least 2025 distinct primes and whose
% positive divisors $1 = d_1 < d_2 < \ldots < d_k = N$ are such that the number $d_2/d_1 + d_3/d_2 +  \ldots  + d_k/d_{k-1}$ is an integer?
% Нравится, но возможно она проще графа. (Паша)

{\ans Могло. \sol Будем доказывать индукцией по $n$, что существует натуральное $N$ с ровно $n$ простыми делителями, для которого соответствующее число $d_2/d_1 + d_3/d_2 +  \ldots  + d_k/d_{k-1}$ целое. Для $n = 1$ достаточно взять $N$ равным любому простому числу. Предположим, что уже построено число $N$, имеющее ровно $n$ простых делителей, и для которого число $d_2/d_1 + d_3/d_2 +  \ldots  + d_k/d_{k-1}$ целое, где $1 = d_1 < d_2 < \ldots < d_k = N$ --- все делители $N$. Выберем простое число $p> N$. Положим $M = N\cdot p^{s}$. Тогда, если выписать все делители $M$ по возрастанию, мы получим ряд
$$1 = d_1 < d_2 < \ldots < d_k< d_1\cdot p< d_2\cdot p < \ldots< d_k\cdot p < \ldots < d_1\cdot p^s< d_2\cdot p^s< \ldots< d_k\cdot p^s.$$
А соответствующая сумма равна 
$$\left(\frac{d_2}{d_1} + \frac{d_3}{d_2} +  \ldots  + \frac{d_k}{d_{k-1}}\right)+ \frac{d_1\cdot p}{d_k}+\left(\frac{d_2\cdot p}{d_1\cdot p} + \frac{d_3\cdot p}{d_2\cdot p} +  \ldots  + \frac{d_k\cdot p}{d_{k-1}\cdot p}\right)+\frac{d_1\cdot p^2}{d_k\cdot p}+\ldots$$
$$+\frac{d_1\cdot p^{s}}{d_k\cdot p^{s-1}}+\left(\frac{d_2\cdot p^s}{d_1\cdot p^s} + \frac{d_3\cdot p^s}{d_2\cdot p^s} +  \ldots  + \frac{d_k\cdot p^s}{d_{k-1}\cdot p^s}\right) =s\cdot \frac{d_1\cdot p}{d_k}+(s+1)\cdot\left(\frac{d_2}{d_1} + \frac{d_3}{d_2} +  \ldots  + \frac{d_k}{d_{k-1}}\right).$$
Положим $s = d_k$. Тогда число $s\cdot \frac{d_1\cdot p}{d_k}$ целое, а число $(s+1)\cdot\left(\frac{d_2}{d_1} + \frac{d_3}{d_2} +  \ldots  + \frac{d_k}{d_{k-1}}\right)$ целое по предположению индукции. Таким образом, переход доказан. 

}


\q8. Пусть $a, b, c$ --- длины сторон треугольника, периметр которого равен 2. Докажите, что $$a^2b+b^2c+c^2a+ab+bc+ca > 2.$$
%А. Кузнецов
%тут лучше по другому сформулировать, не все могут знать, что такое стороны треугольника. (АС)
%например: разность любых двух меньше третьего.

{\sol По неравенству треугольника $a+b>c$, значит $c$ меньше полупериметра, который равен 1. Аналогично с $a$ и $b$. Тогда $$a(a-1)(b-1)+b(b-1)(c-1)+c(c-1)(a-1)>0.$$
Раскрыв скобки, получим $$a^2b+b^2c+c^2a-a^2-b^2-c^2-ab-bc-ca+a+b+c > 0.$$
Преобразуем неравенство к виду
$$a^2b+b^2c+c^2a+ab+bc+ca > a^2+b^2+c^2+2(ab+bc+ac)-a-b-c=(a+b+c)^2-a-b-c=2.$$

}






%{\ans \sol }

\end{document}



