Maths Olympiad Prep

Library / IMO Shortlist /167 of 365

IMO Shortlist

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 ∑x∈F1/x=∑x∈G1/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 ∑x∈F1/x≠r\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 ∑x∈F1/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 ∑x∈Fr1/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 q−r=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
∑y∈Fq∖{x}1y=∑y∈Fq1y−1x=q−1x=r=∑y∈Fr1y \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
∑y∈Fr∪{x}1y=∑y∈Fr1y+1x=r+1x=q=∑y∈Fq1y \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=⌊rx⌋n = \lfloor r x \rfloor and consider the sets Fr−k/x,k=0,…,nF_{r - k / x}, k = 0, \ldots, n. Since 0⩽r−n/x<1/x0 \leqslant r - n / x < 1 / x, the set Fr−n/xF_{r - n / x} does not contain xx, and a repeated application of the lemma shows that the Fr−(n−2k)/xF_{r - (n - 2k) / x} do not contain xx, whereas the Fr−(n−2k−1)/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 x1⩾2x_{1} \geqslant 2.

We first show that SS satisfies (2) if xn+1⩾2xnx_{n+1} \geqslant 2 x_{n} for all nn. In this case, xn⩾2n−1x1x_{n} \geqslant 2^{n-1} x_{1} for all nn, so
s=∑n⩾11xn⩽∑n⩾112n−1x1=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 x1⩾3x_{1} \geqslant 3, or x1=2x_{1} = 2 and xn+1>2xnx_{n+1} > 2 x_{n} for some nn, then ∑x∈F1/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 ∑x∈F1/x≠1/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/xn−1/xn+1<1/xn+1r = 1 / x_{n} - 1 / x_{n+1} < 1 / x_{n+1}. If r=∑x∈F1/xr = \sum_{x \in F} 1 / x for no finite subset FF of SS, then SS satisfies (2).

We now assume that r=∑x∈F01/xr = \sum_{x \in F_{0}} 1 / x for some finite subset F0F_{0} of SS, and show that SS satisfies (1). Since ∑x∈F01/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
∑x∈F0∪{xn+1}1x=∑x∈F01x+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 ∑x∈F1/x=∑x∈G1/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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.