Library / Singapore International Mathematical Olympiad Committee National Team Selection Test /3 of 8

Singapore International Mathematical Olympiad Committee National Team Selection Test

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Singapore

Let $A$ be a set of positive integers and let $k$ be a positive integer. Set $A$ is said to be $k$ -thin if there are $k$ positive integers $n_1, \dots, n_k$ so that for all $1 \le i < j \le k$ and all $a, a' \in A$ , $n_i + a \ne n_j + a'$ . Suppose that $A_r$ is a $k_r$ -thin set for $1 \le r \le m$ and that $\cup_{r=1}^m A_r$ is the set of all positive integers. Show that
$\frac{1}{k_1} + \dots + \frac{1}{k_m} \ge 1.$

Solution

For any positive integer $n$ , let $[n] = \{1, 2, \dots, n\}$ . Consider a $k$ -thin set $A$ with the associated integers $n_1, \dots, n_k$ . Let $N$ be the maximum of these integers. We let
$A + n = \{a + n : a \in A\}.$
For any fixed integer $L$ , let $B = A \cap [L]$ . Now $B + n_i$ , $i = 1, \dots, k$ , are mutually disjoint subsets of $[N+L]$ . Also $|B + n_i| = |B|$ . Thus $k|B| = \sum |B + n_i| \le L + N$ . (Note: this yields $\frac{|A \cap [L]|}{L} \le \frac{1}{k} + \frac{N}{kL}$ . This shows that the probability that any positive integer belongs to $A$ is $\le 1/k$ .)
Now applying this result to the sets $A_1, \dots, A_m$ , with $N$ being the maximum of all the associated integers, we get $|A_i \cap [L]| \le (L+N)/k_i$ . Since $\cup_i A_i \cap [L] = [L]$ and letting $p = \sum \frac{1}{k_i}$ , we have, by summing over all $i$ ,
$L \le (L + N)p, \quad \text{or} \quad (1-p)L \le Np.$
The above must hold for all positive integer $L$ . Since $Np$ is a constant, this is impossible unless $1-p \le 0$ or $p \ge 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 reproduced verbatim; metadata (topic, difficulty) added by this project.