Maths Olympiad Prep

Library / /3 of 9

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Singapore

Let AA be a set of positive integers and let kk be a positive integer. Set AA is said to be kk-thin if there are kk positive integers n1,,nkn_1, \dots, n_k so that for all 1i<jk1 \le i < j \le k and all a,aAa, a' \in A, ni+anj+an_i + a \ne n_j + a'. Suppose that ArA_r is a krk_r-thin set for 1rm1 \le r \le m and that r=1mAr\cup_{r=1}^m A_r is the set of all positive integers. Show that
1k1++1km1. \frac{1}{k_1} + \dots + \frac{1}{k_m} \ge 1.

Solution

For any positive integer nn, let [n]={1,2,,n}[n] = \{1, 2, \dots, n\}. Consider a kk-thin set AA with the associated integers n1,,nkn_1, \dots, n_k. Let NN be the maximum of these integers. We let
A+n={a+n:aA}. A + n = \{a + n : a \in A\}.
For any fixed integer LL, let B=A[L]B = A \cap [L]. Now B+niB + n_i, i=1,,ki = 1, \dots, k, are mutually disjoint subsets of [N+L][N+L]. Also B+ni=B|B + n_i| = |B|. Thus kB=B+niL+Nk|B| = \sum |B + n_i| \le L + N. (Note: this yields A[L]L1k+NkL\frac{|A \cap [L]|}{L} \le \frac{1}{k} + \frac{N}{kL}. This shows that the probability that any positive integer belongs to AA is 1/k\le 1/k.)
Now applying this result to the sets A1,,AmA_1, \dots, A_m, with NN being the maximum of all the associated integers, we get Ai[L](L+N)/ki|A_i \cap [L]| \le (L+N)/k_i. Since iAi[L]=[L]\cup_i A_i \cap [L] = [L] and letting p=1kip = \sum \frac{1}{k_i}, we have, by summing over all ii,
L(L+N)p,or(1p)LNp. L \le (L + N)p, \quad \text{or} \quad (1-p)L \le Np.
The above must hold for all positive integer LL. Since NpNp is a constant, this is impossible unless 1p01-p \le 0 or p1p \ge 1.

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.