Maths Olympiad Prep

Library / /29 of 63

Algebra Difficulty 6.7 National olympiad Prove it Japan

Does there exist a positive integer nn satisfying the following condition?

Condition: For an arbitrary rational number rr, there exist an integer bb and nonzero integers a1,a2,,ana_1, a_2, \dots, a_n such that
r=b+1a1++1an r = b + \frac{1}{a_1} + \dots + \frac{1}{a_n}

Solution

We will show that there exists no positive integer nn for which the statement of the problem is satisfied. Let us denote by AnA_n the set of all rational numbers rr for which there exist an integer bb and nonzero integers a1,,ana_1, \dots, a_n such that r=b+k=1n1akr = b + \sum_{k=1}^{n} \frac{1}{a_k}. In order to establish our claim, it suffices to show that for any positive integer nn the set AnA_n does not exhaust the set of all rational numbers. We will show more: in fact there exists a pair pn,qnp_n, q_n of rational numbers with pn<qnp_n < q_n such that there exists no member of the set AnA_n which lies strictly in between pnp_n and qnq_n. We will show the existence of such a pair recursively.

For n=1n = 1 it suffices to take p1=13p_1 = \frac{1}{3} and q1=12q_1 = \frac{1}{2}. Now suppose, we were able to choose for some nn a pair pn,qnp_n, q_n such that pn<qnp_n < q_n for which there is no element from the set AnA_n lying strictly between pnp_n and qnq_n. Set d=qnpnd = q_n - p_n, and define pn+1=pn+d3p_{n+1} = p_n + \frac{d}{3} and qn+1=qnd3q'_{n+1} = q_n - \frac{d}{3}. Suppose that there exist an integer bb and nonzero integers a1,,an+1a_1, \dots, a_{n+1} for which
pn+1<b+k=1n+11ak<qn+1 p_{n+1} < b + \sum_{k=1}^{n+1} \frac{1}{a_k} < q'_{n+1}
holds.

By the induction hypothesis, we have for each l{1,,n+1}l \in \{1, \dots, n+1\}, either
pnb+k=1,kln+11ak p_n \ge b + \sum_{k=1, k \neq l}^{n+1} \frac{1}{a_k}
or
b+k=1,kln+11akqn. b + \sum_{k=1, k \neq l}^{n+1} \frac{1}{a_k} \ge q_n.

If the former holds, then we have 1al<pn+1pn=d3\frac{1}{a_l} < p_{n+1} - p_n = \frac{d}{3}, while if the latter holds, then 1al<qn+1qn=d3\frac{1}{a_l} < q'_{n+1} - q_n = -\frac{d}{3}. In either case, we get 3d<al<3d-\frac{3}{d} < a_l < \frac{3}{d}, which implies that for each l{1,,n+1}l \in \{1, \dots, n+1\}, there are only finitely many possible integral values that ala_l can take. Furthermore if we fix (a1,,an+1)(a_1, \dots, a_{n+1}), the number of integers bb that satisfy the property pn+1<b+k=1n+11ak<qn+1p_{n+1} < b + \sum_{k=1}^{n+1} \frac{1}{a_k} < q'_{n+1} is also finite.

Consequently, we can conclude that there exist at most a finite number of elements of the set An+1A_{n+1} which lie in between pn+1p_{n+1} and qn+1q'_{n+1}. If we define qn+1q_{n+1} to be equal to the minimum of such exceptional numbers of An+1A_{n+1} if such exists and equal to qn+1q'_{n+1} if there is no such exceptional element, then we can see that pn+1p_{n+1} and qn+1q_{n+1} will satisfy the statement of our assertion for n+1n+1, and therefore, our induction process is complete and our assertion is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.