Kvant Math Problem 298
For $m=5$ the consecutive fractions
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m30s
Source on kvant.digital
Problem
List all irreducible fractions $\dfrac pq$, where $0\lt p\lt q\le m$, in ascending order ($m$ is a given natural number). For example, for $m=5$ the sequence $$\dfrac15,\quad\dfrac14,\quad\dfrac13,\quad\dfrac25,\quad\dfrac12,\quad\dfrac35,\quad\dfrac23,\quad\dfrac34,\quad\dfrac45.$$ is obtained. Prove that for any two consecutive fractions $\dfrac pq\lt\dfrac rs$ in such a sequence, the equality $qr-ps=1$ holds.
N. B. Vasilyev
Exploration
For $m=5$ the consecutive fractions
$$\frac13<\frac25,\qquad \frac25<\frac12,\qquad \frac23<\frac34$$
satisfy
$$3\cdot2-1\cdot5=1,\qquad 5\cdot1-2\cdot2=1,\qquad 3\cdot3-2\cdot4=1.$$
The statement resembles the classical property of neighboring fractions in a Farey sequence.
Suppose $\frac pq<\frac rs$ are consecutive fractions. Then
$$qr-ps>0.$$
Since $p,q,r,s$ are integers, $qr-ps$ is a positive integer. To prove it equals $1$, it suffices to rule out the possibility $qr-ps\ge2$.
If $qr-ps\ge2$, one should try to construct another reduced fraction between $\frac pq$ and $\frac rs$ whose denominator does not exceed $m$. The obvious candidate is the mediant
$$\frac{p+r}{q+s},$$
which always lies strictly between the two fractions. The difficulty is that its denominator may exceed $m$.
The crucial point is therefore: from the assumption $qr-ps\ge2$, produce some fraction between $\frac pq$ and $\frac rs$ with denominator at most $m$.
Assume $q\ge s$. Consider the integers
$$p+kr,\qquad q+ks.$$
For
$$k=\left\lfloor \frac{m-q}{s}\right\rfloor$$
the denominator $q+ks$ does not exceed $m$, while $q+(k+1)s>m$. Put
$$a=p+kr,\qquad b=q+ks.$$
Then
$$\frac pq<\frac ab<\frac rs.$$
Indeed,
$$aq-bp=k(qr-ps)>0,$$
and
$$rb-sa=qr-ps>0.$$
Now $b+s>m$. Hence
$$b>m-s\ge q-s.$$
Since $b=q+ks$, this gives $(k+1)s>m-q$, exactly as required. The remaining issue is to show that $\frac ab$ can be reduced to a fraction whose denominator is still at most $m$. Any reduction only decreases the denominator. Thus a reduced fraction between $\frac pq$ and $\frac rs$ would exist, contradicting consecutiveness. This yields $qr-ps=1$.
The step most likely to hide an error is proving that $\frac ab$ lies strictly between the given fractions and that its denominator indeed does not exceed $m$.
Problem Understanding
We are given all reduced fractions $\frac pq$ satisfying
$$0<p<q\le m,$$
arranged in increasing order. We must prove that whenever two fractions
$$\frac pq<\frac rs$$
appear consecutively in this ordered list, they satisfy
$$qr-ps=1.$$
This is a Type B problem, a pure proof.
The core difficulty is to show that if $qr-ps$ were at least $2$, then another reduced fraction with denominator at most $m$ would necessarily lie between the two given fractions, contradicting their consecutiveness.
Proof Architecture
The first lemma states that if integers $a,b$ satisfy
$$aq-bp>0,$$
then $\frac ab>\frac pq$, and if
$$rb-sa>0,$$
then $\frac ab<\frac rs$; this is just cross multiplication with positive denominators.
The second lemma states that, assuming $q\ge s$, if
$$k=\left\lfloor \frac{m-q}{s}\right\rfloor,$$
and
$$a=p+kr,\qquad b=q+ks,$$
then $b\le m$; this follows directly from the definition of the floor function.
The third lemma states that if $qr-ps\ge2$, then the fraction $\frac ab$ constructed above lies strictly between $\frac pq$ and $\frac rs$; the required inequalities reduce to positive multiples of $qr-ps$.
The final step shows that reducing $\frac ab$ to lowest terms produces a reduced fraction between $\frac pq$ and $\frac rs$ whose denominator is still at most $m$, contradicting the assumption that the two fractions are consecutive.
The hardest part is the construction of the intermediate fraction with denominator at most $m$.
Solution
Let
$$\frac pq<\frac rs$$
be two consecutive fractions in the ordered list of all irreducible fractions satisfying
$$0<p<q\le m.$$
Since
$$\frac pq<\frac rs,$$
we have
$$qr-ps>0.$$
The quantity $qr-ps$ is an integer, so it is enough to prove that the possibility
$$qr-ps\ge2$$
is impossible.
Assume, for contradiction, that
$$qr-ps\ge2.$$
Interchanging the two fractions if necessary, we may suppose that
$$q\ge s.$$
Define
$$k=\left\lfloor\frac{m-q}{s}\right\rfloor,$$
and set
$$a=p+kr,\qquad b=q+ks.$$
From the definition of $k$,
$$q+ks\le m,$$
hence
$$b\le m.$$
Consider the fraction $\frac ab$.
First,
$$aq-bp=(p+kr)q-(q+ks)p =k(qr-ps).$$
Since $k\ge0$ and $qr-ps>0$, we obtain
$$aq-bp>0.$$
Therefore
$$\frac pq<\frac ab.$$
Next,
$$rb-sa=r(q+ks)-s(p+kr) =qr-ps.$$
Since $qr-ps>0$,
$$rb-sa>0,$$
and consequently
$$\frac ab<\frac rs.$$
Thus
$$\frac pq<\frac ab<\frac rs.$$
Let
$$d=\gcd(a,b).$$
Reducing $\frac ab$ to lowest terms gives
$$\frac{a/d}{b/d}.$$
Its denominator is $b/d\le b\le m$. Since reduction does not change the value of the fraction,
$$\frac pq<\frac{a/d}{b/d}<\frac rs.$$
Hence we have found an irreducible fraction with denominator at most $m$ lying strictly between $\frac pq$ and $\frac rs$.
This contradicts the assumption that $\frac pq$ and $\frac rs$ are consecutive fractions in the ordered list.
The contradiction shows that the assumption $qr-ps\ge2$ is false. Since $qr-ps$ is a positive integer, the only remaining possibility is
$$qr-ps=1.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the inequality
$$\frac pq<\frac ab.$$
Substituting $a=p+kr$ and $b=q+ks$ gives
$$aq-bp=k(qr-ps).$$
A careless computation may incorrectly produce $(k+1)(qr-ps)$. The exact expansion is
$$(p+kr)q-(q+ks)p = pq+kqr-pq-kps = k(qr-ps),$$
which is positive because $k\ge0$ and $qr-ps>0$.
The second delicate point is the proof that $b\le m$. From
$$k=\left\lfloor\frac{m-q}{s}\right\rfloor$$
we obtain
$$k\le\frac{m-q}{s}.$$
Multiplying by $s$ and adding $q$ yields
$$q+ks\le m.$$
This is exactly the denominator bound required by the problem.
The third delicate point is the passage to lowest terms. If
$$\frac ab=\frac{a/d}{b/d},$$
the denominator becomes smaller, not larger. Hence
$$\frac{b}{d}\le b\le m.$$
The reduced fraction remains between $\frac pq$ and $\frac rs$ because it has the same numerical value as $\frac ab$.
Alternative Approaches
A classical Farey-sequence argument proceeds by contradiction in a different way. Assume consecutive fractions satisfy $qr-ps\ge2$. Then one chooses an integer denominator $t\le m$ maximizing the value of a fraction between $\frac pq$ and $\frac rs$ with denominator $t$, and studies the corresponding numerator. Elementary inequalities then produce another fraction between the two with a larger denominator, contradicting maximality. This eventually forces $qr-ps=1$.
Another approach uses the theory of mediants. Neighboring fractions in a Farey sequence are characterized by the determinant condition $qr-ps=1$. If $qr-ps>1$, repeated mediant constructions generate a reduced fraction strictly between them. A suitable choice of mediant in the Stern-Brocot tree yields a denominator not exceeding $m$, contradicting consecutiveness. The proof given above is preferable because it avoids any external theory and derives the needed intermediate fraction directly from elementary arithmetic.