Maths Olympiad Prep

Library / /43 of 53

Combinatorics Difficulty 6.9 National olympiad Prove it China

Let nn be an integer greater than two, and let A1,A2,,A2nA_1, A_2, \dots, A_{2n} be pairwise distinct nonempty subsets of {1,2,,n}\{1, 2, \dots, n\}.
Determine the maximum value of i=12nAiAi+1AiAi+1\sum_{i=1}^{2n} \frac{|A_i \cap A_{i+1}|}{|A_i| \cdot |A_{i+1}|}.
(Here, we set A2n+1=A1A_{2n+1} = A_1. For a set XX, let X|X| denote the number of elements in XX.)

Solution

The answer is nn.

We consider each summand si=AiAi+1AiAi+1s_i = \frac{|A_i \cap A_{i+1}|}{|A_i| \cdot |A_{i+1}|}.
If AiAi+1A_i \cap A_{i+1} is the empty set, then si=0s_i = 0.
If AiAi+1A_i \cap A_{i+1} is nonempty, because AiAi+1A_i \neq A_{i+1}, at least one of AiA_i and Ai+1A_{i+1} has more than one element, that is, max{Ai,Ai+1}2\max\{|A_i|, |A_{i+1}|\} \ge 2. Because AiAi+1A_i \cap A_{i+1} is a subset of each of AiA_i and Ai+1A_{i+1}, AiAi+1min{Ai,Ai+1}|A_i \cap A_{i+1}| \le \min\{|A_i|, |A_{i+1}|\} and
si=AiAi+1AiAi+1min{Ai,Ai+1}max{Ai,Ai+1}min{Ai,Ai+1}12. s_i = \frac{|A_i \cap A_{i+1}|}{|A_i| \cdot |A_{i+1}|} \le \frac{\min\{|A_i|, |A_{i+1}|\}}{\max\{|A_i|, |A_{i+1}|\} \cdot \min\{|A_i|, |A_{i+1}|\}} \le \frac{1}{2}.
It follows that
i=12nAiAi+1AiAi+1i=12n12=n. \sum_{i=1}^{2n} \frac{|A_i \cap A_{i+1}|}{|A_i| \cdot |A_{i+1}|} \le \sum_{i=1}^{2n} \frac{1}{2} = n.
This upper bound can be achieved with sets
A1={1},A2={1,2},A3={2},A4={2,3},,A2n2={n1,n},A2n1={n},A2n={n,1}. A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{2\}, A_4 = \{2, 3\}, \dots, A_{2n-2} = \{n-1, n\}, A_{2n-1} = \{n\}, A_{2n} = \{n, 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.