\documentclass[a4paper,12pt]{article}                
\usepackage{amssymb, amsmath, graphicx, wrapfig}                        
\usepackage{amsmath}                        
\usepackage[utf8]{inputenc}               
\usepackage[russian]{babel}                 
\pagestyle{empty}          
\def\kratno{\mathrel{\smash{\lower.1ex\hbox{$\,\vdots\,$}}}}
\usepackage[a4paper, top=0.8cm,bottom=0.6cm,left=0.8cm,right=0.8cm,
marginparwidth=1.75cm]{geometry}               
\renewcommand{\baselinestretch}{0.9}    

\input urtur.sty
%\input CELLS.STY

% ДЛЯ ОТСУТСТВИЯ РЕШЕНИЙ ВЫСТАВИТЬ ВТОРОЙ АРГУМЕНТ НА 0
% ДЛЯ НАЛИЧИЯ -- НА 1
\setcounter{ifsol}{1}

%%ДЛЯ УКАЗАНИЯ ИЛИ СКРЫТИЯ ИСТОЧНИКОВ/АВТОРОВ ЗАДАЧ
\setcounter{ifSource}{1}

\def\data{27.10.2025}
\newcounter{TurNumber}
\setcounter{TurNumber}{1}


\begin{document}

\ifnum\value{ifsol}=0 \large \fi


\MathBattleHead{\arabic{TurNumber}}{\data}{ВЫСШАЯ}{высшая}

\def\concap{
\ifnum\value{ifsol}=1
{\noindent\textbf{Конкурс капитанов.} 
На доске написаны числа $1,2,3,\dots, 150$. Сначала стёрли каждое третье число, начиная с двойки. Потом стёрли каждое пятое из оставшихся, начиная с единицы. Сколько чисел осталось?
\ans{80.}
}
\fi
}

\concap 

\ifnum\value{ifsol}=0
{\vspace{-0,5cm}
}
\fi


\q1.one В школе учится несколько человек, некоторые из которых дружат друг с другом. Каждый ученик пронумеровал своих друзей числами от 0 до $n-1$, где $n$~--- количество его друзей. Изначально, у каждого ученика есть по яблоку. В нулевой день каждый ученик передал своё яблоко своему другу с номером $0$, и у всех снова оказалось по яблоку. В первый день каждый передал своё яблоку своему другу номер 1, и у всех снова оказалось по яблоку. И так далее: в день номер $d$ человек, у которого $n$ друзей, передает свое яблоку другу с номером, равным остатку $d$ от деления на $n$. Через некоторое время оказалось, что каждый человек снова собирается отдать свое яблоко нулевому другу. Докажите, что если два человека дружат, то у них поровну друзей.

{\source{USA TSTST 2025/1}

\sol{Рассмотрим граф, в котором вершины~--- ученики, рёбра~--- дружба. Предположим, что в нём есть две соседние вершины с разной степенью. Это означает, что есть компонента связности $C$ этого графа, в которой не все степени одинаковы. Рассмотрим эту компоненту и выберем в ней вершину $v$ наибольшей степени, которая смежна с вершиной меньшей степени. 

Пусть степень $v$ равна $d$, а степени её соседей $x_1\leqslant d$, $x_2\leqslant d$, \ldots, $x_d < d$. И пусть к моменту, когда каждый человек собирается передать яблоко нулевому другу прошло $n$ дней. Тогда $n \kratno x_i$ для любого~$i$. И от вершины со степенью $x_i$ вершина $v$ получала яблоко ровно $n/x_i$ раз. Следовательно, за $n$ дней $v$ получала яблоко  $n/x_1+n/x_2+\ldots+ n/x_d > n(1/d+1/d+\ldots+1/d)=n$ раз. Противоречие.
}
}


