Kvant Math Problem 24
The condition on the denominators is much stronger than in the usual Egyptian fraction problem.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m42s
Source on kvant.digital
Problem
Prove that any fraction $\dfrac mn$, where $0\lt\dfrac mn\lt1$, can be represented in the form $$\dfrac mn=\dfrac1{q_1}+\dfrac1{q_2}+\dfrac1{q_3}+\ldots+\dfrac1{q_r},$$, where $0 \lt q_1 \lt q_2 \lt \ldots \lt q_r$ are integers, and each $q_k$ ($k = 2$, 3, $\ldots$, $r$) is divisible by $q_{k-1}$.
Exploration
The condition on the denominators is much stronger than in the usual Egyptian fraction problem. We need
$$q_1\mid q_2\mid q_3\mid\cdots\mid q_r.$$
A natural way to generate such denominators is to start from one denominator and repeatedly replace a unit fraction by a sum of two unit fractions whose denominators are multiples of the original one.
For example,
$$\frac1a=\frac1{a+1}+\frac1{a(a+1)}.$$
The new denominators are both divisible by $a+1$, and $a(a+1)$ is divisible by $a+1$.
Trying small examples:
$$\frac23=\frac12+\frac16.$$
Here $2\mid6$.
Also
$$\frac35=\frac12+\frac1{10}.$$
Again $2\mid10$.
These examples suggest reducing the numerator by taking the largest unit fraction not exceeding the given fraction. Let
$$q=\Bigl\lceil\frac nm\Bigr\rceil.$$
Then
$$\frac1q\le\frac mn<\frac1{q-1},$$
and
$$\frac mn-\frac1q =\frac{mq-n}{nq}.$$
Since $q=\lceil n/m\rceil$, we have
$$0\le mq-n<m.$$
Hence the new numerator $mq-n$ is strictly smaller than $m$.
This looks promising for induction on the numerator. The remaining difficulty is preserving the divisibility chain. If the remainder is represented as
$$\frac{mq-n}{nq} =\frac1{t_1}+\cdots+\frac1{t_s}, \qquad t_1\mid t_2\mid\cdots\mid t_s,$$
then multiplying all denominators by $q$ gives
$$\frac1{qt_1}+\cdots+\frac1{qt_s}.$$
Now every denominator is divisible by $q$, and
$$qt_1\mid qt_2\mid\cdots\mid qt_s.$$
Since $t_1\ge2$, we have $q<qt_1$, so the full sequence
$$q,qt_1,\ldots,qt_s$$
is strictly increasing and satisfies the required divisibility chain.
The step most likely to hide an error is the induction step, specifically the verification that the transformed denominators remain strictly increasing and satisfy the divisibility condition.
Problem Understanding
We must prove that every rational number
$$0<\frac mn<1$$
can be written as a finite sum of distinct unit fractions
$$\frac1{q_1}+\frac1{q_2}+\cdots+\frac1{q_r},$$
where the denominators are positive integers satisfying
$$q_1<q_2<\cdots<q_r$$
and
$$q_{k-1}\mid q_k \qquad (k=2,\dots,r).$$
This is a Type B problem. The task is to prove the stated representation always exists.
The core difficulty is obtaining the representation while maintaining the strong divisibility condition between consecutive denominators.
Proof Architecture
We prove the statement by induction on the numerator $m$.
The base case is $m=1$. Then $\frac mn=\frac1n$, which already has the required form.
The induction step uses the greedy choice
$$q=\Bigl\lceil\frac nm\Bigr\rceil.$$
The remainder
$$\frac mn-\frac1q =\frac{mq-n}{nq}$$
has numerator $mq-n$, which satisfies $0\le mq-n<m$.
By the induction hypothesis, the remainder has a representation with a divisibility chain of denominators.
Multiplying every denominator in that representation by $q$ preserves the divisibility chain and scales the sum by $1/q$.
Adding the initial term $1/q$ yields the desired representation of $\frac mn$.
The lemma most likely to fail under scrutiny is the claim that the new denominator sequence
$$q,qt_1,\ldots,qt_s$$
is strictly increasing and satisfies the divisibility condition.
Solution
We proceed by induction on the numerator $m$.
For $m=1$, the fraction is
$$\frac1n,$$
which already has the required form with $r=1$ and $q_1=n$.
Assume now that the statement has been proved for all positive fractions whose numerator is smaller than some integer $m\ge2$. Let
$$0<\frac mn<1.$$
Define
$$q=\Bigl\lceil\frac nm\Bigr\rceil.$$
Then
$$q-1<\frac nm\le q.$$
Multiplying by $m$ gives
$$m(q-1)<n\le mq.$$
Hence
$$0\le mq-n<m.$$
Since
$$\frac mn<1,$$
we have $m<n$, so $n\ne mq$. Therefore
$$mq-n>0.$$
Consequently,
$$0<mq-n<m.$$
Now
$$\frac mn =\frac1q+\left(\frac mn-\frac1q\right) =\frac1q+\frac{mq-n}{nq}.$$
The fraction
$$\frac{mq-n}{nq}$$
has positive numerator $mq-n$, which is strictly smaller than $m$. By the induction hypothesis, there exist integers
$$t_1<t_2<\cdots<t_s$$
such that
$$t_1\mid t_2\mid\cdots\mid t_s$$
and
$$\frac{mq-n}{nq} = \frac1{t_1}+\frac1{t_2}+\cdots+\frac1{t_s}.$$
Multiplying every denominator by $q$, we obtain
$$\frac{mq-n}{nq} = \frac1{qt_1} +\frac1{qt_2} +\cdots +\frac1{qt_s}.$$
Because
$$t_1<t_2<\cdots<t_s,$$
we have
$$qt_1<qt_2<\cdots<qt_s.$$
Also,
$$t_i\mid t_{i+1} \quad\Longrightarrow\quad qt_i\mid qt_{i+1},$$
so
$$qt_1\mid qt_2\mid\cdots\mid qt_s.$$
Since $t_1\ge2$,
$$q<qt_1.$$
Therefore
$$q<qt_1<qt_2<\cdots<qt_s.$$
Furthermore, $q$ divides every number $qt_i$, hence
$$q\mid qt_1\mid qt_2\mid\cdots\mid qt_s.$$
Combining these facts,
$$\frac mn = \frac1q +\frac1{qt_1} +\frac1{qt_2} +\cdots +\frac1{qt_s},$$
and the denominators form a strictly increasing sequence in which each term divides the next.
Thus the required representation exists for numerator $m$. The induction is complete.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is proving that the new numerator is smaller. From
$$q=\Bigl\lceil\frac nm\Bigr\rceil$$
we obtain
$$q-1<\frac nm\le q.$$
After multiplying by $m$,
$$m(q-1)<n\le mq.$$
The left inequality yields
$$mq-n<m,$$
while the right inequality yields
$$mq-n\ge0.$$
Because $m<n$, equality $n=mq$ is impossible. Hence
$$0<mq-n<m.$$
This is exactly what is needed for induction.
The second delicate point is showing that the first denominator $q$ is smaller than all the others. The induction hypothesis provides positive integers
$$t_1<t_2<\cdots<t_s.$$
Since $t_1$ is an integer and $t_1<t_2$, necessarily $t_1\ge2$. Therefore
$$qt_1\ge2q>q,$$
which gives
$$q<qt_1.$$
Without this observation, strict increase of the final denominator sequence would not be justified.
The third delicate point is preservation of divisibility. If
$$t_i\mid t_{i+1},$$
then
$$t_{i+1}=ct_i$$
for some integer $c$. Hence
$$qt_{i+1}=c(qt_i),$$
so
$$qt_i\mid qt_{i+1}.$$
The divisibility chain survives multiplication by the common factor $q$.
Alternative Approaches
A different proof can be based on repeated use of the identity
$$\frac1a=\frac1{a+1}+\frac1{a(a+1)}.$$
Starting from a suitable unit fraction and repeatedly splitting terms, one can generate arbitrarily refined representations whose denominators form a divisibility chain. The challenge is to control the resulting sum so that it equals a prescribed rational number.
The inductive argument above is preferable because each step decreases the numerator. The decrease is explicit, the process must terminate, and the divisibility condition is preserved automatically by multiplying all denominators in the inductive representation by the same factor $q$. This yields a short and completely systematic proof.