Maths Olympiad Prep

Library / /8 of 11

Combinatorics Difficulty 6.5 National Olympiad Prove it New Zealand

Problem:
Let SS be a set of 10 positive integers. Prove that one can find two disjoint subsets A={a1,,ak}A = \{a_{1}, \ldots , a_{k}\} and B={b1,,bk}B = \{b_{1}, \ldots , b_{k}\} of SS with A=B|A| = |B| such that the sums
x=1a1++1akx = \frac{1}{a_{1}} +\dots +\frac{1}{a_{k}}
and
y=1b1++1bky = \frac{1}{b_{1}} +\dots +\frac{1}{b_{k}}
differ by less than 0.01; i.e., xy<1/100|x - y|< 1 / 100

Solution

Solution:
Partition the interval (0.00,2.50](0.00, 2.50] into 250 intervals each of size 0.01.
(0.00,2.50]=(0.00,0.01](0.01,0.02](0.02,0.03](2.49,2.50].(0.00, 2.50] = (0.00, 0.01] \cup (0.01, 0.02] \cup (0.02, 0.03] \cup \dots \cup (2.49, 2.50].
Now consider all possible sets, SS, we can choose from the given 10 positive integers with S=5|S| = 5. Because each of the positive integers must be different, the smallest possible reciprocal sum of one of these sets is
1+12+13+14+15<2.50.1 + \frac{1}{2} +\frac{1}{3} +\frac{1}{4} +\frac{1}{5} < 2.50.
Therefore each of these different sets has a reciprocal sum lying somewhere in the interval (0.00,2.50)(0.00, 2.50). The number of such sets SS is (105)=252\binom{10}{5} = 252 but the number of intervals in our partition is only 250. By the pigeonhole principle there exists at least one interval, (x,x+0.01](x, x + 0.01], and two distinct sets S1,S2S_{1}, S_{2} such that both reciprocal sums,
sS11sandsS21s\sum_{s\in S_{1}}\frac{1}{s}\quad \mathrm{and}\quad \sum_{s\in S_{2}}\frac{1}{s}
lie in (x,x+0.01](x, x + 0.01]. The reciprocal sums of S1S_{1} and S2S_{2} have difference less than 1/1001 / 100 because they both lie in the interval (x,x+0.01](x, x + 0.01]. If S1S_{1} and S2S_{2} are disjoint then we can simply choose A=S1A = S_{1} and B=S2B = S_{2}. Otherwise let C=S1S2C = S_{1} \cap S_{2} be the intersection of S1S_{1} and S2S_{2} and then let A=S1CA = S_{1} \setminus C and let B=S2CB = S_{2} \setminus C. The sets AA and BB are disjoint and equisized because S1=S2|S_{1}| = |S_{2}| and S1S2S_{1} \neq S_{2}.

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.