Азиатско-Тихоокеанская математическая олимпиада, 2013 год

Пусть $a$ и $b$ — натуральные числа. Конечные множества $A$ и $B$, состоящие из целых чисел, удовлетворяют следующим условиям:
(i) $A$ и $B$ не имеют общих элементов;
(ii) если целое число $i$ лежит в $A$ или в $B$, то либо $i+a$ лежит в $A$, либо $i-b$ лежит в $B$.
Докажите, что $a|A| = b|B|$. Здесь $|X|$ обозначает количество элементов $X$.

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

Переформулируем условие:

(1) Пусть у нас есть граф с двумя долями $A$ и $B$ с конечным количеством вершин. Пусть в доле $A$ их $p$ вершин, а в доле $B$ их $q$.

(2) Из любой вершины с числом $i$ проведена стрелка либо к вершине с числом $i+a$ из доли $A$, или к вершине с числом $i-b$ из доли $B$. И для удобства пусть на стрелке написано: $+a$ в первом случаи, и $-b$ во втором.

Заметим, что в нашем графе есть ориентированный цикл.

Доказательство: Возьмём произвольную вершину $X$, тогда пусть оно соединено стрелкой с другой вершиной и оно с другой и т.д. Тогда несколько раз подряд стрелки уходят из вершины одной доли в вершину же этой доли и в один момент оно будет соединено с вершиной другой доли и т.д. Так как у нас вершин конечно у нас эта операция однажды закончиться. ч.т.д.

(Думаю стоит упомянуть что если стрелка входит в одну вершину то эта же стрелка не может из нее выйти, ведь тогда очевидно что $a$ равен $b$ тогда аналогично рассмотриваем циклы и получаем что у нас биекция, и во множествах $A$ и $B$ одинакое количество элементов, ч.т.д.)

Так как вершины в циклах графа не совпадают, то наш граф разбивается на циклы. Рассмотрим произвольный цикл: Возьмем любую вершину $Y$ с числом $m$. Так как мы вышли из вершины с числом $m$ и вернулись обратно в неё же, значит мы несколько раз к числу $m$ прибавляли $a$ и отнимали $b$. Тогда если в этом цикле $k_1$ стрелок с надписью $+a$ и $d_1$ стрелок с надписью $-b$, тогда у нас:

$$ak_1=bd_1$$

Если проделать эту операцию для всех циклов тогда у нас выйдет:

$$a(k_1+k_2+…+k_n)=b(d_1+d_2+…+d_n)$$

Ну, так как у нас $k_1+k_2+…+k_n \geq p$ и все $k_j$ различны то их сумма равно $p$. Аналогично $d_1+d_2+…+d_n=q$

Следовательно $ap=bq$ ч.т.д.