Maths Olympiad Prep

Library / /4 of 6

Combinatorics Difficulty 6.2 National olympiad Prove it Brazil

nn tokens are to be placed on the squares of a 10×1010 \times 10 board such that no 4 tokens be the vertices of a rectangle with sides parallel to the sides of the board. Find the greatest value of nn for which this is possible.

Solution

Let Ai{1,2,,10}A_i \subset \{1, 2, \dots, 10\} be the set of the positions of the tokens in the ii-th line of the board, 1i101 \le i \le 10. The problem is equivalent to finding A1,A2,,A10A_1, A_2, \dots, A_{10} such that AiAj1|A_i \cap A_j| \le 1 for iji \ne j and A1+A2++A10|A_1| + |A_2| + \dots + |A_{10}| is maximum.

Let kik_i be Ai|A_i|. The (ki2)\binom{k_i}{2} subsets of AiA_i with 2 elements must not be contained in any other Aj,jiA_j, j \ne i. Hence
1i10(ki2)(102)1i10(2ki1)2370 \sum_{1 \le i \le 10} \binom{k_i}{2} \le \binom{10}{2} \Leftrightarrow \sum_{1 \le i \le 10} (2k_i - 1)^2 \le 370
By Cauchy's inequality,
1i10121i10(2ki1)2(1i10(2ki1))21i10(2ki1)103701i10ki35 \begin{aligned} & \sum_{1 \le i \le 10} 1^2 \cdot \sum_{1 \le i \le 10} (2k_i - 1)^2 \ge \left( \sum_{1 \le i \le 10} (2k_i - 1) \right)^2 \\ \Rightarrow & \sum_{1 \le i \le 10} (2k_i - 1) \le \sqrt{10 \cdot 370} \\ \Leftrightarrow & \sum_{1 \le i \le 10} k_i \le 35 \end{aligned}
The equality holds if and only if 5 of the kik_i's equal 4 and the other 5 equal 3. In this case, 1i10(ki2)=(102)\sum_{1 \le i \le 10} \binom{k_i}{2} = \binom{10}{2} and hence each subset of {1,2,,10}\{1, 2, \dots, 10\} with 2 elements should be in exactly one AiA_i.

Therefore if it were possible to construct an instance with 35 tokens, each element of {1,2,,10}\{1, 2, \dots, 10\} would either be in 3 subsets with 4 elements or
in 1 subset with 4 elements and 3 subsets with 3 elements. Since there are 5 subsets with 4 elements, there must be elements which belong to 3 subsets with 4 elements. We may thus suppose wlog that A1={1,2,3,4}A_1 = \{1, 2, 3, 4\}, A2={1,5,6,7}A_2 = \{1, 5, 6, 7\}, A3={1,8,9,10}A_3 = \{1, 8, 9, 10\}. However any other subset with 4 elements would be contained in {2,3,,10}\{2, 3, \dots, 10\} and therefore its intersection with one of A1A_1, A2A_2 or A3A_3 would have at least 2 elements. We conclude that it is impossible to have 1i10ki=35\sum_{1\le i\le 10} k_i = 35.

On the other hand, there exist instances with 34 tokens:
Figure 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 and solution reproduced as published; topic and difficulty added by this site.