Натуральные числа $p$ и $q$ взаимно просты. Отрезок $[0;1]$ разбит на $p+q$ одинаковых отрезков. Докажите, что в каждом из этих отрезков, кроме двух крайних, лежит ровно одно из $p+q-2$ чисел
$$
\dfrac1p,\quad\dfrac2p,\quad\ldots,\quad\dfrac{p-1}p,\quad
\dfrac1q,\quad\dfrac2q,\quad\ldots,\quad\dfrac{q-1}q.
$$
Первое решение. Из условия следует, что каждое из чисел $p$ и $q$ взаимно просто с числом $n=p+q$, поэтому никакие две из точек $\dfrac ip$, $\dfrac jq$, $\dfrac kn$ (отличные от 0 и 1) не совпадают. Поскольку $\dfrac1p\gt\dfrac1n$ и $\dfrac1q\gt\dfrac1n$, любые две из точек $\dfrac ip$ лежат в разных отрезках $\left[\dfrac kn;\dfrac{k+1}n\right]$ и любые две из точек $\dfrac jq$ — тоже. Нужно лишь доказать, что какие-то две точки $\dfrac ip$ и $\dfrac jq$ не могут попасть в один и тот же отрезок $\left[\dfrac kn;\dfrac{k+1}n\right]$ ($k=1$, 2, $\ldots$, $n-2$). Но это сразу следует из того, что дробь $\dfrac kn=\dfrac{i+j}{p+q}$ лежит между $\dfrac ip$ и $\dfrac jq$ (см., например, рисунок 2: угловой коэффициент диагонали параллелограмма заключён между угловыми коэффициентами его сторон).
Рис. 2
Второе решение. Нарисуем на клетчатой бумаге прямоугольник размерами $p\times q$ клеток и проведём в нём диагональ $OE$ (рис. 3) — она будет играть роль отрезка $[0;1]$ нашей задачи. Линии одного направления (синие) делят её на $p$ равных частей, другого (красные) — на $q$ равных частей. Проведём через вершины клеток ещё ряд параллельных прямых — под углом $45^\circ$ к линиям сетки (на рисунке это — чёрные прямые $x+y=k$, где $k=1$, 2, $\ldots$, $p+q-1$). Они делят $[OE]$ на $n=p+q$ одинаковых отрезков. Утверждение задачи теперь становится почти очевидным. В самом деле, на $[OE]$ между любыми двумя сине-красными точками обязательно лежит чёрная точка: ведь, пересекая какую-то клетку, $[OE]$ обязательно пересекает и её чёрную диагональ. (Можно вместо этого сказать и так: между любыми точками пересечения $[OE]$ с соседними чёрными прямыми лежит точка пересечения с синей или красной линией.)
Рис. 3
В этом решении взаимная простота чисел $p$ и $q$ гарантирует, что $OE$ не проходит через узлы сетки, отличные от $O$ и $E$ (глядя на наш маленький рисунок, в этом можно усомниться).
Задача М567 допускает замечательное обобщение.
Пусть $\alpha$ и $\beta$ — любые положительные числа, связанные соотношением $\dfrac1\alpha+\dfrac1\beta=1$.
Отметим на числовой оси всевозможные числа вида $i\alpha$ и $j\beta$($i\in\mathbb{Z}$, $j\in\mathbb{Z}$). Тогда каждый отрезок$[k;k+1]$ ($k\in\mathbb{Z}$), ни в один из концов которого не попало отмеченное число, содержит ровно одно из отмеченных чисел $i\alpha$, $j\beta$.
Наша задача эквивалентна этому факту при рациональных $\alpha$ и $\beta$: нужно взять $\alpha=\dfrac np$, $\beta=\dfrac nq$ (роль отрезка $[0;1]$ будет играть теперь отрезок $[0;n]$). Этот же факт (для иррациональных $\alpha$ и $\beta$) упоминался недавно в решении задания М538 («Квант», 1979, № 11), очень похожем на наше второе решение М567.
