uniolympiads Ελληνικά

IMC 1997, Day 1, Problem 4

Let α\alpha be a real number, 1<α<21 < \alpha < 2.

a) Show that α\alpha has a unique representation as an infinite product

α=(1+1n1)(1+1n2)…\alpha = \left(1 + \frac{1}{n_1}\right)\left(1 + \frac{1}{n_2}\right)\dots

where each nin_i is a positive integer satisfying

ni2≤ni+1.n_i^2 \le n_{i+1}.

b) Show that α\alpha is rational if and only if its infinite product has the following property:

For some mm and all k≥mk \ge m,

nk+1=nk2.n_{k+1} = n_k^2.
Original from the official PDFLet α be a real number, 1 < α < 2. a) Show that α has a unique representation as an infinite product α = 1+ 1 n 1 1+ 1 ... n 2 where each n i is a positive integer satisfying n 2 i ≤ n i+1 . b) Show that α is rational if and only if its infinite product has the following property: For some m and all k ≥ m, n k+1 = n 2 k .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. a) We construct inductively the sequence {ni}\{n_i\} and the ratios

θk=α∏1k(1+1ni)\theta_k = \frac{\alpha}{\prod_1^k (1 + \frac{1}{n_i})}
so that
θk>1 for all k.\theta_k > 1 \text{ for all } k.
Choose nkn_k to be the least nn for which
1+1n<θk−11 + \frac1n < \theta_{k-1}
(θ0=α\theta_0 = \alpha) so that for each kk,
1+1nk<θk−1≤1+1nk−1.(1)1 + \frac{1}{n_k} < \theta_{k-1} \le 1 + \frac{1}{n_k - 1}. \tag{1}
Since
θk−1≤1+1nk−1\theta_{k-1} \le 1 + \frac{1}{n_k - 1}
we have
1+1nk+1<θk=θk−11+1nk≤1+1nk−11+1nk=1+1nk2−1.1 + \frac{1}{n_{k+1}} < \theta_k = \frac{\theta_{k-1}}{1 + \frac{1}{n_k}} \le \frac{1 + \frac{1}{n_k - 1}}{1 + \frac{1}{n_k}} = 1 + \frac{1}{n_k^2 - 1}.
Hence, for each kk, nk+1≥nk2n_{k+1} \ge n_k^2.

Since n1≥2n_1 \ge 2, nk→∞n_k \to \infty so that θk→1\theta_k \to 1. Hence

α=∏1∞(1+1nk).\alpha = \prod_1^\infty \left(1 + \frac{1}{n_k}\right).

The uniquness of the infinite product will follow from the fact that on every step nkn_k has to be determine by (1).

Indeed, if for some kk we have

1+1nk≥θk−11 + \frac{1}{n_k} \ge \theta_{k-1}
then θk≤1\theta_k \le 1, θk+1<1\theta_{k+1} < 1 and hence {θk}\{\theta_k\} does not converge to 1.

Now observe that for M>1M > 1,

(1+1M)(1+1M2)(1+1M4)⋯=1+1M+1M2+1M3+⋯=1+1M−1.(2)\left(1 + \frac1M\right)\left(1 + \frac{1}{M^2}\right)\left(1 + \frac{1}{M^4}\right)\cdots = 1 + \frac1M + \frac{1}{M^2} + \frac{1}{M^3} + \cdots = 1 + \frac{1}{M-1}. \tag{2}
Assume that for some kk we have
1+1nk−1<θk−1.1 + \frac{1}{n_k - 1} < \theta_{k-1}.
Then we get
α(1+1n1)(1+1n2)…=θk−1(1+1nk)(1+1nk+1)…≥θk−1(1+1nk)(1+1nk2)…=θk−11+1nk−1>1\begin{aligned} \frac{\alpha}{(1 + \frac{1}{n_1})(1 + \frac{1}{n_2})\ldots} &= \frac{\theta_{k-1}}{(1 + \frac{1}{n_k})(1 + \frac{1}{n_{k+1}})\ldots} \\ &\ge \frac{\theta_{k-1}}{(1 + \frac{1}{n_k})(1 + \frac{1}{n_k^2})\ldots} = \frac{\theta_{k-1}}{1 + \frac{1}{n_k - 1}} > 1 \end{aligned}
– a contradiction.

b) From (2) α\alpha is rational if its product ends in the stated way.

Conversely, suppose α\alpha is the rational number pq\dfrac pq. Our aim is to show that for some mm,

θm−1=nmnm−1.\theta_{m-1} = \frac{n_m}{n_m - 1}.
Suppose this is not the case, so that for every mm,
θm−1<nmnm−1.(3)\theta_{m-1} < \frac{n_m}{n_m - 1}. \tag{3}
For each kk we write
θk=pkqk\theta_k = \frac{p_k}{q_k}
as a fraction (not necessarily in lowest terms) where
p0=p,q0=qp_0 = p, \quad q_0 = q
and in general
pk=pk−1nk,qk=qk−1(nk+1).p_k = p_{k-1} n_k, \quad q_k = q_{k-1}(n_k + 1).
The numbers pk−qkp_k - q_k are positive integers: to obtain a contradiction it suffices to show that this sequence is strictly decreasing. Now,
pk−qk−(pk−1−qk−1)=nkpk−1−(nk+1)qk−1−pk−1+qk−1=(nk−1)pk−1−nkqk−1\begin{aligned} p_k - q_k - (p_{k-1} - q_{k-1}) &= n_k p_{k-1} - (n_k + 1) q_{k-1} - p_{k-1} + q_{k-1} \\ &= (n_k - 1) p_{k-1} - n_k q_{k-1} \end{aligned}
and this is negative because
pk−1qk−1=θk−1<nknk−1\frac{p_{k-1}}{q_{k-1}} = \theta_{k-1} < \frac{n_k}{n_k - 1}
by inequality (3).

Transcribed from the official solutions, pages 3–5. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?