Maths Olympiad Prep

Library / /38 of 54

Combinatorics Difficulty 6.4 National olympiad Prove it China

Determine all possible values of positive integer nn, such that there are nn different 3-element subsets A1,A2,,AnA_1, A_2, \dots, A_n of the set {1,2,,n}\{1, 2, \dots, n\}, with AiAj1|A_i \cap A_j| \neq 1 for all iji \neq j.

Solution

The set of positive integers satisfying the given condition consists of all positive multiples of 44. We first prove that n=4kn = 4k (kZ+k \in \mathbb{Z}_+) satisfies the condition. Define A1,A2,,A4kA_1, A_2, \dots, A_{4k} as follows: A4ij={4i3,4i2,4i1,4i}{4ij}A_{4i-j} = \{4i-3, 4i-2, 4i-1, 4i\} \setminus \{4i-j\}, for all 1ik1 \le i \le k and 0j30 \le j \le 3.

Second, we want to prove that if 4n4 \nmid n, then such nn subsets do not exist. Suppose to the contrary that A1,,AnA_1, \dots, A_n are different 3-element subsets fulfilling the condition stated in the problem. Let A1={a,b,c}A_1 = \{a, b, c\}, consider all the given 3-element subsets with non-empty intersection; we may assume that they are A2,,AmA_2, \dots, A_m after relabeling. Let U=A1A2AmU = A_1 \cup A_2 \cup \dots \cup A_m. We divide into the following different cases:

* If U=3|U| = 3, then m=1<Um = 1 < |U|.
* If U=4|U| = 4, then m(43)=4=Um \le \binom{4}{3} = 4 = |U|.
* If U5|U| \ge 5, then we prove that m<Um < |U| as follows.

Suppose that mUm \ge |U|, then for any 2i,jm2 \le i, j \le m, we have A1Ai=2|A_1 \cap A_i| = 2, A1Aj=2|A_1 \cap A_j| = 2. As A1=3|A_1| = 3, we have AiAjA_i \cap A_j \ne \emptyset. And it follows from AiAj1|A_i \cap A_j| \ne 1 that AiAj=2|A_i \cap A_j| = 2. It means that any two distinct subsets of A1,,AmA_1, \dots, A_m have only two common elements.

Consider the four intersections A1A2,A1A3,A1A4,A1A5A_1 \cap A_2, A_1 \cap A_3, A_1 \cap A_4, A_1 \cap A_5, it follows from the pigeon-hole principle that there are two intersections that are equal; by relabeling again, we may assume that they are A2={a,b,d},A3={a,b,e}A_2 = \{a, b, d\}, A_3 = \{a, b, e\}. Then for any 4im4 \le i \le m, we have a,bAia, b \in A_i; otherwise, AiA_i contains at least one of aa or bb, and the other three elements c,dc, d and ee, in this case, Ai4|A_i| \ge 4, which is impossible. Hence U=m+2|U| = m+2, which contradicts U=m|U| = m.

From the argument above, one can divide the subsets A1,,AnA_1, \dots, A_n into several groups, and any two subsets in the same group have non-empty intersections. Moreover, the number of subsets in the same group is not more than the number of elements appearing in this group. As the number of subsets is nn, which is equal to the number of elements in {1,2,,n}\{1, 2, \dots, n\}, so each group has exactly four subsets. It follows that 4n4|n, which contradicts the original assumption 4n4 \nmid n. \square

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.