Азия-тынық мұхит математикалық олимпиадасы, 2013 жыл

$a$ мен $b$ бүтін оң сандар, ал $A$ мен $B$ төменгі шарттарды қанағаттандыратын шекті бүтін сандар жиындары болсын:
(i) $A$ мен $B$ жиындарының ортақ элементі жоқ;
(ii) егер бүтін $i$ саны $A$ немесе $B$ жиынында болса, онда ${i+a}$ саны $A$ жиынында немесе ${i-a}$ саны $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$ ч.т.д.