XIX математическая олимпиада «Шелковый путь», 2024 год

Задача №1. Дано натуральное число $n$. Пусть $p, q > n$ — нечетные простые числа. Докажите, что все натуральные числа от $1$ до $n$ можно покрасить в два цвета так, чтобы для любых различных одноцветных чисел $x, y$ число $(xy - 1)$ не делилось ни на $p$, ни на $q$. ( Зиманов Т. )
комментарий/решение

Задача №2. Дана неравнобокая трапеция $ABCD$ ($AB \parallel CD$). Некоторая окружность проходит через точки $A$ и $B$, и пересекает боковые стороны $AD$ и $BC$ в точках $E$ и $F$, соответственно. Отрезки $AF$ и $BE$ пересекаются в точке $G$, а описанные окружности треугольников $ADG$ и $BCG$ пересекаются во второй раз в точке $H$. Докажите, что если $DG=CG$, то $H$ является точкой пересечения высот треугольника $ABG$. ( М. Кунгожин )
комментарий/решение(2)

Задача №3. Пусть $n>1$ — целое число. В гостинице $n$ номеров, занумерованных числами $1,2,\dots,n$; в $i$-м номере $i$ комнат, при всех $i=1,2,\dots,n$. Каждую неделю в гостиницу заезжает очередная группа из $n$ семей; каждая семья заранее заявляет натуральное число — минимальное количество комнат в номере, которое ей необходимо. Перед каждым заездом, когда предыдущая группа выехала, портье подсчитывает количество $A$ способов выдать каждой семье по отдельному номеру так, чтобы все их требования были выполнены. Затем он записывает число $A$ в свою записную книжку. Докажите, что в записной книжке у портье есть не более $2^{n-1}$ различных ненулевых чисел. ( И. Богданов )
комментарий/решение

Задача №4. Пусть $\{a_{n}\}_{n \ge 1}$ — строго возрастающая последовательность натуральных чисел. Известно, что для любого $n$, $a_{n}$ нельзя представить в виде $c_{1} a_{1} + \ldots + c_{n-1} a_{n-1},$ где $c_{i} \in\{0,1\}$. Для натурального числа $m$, через $f(m)$ обозначим количество элементов последовательности $\{a_{n}\}_{n \ge 1}$, не превосходящих $m$. Для всех натуральных $m$ и $k$ докажите, что $$f(m) \leq a_{k} + \frac{m}{k + 1}.$$
комментарий/решение

результаты