\q2.two Можно ли выбрать 17 натуральных чисел от 1 до 100 так, чтобы для любых двух выбранных чисел выполнялось условие: $a$ делится на $b$ тогда и только тогда, когда $s(a)$ делится на $s(b)$ ($s(n)$ обозначает сумму цифр числа $n$)?

{\source{JBMO 2023 Shortlist Albania NT5, упрощение }

\ans{Да.} \sol{Нетрудно проверить, что подойдут числа 1, 3, 5, 7, 9, 11, 22, 33, 44, 55, 66, 77, 88, 89, 92, 94, 99.}
} 

\q3. В ряд выписаны числа $1$, $2$, \ldots, $100$ в некотором порядке. Каждым ходом Алиса меняет местами два соседних числа в ряду. Её цель~--- сделать так, чтобы никакие три
подряд идущих числа в ряду не стояли в возрастающем или убывающем порядке.
Найдите наименьшее натуральное число $k$, такое что для любого изначального ряда Алиса может достичь своей цели, сделав не более чем $k$ ходов.

{\source{2025 Taiwan TST Round 3 Independent Study 1-C s14}

\ans{49.} \sol{Разобьём все числа на 50 пар. Докажем, что Алиса может последовательно рассматривать пары и для каждой следующей пары делать не более одного хода, избегая появления монотонных троек. Действительно, пусть последняя пара $a$, $b$, а следующая $c$, $d$. Не умаляя общности, $a<b$. Если монотонных троек не появилось, то Алиса переходит к следующей паре. Разберем два случая.

Случай 1. $d<b$. Тогда монотонная тройка или $b>c>d$, или $a<b<c$. В любом случае $c>d$. Переставляя $c$ и $d$ получим $a<b>d<c$.

Случай 2. $d>b$. Тогда $c>b$, иначе монотонных троек нет. Алиса переставляет $b$ и $c$ и получает $a<c>b<d$. 

В итоге для каждой пары, кроме самой первой, не более одного хода и всего не более 49 ходов.

Заметим, что если изначально числа идут в порядке возрастания, то в одну из пар 1,2 и 2,3 необходимо сделать ход, также в одну из пар 3,4 и 4,5; 5,6 и 6,7\ldots 97,98 и 98,99 --- итого не менее 49 ходов.

\r Только оценка или только пример: 4 балла.
}
} 

\q4.four На доске записаны все натуральные числа от 1 до $n$  в некотором порядке. Любое натуральное число от 1 до $n(n+1)/2$  можно получить как сумму нескольких записанных подряд чисел. Для каких натуральных значений $n$ это возможно?

{\source{KoMaL-2025, май}

\ans{ $1$, $2$ и $3$.} \sol{ Примеры: $(1)$, $(1,2)$, $(1,3,2)$.

Докажем, что $n>3$ не подходит. Заметим, что всего различных блоков подряд идущих чисел ровно $n(n+1)/2$, так как $n$ блоков длины 1, $n-1$ блок длины 2, \ldots, $1$ блок длины $n$. Следовательно, во всех блоках должны быть разные суммы чисел. Тогда если рядом с $1$ стоит число $x$, то $1+x>n$, иначе сумма в блоке $(1,x)$ будет совпадать с суммой в блоке $(1+x)$. Значит, $1$ стоит с краю, а рядом с ней стоит $n$. Далее $2$ должна образовывать с соседями суммы, большие $n+1$. Но единственный вариант, когда так происходит, если $2$ стоит с краю, а рядом с ней стоит $n$. Получаем, что ряд выгляди как $(1,n,2)$, что невозможно при $n>3$. 

\r Приведены все ответы с примерами: 2 балла.

\r Доказано, что $n>3$ не подходят: 6 баллов.
}
} 


\ifnum\value{ifsol}=0
{\begin{wrapfigure}[5]{r}{0.2\linewidth} 
\vspace{-2,8em}
\includegraphics[width=\linewidth]{ris/snake-1.png}
\end{wrapfigure}
}
\fi

