Maths Olympiad Prep

Library / /180 of 383

Number theory Difficulty 8.5 Shortlist Prove it IMO

Given any set SS of positive integers, show that at least one of the following two assertions holds:
(1) There exist distinct finite subsets FF and GG of SS such that xF1/x=xG1/x\sum_{x \in F} 1 / x = \sum_{x \in G} 1 / x;
(2) There exists a positive rational number r<1r < 1 such that xF1/xr\sum_{x \in F} 1 / x \neq r for all finite subsets FF of SS.

Solutions — 2

Solution 1

Solution 1. Argue indirectly. Agree, as usual, that the empty sum is 00 to consider rationals in [0,1)[0,1); adjoining 00 causes no harm, since xF1/x=0\sum_{x \in F} 1 / x = 0 for no nonempty finite subset FF of SS. For every rational rr in [0,1)[0,1), let FrF_{r} be the unique finite subset of SS such that xFr1/x=r\sum_{x \in F_{r}} 1 / x = r. The argument hinges on the lemma below.

Lemma. If xx is a member of SS and qq and rr are rationals in [0,1)[0,1) such that qr=1/xq - r = 1 / x, then xx is a member of FqF_{q} if and only if it is not one of FrF_{r}.

Proof. If xx is a member of FqF_{q}, then
yFq{x}1y=yFq1y1x=q1x=r=yFr1y \sum_{y \in F_{q} \setminus \{x\}} \frac{1}{y} = \sum_{y \in F_{q}} \frac{1}{y} - \frac{1}{x} = q - \frac{1}{x} = r = \sum_{y \in F_{r}} \frac{1}{y}
so Fr=Fq{x}F_{r} = F_{q} \setminus \{x\}, and xx is not a member of FrF_{r}. Conversely, if xx is not a member of FrF_{r}, then
yFr{x}1y=yFr1y+1x=r+1x=q=yFq1y \sum_{y \in F_{r} \cup \{x\}} \frac{1}{y} = \sum_{y \in F_{r}} \frac{1}{y} + \frac{1}{x} = r + \frac{1}{x} = q = \sum_{y \in F_{q}} \frac{1}{y}
so Fq=Fr{x}F_{q} = F_{r} \cup \{x\}, and xx is a member of FqF_{q}.

Consider now an element xx of SS and a positive rational r<1r < 1. Let n=rxn = \lfloor r x \rfloor and consider the sets Frk/x,k=0,,nF_{r - k / x}, k = 0, \ldots, n. Since 0rn/x<1/x0 \leqslant r - n / x < 1 / x, the set Frn/xF_{r - n / x} does not contain xx, and a repeated application of the lemma shows that the Fr(n2k)/xF_{r - (n - 2k) / x} do not contain xx, whereas the Fr(n2k1)/xF_{r - (n - 2k - 1) / x} do. Consequently, xx is a member of FrF_{r} if and only if nn is odd.

Solution 2

Solution 2. A finite SS clearly satisfies (2), so let SS be infinite. If SS fails both conditions, so does S{1}S \setminus \{1\}. We may and will therefore assume that SS consists of integers greater than 11. Label the elements of SS increasingly x1<x2<x_{1} < x_{2} < \cdots, where x12x_{1} \geqslant 2.

We first show that SS satisfies (2) if xn+12xnx_{n+1} \geqslant 2 x_{n} for all nn. In this case, xn2n1x1x_{n} \geqslant 2^{n-1} x_{1} for all nn, so
s=n11xnn112n1x1=2x1 s = \sum_{n \geqslant 1} \frac{1}{x_{n}} \leqslant \sum_{n \geqslant 1} \frac{1}{2^{n-1} x_{1}} = \frac{2}{x_{1}}
If x13x_{1} \geqslant 3, or x1=2x_{1} = 2 and xn+1>2xnx_{n+1} > 2 x_{n} for some nn, then xF1/x<s<1\sum_{x \in F} 1 / x < s < 1 for every finite subset FF of SS, so SS satisfies (2); and if x1=2x_{1} = 2 and xn+1=2xnx_{n+1} = 2 x_{n} for all nn, that is, xn=2nx_{n} = 2^{n} for all nn, then every finite subset FF of SS consists of powers of 22, so xF1/x1/3\sum_{x \in F} 1 / x \neq 1 / 3 and again SS satisfies (2).

Finally, we deal with the case where xn+1<2xnx_{n+1} < 2 x_{n} for some nn. Consider the positive rational r=1/xn1/xn+1<1/xn+1r = 1 / x_{n} - 1 / x_{n+1} < 1 / x_{n+1}. If r=xF1/xr = \sum_{x \in F} 1 / x for no finite subset FF of SS, then SS satisfies (2).

We now assume that r=xF01/xr = \sum_{x \in F_{0}} 1 / x for some finite subset F0F_{0} of SS, and show that SS satisfies (1). Since xF01/x=r<1/xn+1\sum_{x \in F_{0}} 1 / x = r < 1 / x_{n+1}, it follows that xn+1x_{n+1} is not a member of F0F_{0}, so
xF0{xn+1}1x=xF01x+1xn+1=r+1xn+1=1xn. \sum_{x \in F_{0} \cup \{x_{n+1}\}} \frac{1}{x} = \sum_{x \in F_{0}} \frac{1}{x} + \frac{1}{x_{n+1}} = r + \frac{1}{x_{n+1}} = \frac{1}{x_{n}}.
Consequently, F=F0{xn+1}F = F_{0} \cup \{x_{n+1}\} and G={xn}G = \{x_{n}\} are distinct finite subsets of SS such that xF1/x=xG1/x\sum_{x \in F} 1 / x = \sum_{x \in G} 1 / x, and SS satisfies (1).

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 reproduced verbatim; metadata (topic, difficulty) added by this project.