Задача из журнала «Квант» (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).

Условие

Натуральные числа [latex]x[/latex] и [latex]y[/latex] таковы, что сумма дробей [latex]\frac { { x }^{ 2 }-1 }{ y\quad+\quad 1 } +\frac { { y }^{ 2 }-1 }{ x\quad+\quad 1 }[/latex] — целое число. Докажите, что каждая из дробей — целое число.

Решение:

Пусть [latex]u[/latex] — первая, [latex]v[/latex] — вторая из этих дробей. Их сумма и произведение — целые числа, поэтому [latex]u[/latex] и [latex]v[/latex] корни квадратного уравнения с целыми коэффициентами, скажем, [latex]{ z }^{ 2 } + m \cdot z + n = 0[/latex]. Так как [latex]u[/latex] и [latex]v[/latex] — рациональные корни, то дискриминант [latex]{ m }^{ 2 }-4\cdot n[/latex] этого уравнения — рациональное число и, более того, целое, причем той же четности, что и [latex]m[/latex].
Формулы Виета
Но тогда [latex]u[/latex] и [latex]v[/latex] — тоже целые, ведь [latex]u[/latex], [latex]v[/latex] = [latex]\frac { -m+-\sqrt { { m }^{ 2 }-4\cdot n } }{ 2 }[/latex], а в числителе под корнем стоит четное число. Существует также много решений этой задачи, связанных с рассмотрением общих делителей чисел [latex]x + 1[/latex] и [latex]y + 1[/latex].

А.Перлин

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

Условие

Две окружности пересекаются в точках \(P\) и \(Q\). Третья окружность с центром в точке \(P\) пересекает первую в точках \(A\), \(B\), а вторую в точках — \(C\) и \(D\) (см. рисунок). Докажите, что углы \(AQD\) и \(BQC\) равны.

Решение

Треугольники \(APB\) и \(DPC\) равнобедренные. Обозначим углы при их основаниях \(\angle ABP =\angle BAP = \alpha \), \(\angle DCP =\angle CDP = \beta \). Четырехугольники \(AQBP\) и \(DQCP\) вписанные, отсюда \(\angle AQP =\angle ABP = \alpha \) и \(\angle DQP =\angle DCP = \beta \). Получаем: \(\angle AQD = \angle AQP + \angle DQP = \alpha + \beta \). Далее, \(\angle BQP =\angle BAP = \alpha \), также \(\angle CQP = \beta \) и \(\angle BQC = \angle BQP + \angle CQP = \alpha + \beta \). Значит, \(\angle AQD = \angle BQC\).

Условие

[latex]\forall n \in N[/latex] обозначим через [latex]f(n)[/latex] число способов представления числа [latex]n[/latex] в виде суммы целых неотрицательных степеней числа [latex]2[/latex]. Преставления, отличающиеся лишь порядком слагаемых, считаются одинаковыми. Например, [latex]f(4) = 4[/latex], так как число [latex]4[/latex] может быть представлено следующими четырьмя способами:
[latex]4 = 4[/latex];
[latex]4 = 2 + 2[/latex];
[latex]4 = 2 + 1 + 1[/latex];
[latex]4 = 1 + 1 + 1 + 1[/latex].
Докажите, что [latex]\forall n \in N, n \geq 3: 2^{n^2/4} < f(2^n) < 2^{n^2/2}[/latex].

Решение

Если [latex]n = 2k + 1[/latex] — любое нечетное число, большее [latex]1[/latex], то каждое его представление в требуемом по условию задачи виде содержит [latex]1[/latex] в качестве слагаемого. Убрав эту единицу, мы получим представление числа [latex]2k[/latex]. Очевидно и обратное. Следовательно, [latex]f(2k + 1) = f(2k)[/latex]. [latex](*)[/latex]