\q5.five \emph{Змея} в  квадрате $n\times n$~--- это путь, состоящий из прямых отрезков между центрами соседних клеток, проходящий через центры всех $n^2$ клеток ровно по одному разу. (Две клетки считаются соседними, если они имеют общую сторону).  На рисунке показан пример змеи в квадрате размером $4\times 4$. Эта змея делает девять поворотов на $90^{\circ}$, отмеченных маленькими черными квадратами.\\
Какое наибольшее количество поворотов на $90^{\circ}$ может сделать змея \\в квадрате $45\times 45$?

{\source{MEMO 2025}

\ans{$45^2-1-45 =1979$.} \sol{ Пронумеруем клетки пути $c_1$, $c_2$, \dots, $c_{n^2}$.
\begin{wrapfigure}[7]{r}{0.2\linewidth} 
\vspace{-0em}
\includegraphics[width=\linewidth]{ris/snake-3.png}
\end{wrapfigure}

Оценка, способ 1. Не умаляя общности, пусть первый ход сделан в горизонтальном направлении. Докажем, что в каждой строке (кроме, может быть, строки, содержащей конец пути) должна быть хотя бы одна клетка, в которой не происходит поворота, и которая отлична от начала и конца пути. В самом деле, в противном случае клетки строки бились бы на пары --- путь должен прийти в эту строку, повернуть на $90^\circ$, пройти одну клетку, снова повернуть и уйти из строки (если строка является началом пути, то начало тоже занимает две клетки строки). Но 45 не делится на 2, так что хотя бы в 44 строках будет клетка, в которой нет поворота. Также поворотом не являются начало и конец пути. Значит, поворотов не более $45^2-46=1979$.
 
Оценка, способ 2. Раскрасим клетки доски в шахматном порядке так, чтобы углы были черными, а затем черные клетки в нечетных столбцах покрасим в фиолетовый, а в четных~--- в зеленый. Заметим, что в белой клетке $c_i$ произошел поворот тогда и только тогда, когда из клеток $c_{i+1}$ и $c_{i-1}$ одна зеленая, а другая~--- фиолетовая. Следовательно, количество белых клеток, в которых произошел поворот, не превосходит удвоенного количества зеленых клеток. То есть не менее чем в $$\frac{45^2-1}{2} - 2\left(\frac{45-1}{2}\right)^2 = \frac{45^2-1 - 45^2 +2\cdot 45 -1}{2}  =44 $$
белых клетках не произошел поворот. Также поворота не было в двух черных клетках, которые являются началом и концом змеи. Что  и требовалось доказать.


Пример строится последовательным добавлением рамочки ширины 2. Как заполнять рамочку, показано на рисунке.


\r Только оценка или только пример: 4 балла.
}
} 

\ifnum\value{ifsol}=0
{\begin{wrapfigure}[4]{r}{0.19\linewidth} 
\vspace{-4,5em}
\includegraphics[width=\linewidth]{ris/prisma.png}
\end{wrapfigure}
}
\fi
\q6.six На доске нарисованы два 2025-угольника, один из которых лежит внутри другого. Помимо сторон многоугольников, провели ещё 2025 отрезков, каждый из которых соединяет $i$-ую вершину первого многоугольника с $i$-той вершиной второго (на рисунке изображен пример для 8-угольников).  Раскраска всех вершин двух многоугольников в чёрный и белый цвета называется \emph{хорошей}, если для каждой вершины в чёрный цвет покрашено нечётное количество вершин, с которыми она соединена отрезком. Найдите количество  хороших раскрасок.

