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 }$.

567-1

Решение

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

Первое решение. Из условия следует, что каждое из чисел $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$: угловой коэффициент диагонали параллелограмма заключён между угловыми коэффициентами его сторон*).

M567-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$ (глядя на наш маленький рисунок, в этом можно усомниться).

M567-3

Задача М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).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *