6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – Tad Jan 28 '17 at 14:05
13
+100
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.