{\source{Беларусь-2025, 3 этап, 9 класс.}

\ans{4.} \sol{Пусть $A_1$, $A_2$, \dots, $A_{2025}$~--- это последовательные вершины первого многоугольника, а $B_1$, $B_2$,\dots , $B_{2025}$~--- это соответствующие им вершины второго многоугольника. Если все вершины первого многоугольника~--- чёрные, то все вершины второго тоже чёрные. Пусть есть две вершины первого многоугольника через одну разного цвета. Не умаляя общности, $A_1$ - чёрная, $A_3$ - белая. Тогда, рассматривая последовательно соседей вершин $A_2$, $B_3$, $A_4$, $B_5$ и т. д. получим, что вершина $B_2$ белая, $B_4$ чёрная, $A_5$ белая, $B_6$ белая, $A_7$ чёрная, $B_8$ белая, $A_9$ белая и т. д. по циклу. То есть если рассматривать вершины $A_i$ через одну, то цвета идут в порядке чббчббчбб\ldots и, так как 2025 нечётно, но делится на 3, то все вершины однозначно определятся по цвету, а тогда и цвета всех вершин второго многоугольника тоже однозначно определятся. Нетрудно проверить, что такая раскраска, а также ещё две, получаемые из неё циклическими сдвигами, подходят Итого 4 варианта раскраски. 

\r Правильный ответ со всем примерами: 4 балла.
}
} 

\q7.seven На доске написано 100 натуральных чисел.
Известно, что нет двух написанных чисел, отличающихся на 1, и что наибольший общий
делитель всех написанных чисел равен~1.
Докажите, что на доске найдутся два числа такие, что
ни один простой делитель их разности не написан.

{\source{По мотивам Беларусь-2024, 3 этап, 11 класс.}

\sol{Рассмотрим самое маленькое число на доске $a$. Если $a=1$, то ни один простой делитель разности второго по величине числа на доске и $a$ не написан. Если $a>1$, то пусть $b$~--- самое маленькое число на доске, не делящееся на $a$. Рассмотрим число $b-a$. Если какой-то простой делитель этой разности написан на доске, то этот делитель меньше $b$, а тогда он должен делиться на $a$, но тогда и $b$ делится на $a$~--- противоречие. Значит пара $(b,a)$ подходит.}
} 

\q8.eight У Васи есть 30 карточек, на каждой написано натуральное число от 1 до 30 (ровно одна карточка с каждым числом). Вася разложил свои карточки по 10 конвертам так, чтобы в каждом конверте находилось не менее 2 и не более 4 карточек. Для каждого конверта он посчитал сумму чисел на карточках, содержащихся в этом конверте, и получил суммы $S_1 \geqslant S_2  \geqslant \ldots \geqslant S_{10}$.  Найдите наименьшее возможное значение числа~$S_3$.

{\source{KoMaL-2025, май}

\ans{32.} \sol{Заметим, что $S_1+S_2 \leqslant 30+29+\ldots 23$, поэтому $S_3 \geqslant (1+2+\ldots+22)/8 = 253/8 > 31$. Следовательно, $S_3 \geqslant 32$.

Пример на 32:
$$(30,29,28,27),(26,25,24,23),(22,9,1),(21,8,3),(20,7,5),(19,11,2),(18,10,4),(13,12,6),(17,14),(16,15)$$

\r Только оценка или только пример: 4 балла.
}
} 






\newpage

\MathBattleHead{\arabic{TurNumber}}{\data}{ПЕРВАЯ}{первая}

\concap 
\ifnum\value{ifsol}=0
{\vspace{-0,5cm}
}
\fi

\q1. В школе учится несколько человек, некоторые из которых дружат друг с другом, причём у Васи ровно два друга, а у всех остальных по 3. Каждый ученик, кроме Васи, пронумеровал своих друзей числами от 0 до 2. Изначально, у каждого ученика есть по яблоку. В нулевой день каждый ученик, кроме Васи, передал своё яблоко своему другу с номером $0$ (а Вася~--- любому своему другу). В первый день каждый, кроме Васи, передал все свои яблоки своему другу номер 1. И так далее: в день номер $d$ все, кроме Васи, передают свои яблоки другу с номером, равным остатку $d$ от деления на 3, а Вася~--- любому своему другу (если у человек нет яблок, то он ничего не передает). Докажите, что в какой-то момент у кого-то из ребят окажется более одного яблока.  

