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

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

Комментарий/решение

На это все еще модно?

Вполне фундаментально решается графами.

Представим числа как вершины графа.

$$p | xy-1$$

$$q | xy-1$$

Если одно утверждение верно для $x$ & $y$ то они образуют ребро (примечаем что оба утверждения не могут быть верными как $0<xy-1<pq$), иначе нет ребра. Так еще покрасим в красный или синий если $xy-1$ делится на $p$ или $q$.

Заметим, что у любой вершины может быть не больше 2-ух ребер: для числа $x$ может быть не больше одного числа $y$ что $p | xy-1$. Допустим что нашлось число $z$ что $p | xz-1$. Тогда $p | x(y-z)$, что невозможно так как $0 < x, |y-z| < p$. Аналогично для $q$. Для каждой вершины есть не больше одного красного и синего ребра.

Ключевая идея которую можно заметить:

Граф состоит из одиночных вершин, колес и сплинов.

Сплин - дерево (связные графы без циклов) в котором есть лишь две конечные вершины (имеют только одно ребро) такие что переходя с одной конечной вершины до другой можно пройти через все остальные вершины ровно 1 раз. Одиночное ребро можно считать сплином с длиной 1.

Колесо - связный цикличный граф где у каждой вершины 2 ребра.

Чтобы доказать разобьем подграфы на цикличные и не-цикличные/деревья.

Разберем любой цикл и заметим что во всех его вершинах 2 ребра. Тогда вершины этого цикла не связаны с никакой вершиной вне этого цикла - это есть колесо.

Разберем подграф без цикл - дерево. Так как это дерево можно найти вершину лишь с одним ребром А. Переходим с А по ребрам в другие вершины, и заметим что любая вершина ведет либо лишь в одну другую вершину в которой не были, либо в никуда. В любом конечном дереве должен быть конец - другая вершина Б с одним ребром как остальные имеют 2.

Заметим что в любом колесе четное количество вершин и ребер - что исходит с того что у каждой вершины 1 синее и 1 красное ребро. Можно поочередно красить вершины в белый и черный. В любом сплине берем один конец и поочередно красить в белый и черный. Одиночные вершины красим как угодно. В конце получим что вершины одного цвета не имеют общих ребер, такая раскраска удовлетворяет требуемое.