Maths Olympiad Prep

Library / /105 of 224

Combinatorics Difficulty 6.0 AIME, harder Prove it Belarus

Each of twenty two sets contains five elements. An intersection of any two of these sets contains exactly two elements.
Prove that the intersection of all these sets contains exactly two elements.

Solution

Assume there are no two such elements. Let A1,,A22A_1, \ldots, A_{22} be the initial sets, Ai=5|A_i| = 5, i=1,,22i = 1, \ldots, 22.
Put S=i=122AiS = \bigcup_{i=1}^{22} A_i and a(x,y)={i{x,y}Ai}a(x, y) = |\{i \mid \{x, y\} \subset A_i\}| for x,ySx, y \in S.
Assume there are five sets that contain xx and yy, without loss of generality, A1,A2,A3,A4,A5A_1, A_2, A_3, A_4, A_5. Then a set AjA_j with {x,y}⊄Aj\{x, y\} \not\subset A_j must contain an element from Ai{x,y}A_i \setminus \{x, y\} for i=1,2,3,4,5i = 1, 2, 3, 4, 5. Hence, {1,2}Aj=\{1, 2\} \cap A_j = \emptyset and a contradiction A1Aj=2|A_1 \cap A_j| = 2 follows.
Consequently, we can assume that a(x,y)4a(x, y) \le 4 for all x,ySx, y \in S.
There are exactly 10 unordered pairs contained in A1A_1, and every AiA_i, i=2,3,,22i = 2, 3, \ldots, 22, contains exactly one of them. Hence, one of the pairs is contained in A1A_1 and three other sets, i.e. there are x,ySx, y \in S with a(x,y)=4a(x, y) = 4.
Without loss of generality, we assume that x=1,y=2x = 1, y = 2 and that the four sets containing 1 and 2 are:
A1={1,2,3,a,b},A2={1,2,4,c,d},A3={1,2,5,e,f},A4={1,2,6,g,h}. A_1 = \{1, 2, 3, a, b\}, \quad A_2 = \{1, 2, 4, c, d\}, \quad A_3 = \{1, 2, 5, e, f\}, \quad A_4 = \{1, 2, 6, g, h\}.
Furthermore, we can assume that A5={1,3,4,5,6}A_5 = \{1, 3, 4, 5, 6\}. To meet the condition AiAj=2|A_i \cap A_j| = 2 for i=1,2,3,4i = 1, 2, 3, 4 every AjA_j with j>4j > 4 must contain either 1 or 2. Assume that 1Aj1 \in A_j for j=5,6,,14j = 5, 6, \ldots, 14. Each of the nine sets AjA_j, j=6,,14j = 6, \ldots, 14, must contain 3,4,53, 4, 5, or 6 because of A5Aj=2|A_5 \cap A_j| = 2. Hence, there is an x{3,4,5,6}x \in \{3, 4, 5, 6\} with a(1,x)5a(1, x) \ge 5, a contradiction. Consequently, at most nine of the sets AjA_j, j=5,,22j = 5, \ldots, 22, contain 1. Analogously, at most nine of the sets AjA_j, j=5,,22j = 5, \ldots, 22, contain 2. It follows that exactly nine of the sets AjA_j, j=5,,22j = 5, \ldots, 22, contain 1, without loss of generality, the sets A5,,A13A_5, \ldots, A_{13}.
Taking into account that a(x,y)4a(x, y) \le 4 for all x,ySx, y \in S and AiAj=2|A_i \cap A_j| = 2 for 1i<j131 \le i < j \le 13, without loss of generality, we can assume
A6={1,3,c,e,g},A7={1,3,d,f,h},A8={1,4,a,e,h}, A_6 = \{1, 3, c, e, g\}, \quad A_7 = \{1, 3, d, f, h\}, \quad A_8 = \{1, 4, a, e, h\},
A9={1,4,b,f,g},A10={1,5,a,d,g},A11={1,5,b,c,h}, A_9 = \{1, 4, b, f, g\}, \quad A_{10} = \{1, 5, a, d, g\}, \quad A_{11} = \{1, 5, b, c, h\},
and there is no proper choice left for A12A_{12}.

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.