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

Задача №1. Дано натуральное число

$n$ . Пусть

$p, q > n$ — нечетные простые числа. Докажите, что все натуральные числа от

$1$ до

$n$ можно покрасить в два цвета так, чтобы для любых различных одноцветных чисел

$x, y$ число

$(xy - 1)$ не делилось ни на

$p$ , ни на

$q$ . ( Зиманов Т. )
комментарий/решение(1)

Задача №2. Дана неравнобокая трапеция

$ABCD$ (

$AB \parallel CD$ ). Некоторая окружность проходит через точки

$A$ и

$B$ , и пересекает боковые стороны

$AD$ и

$BC$ в точках

$E$ и

$F$ , соответственно. Отрезки

$AF$ и

$BE$ пересекаются в точке

$G$ , а описанные окружности треугольников

$ADG$ и

$BCG$ пересекаются во второй раз в точке

$H$ . Докажите, что если

$DG=CG$ , то

$H$ является точкой пересечения высот треугольника

$ABG$ . ( М. Кунгожин )
комментарий/решение(3)

Задача №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}.$
комментарий/решение

результаты