Maths Olympiad Prep

Library / /200 of 397

Number theory Difficulty 5.8 AIME, harder Prove it Taiwan

Given a set SS consisting of several positive integers, prove that at least one of the following two statements holds:

(1) There exist distinct finite subsets FF and GG of SS such that
xF1x=xG1x; \sum_{x \in F} \frac{1}{x} = \sum_{x \in G} \frac{1}{x};
(2) There exists a positive rational number r<1r < 1 such that for every finite subset FF of SS,
xF1xr. \sum_{x \in F} \frac{1}{x} \neq r.

Solutions — 2

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
xFr1x=r. \sum_{x \in F_r} \frac{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=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} = \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=[rx]n = [rx] and consider the sets Frk/xF_{r-k/x}, k=1,,nk = 1, \dots, n. Since
0rnx<1x, 0 \le r - \frac{n}{x} < \frac{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.

Finally, consider F2/3F_{2/3}. By the preceding, [2x/3][2x/3] is odd for each xx in F2/3F_{2/3}, so 2x/32x/3 is not integral. Since F2/3F_{2/3} is finite, there exists a positive rational ϵ\epsilon such that [(2/3ϵ)x]=[2x/3][(2/3 - \epsilon)x] = [2x/3] for all xx in F2/3F_{2/3}. This implies that F2/3F_{2/3} is a subset of F2/3ϵF_{2/3-\epsilon} which is impossible.

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 increasing x1<x2<x_1 < x_2 < \dots, where x12x_1 \ge 2.

We first show that SS satisfies (2) if xn+12xnx_{n+1} \ge 2x_n for all nn. In this case, xn2n1x1x_n \ge 2^{n-1}x_1 for all nn, so
s=n11xnn112n1x1=2x1. s = \sum_{n \ge 1} \frac{1}{x_n} \le \sum_{n \ge 1} \frac{1}{2^{n-1}x_1} = \frac{2}{x_1}.
If x13x_1 \ge 3, or x1=2x_1 = 2 and xn+1>2xnx_{n+1} > 2x_n for some nn, then
xF1x<s<1 for every finite subset F of S, \sum_{x \in F} \frac{1}{x} < s < 1 \text{ for every finite subset } F \text{ of } S,
so SS satisfies (2); and if x1=2x_1 = 2 and xn+1=2xnx_{n+1} = 2x_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
xF1x13 \sum_{x \in F} \frac{1}{x} \ne \frac{1}{3}
and again SS satisfies (2).

Finally, we deal with the case where xn+1<2xnx_{n+1} < 2x_n for some nn. Consider the positive rational
r=1xn1xn+1<1xn+1. r = \frac{1}{x_n} - \frac{1}{x_{n+1}} < \frac{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
xF01x=r<1xn+1, \sum_{x \in F_0} \frac{1}{x} = r < \frac{1}{x_{n+1}},
it follows that xn+1x_{n+1} is not a member of F0F_0, so
xF0{xn+1}=xF01x+1xn+1=r+1xn+1=1xn. \sum_{x \in F_0 \cup \{x_{n+1}\}} = \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
xF1x=xG1x, \sum_{x \in F} \frac{1}{x} = \sum_{x \in G} \frac{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 translated into English from zh; metadata (topic, difficulty) added by this project.