M567. О разбиении единичного отрезка на $p+q$ равных отрезков

Задача из журнала «Квант» (1979, №6)

Условие

Натуральные числа $p$ и $q$ взаимно просты. Отрезок $\left[ 0;1 \right]$ разбит на $p+q$ одинаковых отрезков (рис. $1$). Докажите, что в каждом из этих отрезков, кроме двух крайних, лежит ровно одно из $p+q-2$ чисел $\frac { 1 }{ p } , \frac { 2 }{ p }, \dots \frac { p-1 }{ p }, \frac { 1 }{ q }, \frac { 2 }{ q }, \dots \frac { q-1 }{ q }$.

Решение

Приведём два решения.

Первое решение. Из условия следует, что каждое из чисел $p$ и $q$ взаимно просто с числом $n=p+q$, поэтому никакие две из точек $\frac { i }{ p } ,\frac { j }{ q } ,\frac { k }{ n }$ (отличные от $0$ и $1$) не совпадают. Поскольку $\frac { 1 }{ p } >\frac { 1 }{ n }$ и $\frac { 1 }{ q } >\frac { 1 }{ n }$, любые две из точек $\frac { i }{ p }$ лежат в разных отрезках $\left[ \frac { k }{ n } ;\frac { k+1 }{ n } \right]$ и любые две из точек $\frac { j }{ q }$ — тоже. Нужно лишь доказать, что какие-то две точки $\frac { i }{ p }$ и $\frac { j }{ q }$ не могут попасть в один и тот же отрезок $\left[ \frac { k }{ n } ;\frac { k+1 }{ n } \right]$ $\left( k=1,2,\dots,n-2 \right)$. Но это сразу следует из того, что дробь $\frac { k }{ n } =\frac { i+j }{ p+q }$ лежит между $\frac { i }{ p }$ и $\frac { j }{ q }$ (см., например, рисунок $2$: угловой коэффициент диагонали параллелограмма заключён между угловыми коэффициентами его сторон*).

Второе решение. Нарисуем на клетчатой бумаге прямоугольник размерами $p\times q$ клеток и проведём в нём диагональ $OE$ (рис. $3$) — она и будет играть роль отрезка $\left[ 0;1 \right]$ нашей задачи. Линии одного направления (синие) делят её на $p$ равных частей, другого (красные) — на $q$ равных частей. Проведём через вершины клеток ещё ряд параллельных прямых — под углом $45^{\circ}$ к линиям сетки (на рисунке это — чёрные прямые $x+y=k$, где $k=1,2,\dots,p+q-1.$ Они делят $\left[ OE \right]$ на $n=p+q$ одинаковых отрезков. Утверждение задачи теперь становятся почти очевидным. В самом деле, на $\left[ OE \right]$ между любыми двумя сине-красными точками обязательно лежит чёрная точка: ведь, пересекая какую-то клетку, $\left[ OE \right]$ обязательно пересекает и её чёрную диагональ. (Можно вместо этого сказать и так: между любыми двумя точками пересечения $\left[ OE \right]$ с соседними чёрными прямыми лежит точка пересечения с синей или красной линией.)

В этом решении взаимная простота чисел $p$ и $q$ гарантирует, что $\left[ OE \right]$ не проходит через узлы сетки, отличные от $0$ и $E$ (глядя на наш маленький рисунок, в этом можно усомниться).

Задача М567 допускает замечательное обобщение. Пусть $\alpha$ и $\beta$ — любые положительные числа, связанные соотношением $\frac { 1 }{ \alpha } +\frac { 1 }{ \beta } =1$. Отметим на числовой оси всевозможные числа вида $i\alpha$ и $j\beta \left( i\in Z,j\in Z \right)$. Тогда каждый отрезок $\left[ k;k+1 \right]$ оси $\left( k\in Z \right)$, ни в один из концов которого не попало отмеченное число, содержит ровно одно из отмеченных чисел $i\alpha$, $j\beta$. Наша задача эквивалента этому факту при рациональных $\alpha$ и $\beta$: нужно взять $\alpha =\frac { n }{ p } , \beta =\frac { n }{ q }$ (роль отрезка $\left[ 0;1 \right]$ будет играть теперь отрезок $\left[ 0;n \right])$. Этот же факт (для иррациональных $\alpha$ и $\beta$) упоминался недавно в решении задачи М538 («Квант», 1979, № $11$), очень похожем на наше второе решение М567.

Н.Васильев

---

(*) Тот факт, что «медианта» двух дробей $\frac { i }{ p }$ и $\frac { j }{ p }$ лежит между ними, использовался в статье «Близкие дроби» («Квант», 1975, №8).