Если [latex]n = 2k[/latex] — любое четное число, то каждое его представление в требуемом виде принадлежит к одному из двух типов: либо оно содержит слагаемое [latex]1[/latex], либо не
содержит таких слагаемых. В первом случае, убрав одно слагаемое [latex]1[/latex], мы получим представление числа [latex]2k — 1[/latex]. Как и выше, легко заметить, что есть взаимно однозначное соответствие между всеми представлениями числа [latex]2k — 1[/latex] и представлениями числа [latex]2k[/latex] первого типа. Во втором случае мы можем разделить все слагаемые
на [latex]2[/latex] и получить представление числа [latex]k[/latex]. Это соответствие также взаимно однозначно. Итак, [latex]f(2k) = f(2k — 1) + f(k)[/latex]. [latex](**)[/latex]

Обе полученные формулы выполнены для всех натуральных [latex]k > 1[/latex]. Очевидно, что [latex]f(1) = 1[/latex]. Пусть по определению [latex]f(0) = 1[/latex], тогда формула [latex](*)[/latex] выполнена и при [latex]k = 0[/latex]. Заметим еще, что из [latex](*)[/latex] и [latex](**)[/latex] следует, что [latex]f(n)[/latex] не убывает.

Согласно [latex](*)[/latex], число [latex]f(2k — 1)[/latex] в [latex](**)[/latex] можно заменить на
[latex]f(2k — 2)[/latex], откуда [latex]f(2k) — f(2k — 2) = f(k)[/latex] [latex]\forall k \geq 1[/latex]. Суммируя эти равенства от [latex]1[/latex] до [latex]n[/latex], получаем, что [latex]f(2n) = \sum_{i=0}^n f(i)[/latex]. [latex](***)[/latex]
В правой части [latex](***)[/latex] каждое слагаемое не больше последнего, а так как [latex]2 = f(0) + f(1) \leq f(n)[/latex] [latex]\forall n \geq 2[/latex], то [latex]f(2n) = 2 + \sum_{i=2}^n f(i) \leq 2 + (n — 1)f(n) \leq f(n) + (n — 1)f(n) \leq nf(n)[/latex] [latex]\forall n \geq 2[/latex]. Следовательно, [latex]f(2^n) \leq 2^{n-1}f(2^{n-1}) \leq 2^{n-1}2^{n-2}f(2^{n-2}) \leq \ldots \leq 2^{(n-1) + (n-2) + \ldots + 2 + 1}f(2) = 2^{\frac{n(n-1)}{2} + 1}[/latex].
И так как [latex]\frac{n(n-1)}{2} + 1 < \frac{n^2}{2}[/latex], т.е. [latex]2^{\frac{n(n-1)}{2} + 1} < 2^{\frac{n^2}{2}}[/latex] [latex]\forall n \geq 3[/latex], верхняя оценка для [latex]f(2n)[/latex] получена.

Чтобы получить нижнюю оценку, докажем сначала, что [latex]f(b + 1) — f(b) \geq f(a + 1) — f(a)[/latex] [latex](4)[/latex], если [latex]0 \leq a \leq b[/latex] — целые числа одинаковой четности. Действительно, если [latex]a[/latex] и [latex]b[/latex] четны, то из [latex](*)[/latex] следует,что каждая часть неравенства [latex](4)[/latex] обращается в нуль, если они оба нечетны, то из [latex](**)[/latex] следует, что [latex]f(b + 1) — f(b) = f(\frac{b+1}{2})[/latex], [latex]f(a + 1) — f(a) = f(\frac{a+1}{2})[/latex], при чем, как было показано ранее, [latex]f[/latex] не убывает.