{\source{USA TSTST 2025/1, упрощение}

\sol{Посмотрим на первые три дня. Каждый из Васиных друзей передавал ему яблоко не более одного раза за эти три дня, поэтому в какой из дней Вася не получил яблока. Следовательно, у кого-то оказалось хотя бы два яблока.}
} 


\two

\q3.three В ряд выписаны числа $1$, $2$, \ldots, $100$ в некотором порядке. Каждым ходом Алиса меняет местами два соседних числа в ряду. Её цель~--- сделать так, чтобы никакие три
подряд идущих числа в ряду не стояли в возрастающем или убывающем порядке.
Может ли для любого изначального ряда Алиса достичь своей цели, сделав менее $50$ ходов? 

{\source{2025 Taiwan TST Round 3 Independent Study 1-C s14}

\ans{Может.} \sol{Разобьём все числа на 50 пар. Докажем, что Алиса может последовательно рассматривать пары и для каждой следующей пары делать не более одного хода, избегая появления монотонных троек. Действительно, пусть последняя пара $a$, $b$, а следующая $c$, $d$. Не умаляя общности, $a<b$. Если монотонных троек не появилось, то Алиса переходит к следующей паре. Разберем два случая.

Случай 1. $d<b$. Тогда монотонная тройка или $b>c>d$, или $a<b<c$. В любом случае $c>d$. Переставляя $c$ и $d$ получим $a<b>d<c$.

Случай 2. $d>b$. Тогда $c>b$, иначе монотонных троек нет. Алиса переставляет $b$ и $c$ и получает $a<c>b<d$. 

В итоге для каждой пары, кроме самой первой, не более одного хода и всего не более 49 ходов.}
} 

\four

\ifnum\value{ifsol}=0
{\begin{wrapfigure}[5]{r}{0.2\linewidth} 
\vspace{-2,8em}
\includegraphics[width=\linewidth]{ris/snake-1.png}
\end{wrapfigure}
}
\fi
\q5. \emph{Змея} в  квадрате $n\times n$~--- это путь, состоящий из прямых отрезков между центрами соседних клеток, проходящий через центры всех $n^2$ клеток ровно по одному разу. (Две клетки считаются соседними, если они имеют общую сторону).  На рисунке показан пример змеи в квадрате размером $4\times 4$. Эта змея делает девять поворотов на $90^{\circ}$, отмеченных маленькими черными квадратами.\\
Докажите, что в квадрате $45\times 45$ змея сделает менее 2000 поворотов \\ на $90^{\circ}$.

{\source{MEMO 2025}

\sol{Заметим, что в каждой строке (кроме, может быть, строк, содержащих начало и конец пути) должна быть хотя бы одна клетка, в которой не происходит поворота. В самом деле, в противном случае клетки строки бились бы на пары --- путь должен прийти в эту строку, повернуть на $90^\circ$, пройти одну клетку, снова повернуть и уйти из строки. Но 45 не делится на 2, так что хотя бы в 43 строках будет клетка, в которой нет поворота. Значит, поворотов не более $45^2-43<2000$.
} }

\ifnum\value{ifsol}=0
{\begin{wrapfigure}[4]{r}{0.19\linewidth} 
\vspace{-4,5em}
\includegraphics[width=\linewidth]{ris/prisma.png}
\end{wrapfigure}
}
\fi
\six

\seven 

\eight



\newpage





\newpage
\MathBattleHead{\arabic{TurNumber}}{\data}{ВТОРАЯ}{вторая}

\concap

