Азиатско-Тихоокеанская математическая олимпиада, 2013 год
Комментарий/решение:
Переформулируем условие:
(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$ ч.т.д.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.