Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /184 of 359

Taiwan IMO Selection Camp

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
∑x∈F1x=∑x∈G1x; \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,
∑x∈F1x≠r. \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 ∑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∈Fr1x=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 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=∑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} = \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 = [rx] and consider the sets Fr−k/xF_{r-k/x}, k=1,…,nk = 1, \dots, n. Since
0≤r−nx<1x, 0 \le r - \frac{n}{x} < \frac{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.

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 x1≥2x_1 \ge 2.

We first show that SS satisfies (2) if xn+1≥2xnx_{n+1} \ge 2x_n for all nn. In this case, xn≥2n−1x1x_n \ge 2^{n-1}x_1 for all nn, so
s=∑n≥11xn≤∑n≥112n−1x1=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 x1≥3x_1 \ge 3, or x1=2x_1 = 2 and xn+1>2xnx_{n+1} > 2x_n for some nn, then
∑x∈F1x<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
∑x∈F1x≠13 \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=1xn−1xn+1<1xn+1. r = \frac{1}{x_n} - \frac{1}{x_{n+1}} < \frac{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∈F01x=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
∑x∈F0∪{xn+1}=∑x∈F01x+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
∑x∈F1x=∑x∈G1x, \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,604 problems in a working order, from Junior Challenge 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.