Возьмем произвольные [latex]r[/latex] и [latex]k[/latex], [latex]r \geq k[/latex], [latex]r[/latex] — четное. Подставим в неравенство [latex](4)[/latex] [latex]a = r + j, b = r — j, j = 0, 1, \ldots, k — 1[/latex]. Получаем следующий набор неравенств:
[latex]j = 0 : \underline{f(r + 1)} — f(r) \geq f(r + 1) — \underline{f(r)}[/latex]
[latex]j = 1 : \underline{f(r + 2)} — \underline{f(r + 1)} \geq \underline{f(r)} — \underline{f(r — 1)}[/latex]
[latex]j = 2 : \underline{f(r + 3)} — \underline{f(r + 2)} \geq \underline{f(r — 1)} — \underline{f(r — 2)}[/latex]
(…)
[latex]j = k — 2 : \underline{f(r + k — 1)} — \underline{f(r + k — 2)} \geq \underline{f(r + k — 3)} — \underline{f(r + k — 2)}[/latex]
[latex]j = k — 1 : f(r + k) — \underline{f(r + k — 1)} \geq \underline{f(r + k — 2)} — f(r + k — 1)[/latex]
Просуммировав левые и правые части неравенств соответственно, легко увидеть, что все промежуточные слагаемые сокращаются, и остается следующее: [latex]f(r + k) — f(r) \geq f(r + 1) — f(r — k + 1)[/latex], а в силу того, что [latex]r[/latex] — четное и [latex]f(r + 1) = f(r)[/latex], получим [latex]f(r + k) + f(r — k + 1) \geq 2f(r)[/latex]. Так как [latex]r \geq k[/latex], просуммируем уже такие неравенства по [latex]k = 1, 2, \ldots, r[/latex], и получим [latex]\sum_{i=1}^{2r}f(i) \geq 2rf(r)[/latex], или, что тоже самое [latex]\sum_{i=0}^{2r}f(i) — f(0) \geq 2rf(r)[/latex]. В силу [latex](***)[/latex] [latex]\sum_{i=0}^{2r}f(i) = f(4r)[/latex], а [latex]f(0) = 1[/latex]. Получаем следующее неравенство: [latex]f(4r) \geq 2rf(r) + 1 > 2rf(r)[/latex]. Возьмем [latex]r = 2^{m — 2}[/latex], тогда [latex]f(2^m) > 2^{m — 1}f(2^{m — 2})[/latex]. [latex](5)[/latex]
(Очевидно, что [latex]\forall m \in N, m > 2: 2^{m — 2}[/latex] — четно. Также, непосредственно подстановкой легко убедиться, что неравенство [latex](5)[/latex] справедливо и при [latex]m = 2: f(4) = 4 > 2 = f(2)f(1)[/latex].)

Наконец. пусть [latex]n \in N, n > 1[/latex]. Если [latex]l[/latex] — положительное целое такое, что [latex]2l \leq n[/latex], то применяя неравенство [latex](5)[/latex] к [latex]m = n, n — 1, \ldots, n -2l + 2[/latex], получаем:
[latex]f(2^n) > 2^{n — 1}f(2^{n — 2}) > 2^{n — 1}2^{n — 3}f(2^{n — 4}) > \ldots[/latex] [latex]> 2^{(n — 1) + (n — 3) + \ldots + (n — 2l + 1)}f(2^{n — 2l}) = 2^{l(n — 2l)}f(2^{n — 2l})[/latex] (слагаемых в показателе степени — [latex]l[/latex] штук, а [latex]1 + 3 + \ldots + (2l — 1) = l^2[/latex], тогда [latex](n — 1) + (n — 3) + \ldots + (n — 2l + 1) = nl — l^2 = l(n — l)[/latex]).

Теперь, пусть [latex]n[/latex] — четно, [latex]l = \frac{n}{2}[/latex]. Получаем, [latex]f(2^n) > 2^{\frac{n}{2}(n — \frac{n}{2})}f(2^0) = 2^{\frac{n^2}{4}}f(1) = 2^{\frac{n^2}{4}}[/latex].
Если же [latex]n[/latex] — нечетно, то положим [latex]l = \frac{n — 1}{2}[/latex]. Тогда, [latex]f(2^n) > 2^{\frac{n — 1}{2}(n — \frac{n — 1}{2})}f(2^1) = 2^{\frac{(n — 1)(n + 1)}{4}}f(2) = 2^{\frac{n^2 — 1}{4} + 1} = 2^{\frac{n^2 + 3}{4}} > 2^{\frac{n^2}{4}}[/latex].
Таким образом, нужный результат доказан [latex]\forall n > 1[/latex]. Непосредственно проверяется, что и для [latex]n = 1[/latex] соответствующее неравенство справедливо.

Тогда получаем, что [latex]\forall n \in N, n \geq 3: 2^{n^2/4} < f(2^n) < 2^{n^2/2}[/latex], что и требовалось доказать.