\q1. Пираты делили добычу --- мешок монет. Сначала всем раздали поровну монет, но главарь (самый сильный пират) возмутился и отобрал половину монет у последнего (самого слабого). После этого возмутился второй по силе пират и отобрал у самого слабого треть оставшихся у того монет. Третий отобрал четверть, и т.д. до предпоследнего пирата. Сколько всего было пиратов, если монет у главаря оказалось в 9 раз больше, чем у последнего?

{\source{С. Волчёнков}

\ans{6.} \sol{Первое действие увеличило капитал главаря в полтора раза. Капитал последнего (слабого) пирата умножается каждый раз на  $\frac{i}{i+1}$. После пятого умножения получаем требуемый баланс.
\r Только ответ с проверкой: 6 баллов. Задача не решена.
} 
}

\q2. Назовём пару чисел $(a, b)$ {\it зеркальной}, если либо $a$ делится на $b$ и одновременно $s(a)$ делится на $s(b)$, либо $a$ не делится на $b$ и одновременно $s(a)$ не делится на $s(b)$ ($s(n)$ обозначает сумму цифр числа $n$).
Можно ли выбрать 15 различных натуральных чисел от 1 до 100 так, чтобы любая пара выбранных числа была зеркальной?

{\source{JBMO 2023 Shortlist Albania NT5, упрощение }

\ans{Можно.} \sol{Подойдут, например, числа: $1, 3, 5, 7, 9, 11, 22, 44, 55, 66, 77, 88, 89, 92, 94, 99$}
} 

\three

\four

\ifnum\value{ifsol}=0
{\begin{wrapfigure}[5]{r}{0.2\linewidth} 
\vspace{-2,8em}
\includegraphics[width=\linewidth]{ris/snake-1.png}
\end{wrapfigure}
}
\fi
\q5. \emph{Змея} в  квадрате $n\times n$~--- это путь, состоящий из прямых отрезков между центрами соседних клеток, проходящий через центры всех $n^2$ клеток ровно по одному разу. (Две клетки считаются соседними, если они имеют общую сторону).  На рисунке показан пример змеи в квадрате размером $4\times 4$. Эта змея делает девять поворотов на $90^{\circ}$, отмеченных маленькими черными квадратами.
Может ли змея сделать более 70 поворотов на $90^{\circ}$ в квадрате $9\times 9$?

{\source{MEMO 2025}

\ans{Да, может.} \sol{Пример можно построить так, как на рисунке. Тут обойдена
каёмка ширины 2, далее надо обойти аналогичную каёмку. Всего будет 71 поворот.
\begin{wrapfigure}[7]{r}{0.14\linewidth} 
\vspace{-0em}
\includegraphics[width=\linewidth]{ris/snake-3.png}
\end{wrapfigure}
}
} 


\ifnum\value{ifsol}=0
{\begin{wrapfigure}[4]{r}{0.19\linewidth} 
\vspace{-4,5em}
\includegraphics[width=\linewidth]{ris/prisma.png}
\end{wrapfigure}
}
\fi
\six

\q7. По кругу лежат 30 мячей — красные, синие, белые, зелёные и жёлтые. Мячи всех цветов встречаются. Оказалось, что справа от красного мяча всегда лежит синий, справа от синего — всегда белый, справа от жёлтого — тоже всегда белый, справа от зелёного — жёлтый. А справа от белого может лежать красный или зелёный мяч. Известно, что всего синих мячей — 8 штук. Найдите количество зелёных мячей.
%

{\source{Ассара 2025.}

\ans{2.} \sol{Из условия следует, что возможны только такие фрагменты расположения мячей: ...КСБ(К или З)...и ...ЗЖБ(К или З)... Любой из этих двух фрагментов может следовать за любым, стыкуясь красным или зелёным мячом. Круг делится на 10 таких фрагментов. В восьми из них есть синий мяч. Значит, 8 раз встречается первый фрагмент и 2 раза второй. В первом фрагменте зелёных мячей нет, значит всего их два.}

\r Только ответ с примером: 2 балла.
}

\eight


\end{document}
