# Number theory/combinatorics problem?

Given any set of $14$ (different) natural numbers, prove that for some $k$ ($1 ≤ k ≤ 7$) there exist two disjoint $k$-element subsets $\{a_1,...,a_k\}$ and $\{b_1,...,b_k\}$ such that the sum of the reciprocals of all elements in each set differ by less than $0.001$, i.e. $|A−B| < 0.001$, where $A =$ the sum of the reciprocals of the elements of the first subset and $B =$ the sum of the reciprocals of the elements of the second subset.

Note: this problem is from the $1998$ Czech and Slovak Math Olympiad

• What have you tried so far? That will help people give you an appropriate hint. (In particular, have you tried figuring out the bound when you have 2 numbers? 4 numbers?) – Tad Jan 28 '17 at 14:05

## 2 Answers

Consider the $\binom{14}{7} = 3432$ $7$-element subsets of the fourteen numbers, and look at the sums of the reciprocals of the numbers in each subset. Each sum is at most$$1 + {1\over2} + \ldots + {1\over7} = {{363}\over{140}} < 2.60,$$so each of the $3432$ sums lies in one of the $2600$ intervals$$\left(0, {1\over{1000}}\right], \text{ }\left({1\over{1000}}, {2\over{1000}}\right], \text{ }\ldots\text{ }, \text{ }\left({{2599}\over{1000}}, {{2600}\over{1000}}\right].$$Then by the pigeonhole principle, some two sums lie in the same interval. Taking the corresponding sets and discarding any possible common elements, we obtain two satisfactory subsets $A$ and $B$.

Here is a greedy approach, which suggests that $14$ could be lowered to $13$ but is not a proof. If the first number is very large to keep its reciprocal small, the next one needs to be at most $999$ so its reciprocal exceeds $0.001$. Then the next needs to be at most $499$ so its reciprocal exceeds $0.002$. The next reciprocal needs to be at least $0.004$, so the number is at most $249$. We can represent these as $0,1,2,4$, the number of thousandths in the reciprocal. If we continue we get $0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284\ldots$, shown in OEIS $A005318$. The fact that the thirteenth term exceeds $1000$ suggests we have run out of room already.