Maths Olympiad Prep

Library / IMO 1J, Independent Study 2 /4 of 4

IMO 1J, Independent Study 2

Combinatorics Difficulty 9.2 IMO level Prove it Taiwan

A kk-set is a set with exactly kk elements. For a 6-set AA and any collection F\mathcal{F} of 4-sets, we say that AA is F\mathcal{F}-good if there are exactly three elements B1,B2,B3B_1, B_2, B_3 in F\mathcal{F} that are subsets of AA, and they furthermore satisfy
(A∖B1)∪(A∖B2)∪(A∖B3)=A. (A \setminus B_1) \cup (A \setminus B_2) \cup (A \setminus B_3) = A.
Find all n≥6n \ge 6 so that there exists a collection F\mathcal{F} of 4-subsets of {1,2,…,n}\{1, 2, \dots, n\} such that every 6-set A⊂{1,2,…,n}A \subset \{1, 2, \dots, n\} is F\mathcal{F}-good.

Solution

**The answer is n=6,7,8n = 6, 7, 8.** Note that for 6≤m≤n6 \le m \le n, if we can construct an F\mathcal{F} satisfying the problem's conditions for {1,2,…,n}\{1, 2, \dots, n\}, then we can necessarily construct an F\mathcal{F} satisfying the problem's conditions for {1,2,…,m}\{1, 2, \dots, m\}. Therefore, we only need to prove two points:

1. When n=9n = 9, there is no F\mathcal{F} satisfying the problem's conditions.
Proof: By contradiction, suppose such an F\mathcal{F} exists. Then for any A⊂{1,2,…,n}A \subset \{1, 2, \dots, n\}, there exist three B∈FB \in \mathcal{F} satisfying the condition, so the total number of (A,B)(A, B) combinations is C6n×3C_6^n \times 3. On the other hand, since each BB lies in C2n−2C_2^{n-2} different AA's, the total number of (A,B)(A, B) combinations is also C2n−2×∣F∣C_2^{n-2} \times |\mathcal{F}|.
This means
3C6n=C2n−2×∣F∣⇒∣F∣=15C4n, 3C_6^n = C_2^{n-2} \times |\mathcal{F}| \Rightarrow |\mathcal{F}| = \frac{1}{5}C_4^n,
hence ∣F∣|\mathcal{F}| is not an integer, a contradiction.

2. When n=8n = 8, there exists an F\mathcal{F} satisfying the problem's conditions.
Let [n]={1,2,…,n}[n] = \{1, 2, \dots, n\}, and for any set XX, let Xmn=X∩{m,m+1,…,n}X_m^n = X \cap \{m, m+1, \dots, n\}.
Consider the set
F={[4],[4]c}∪{X14∪(X14+4),X14∪((Xc)14+4):X14⊂[4],∣X14∣=2}. \mathcal{F} = \{[4], [4]^c\} \cup \{X_1^4 \cup (X_1^4 + 4), X_1^4 \cup ((X^c)_1^4 + 4) : X_1^4 \subset [4], |X_1^4| = 2\}.
Now note that if ∣A∣=6|A| = 6 and A⊂[8]A \subset [8], then ∣A14∣={2,3,4}|A_1^4| = \{2, 3, 4\}.

- ∣A14∣=2|A_1^4| = 2: Without loss of generality, let A={1,2,5,6,7,8}A = \{1, 2, 5, 6, 7, 8\}. In this case, the elements of F\mathcal{F} that are subsets of AA are exactly {5,6,7,8}\{5, 6, 7, 8\}, {1,2,5,6}\{1, 2, 5, 6\}, and {1,2,7,8}\{1, 2, 7, 8\}, and it is easy to check that this satisfies the problem's conditions.

- ∣A14∣=4|A_1^4| = 4: Without loss of generality, let A={1,2,3,4,7,8}A = \{1, 2, 3, 4, 7, 8\}. In this case, the elements of F\mathcal{F} that are subsets of AA are exactly {1,2,3,4}\{1, 2, 3, 4\}, {3,4,7,8}\{3, 4, 7, 8\}, and {1,2,7,8}\{1, 2, 7, 8\}, and it is easy to check that this satisfies the problem's conditions.

- ∣A14∣=3|A_1^4| = 3: In this case ∣A14∣=∣A58∣=3|A_1^4| = |A_5^8| = 3. Consider two cases:

* A58−4=A14A_5^8 - 4 = A_1^4: Without loss of generality, let A={1,2,3,5,6,7}A = \{1,2,3,5,6,7\}. In this case, the elements of F\mathcal{F} that are subsets of AA are exactly {1,2,5,6}\{1,2,5,6\}, {1,3,5,7}\{1,3,5,7\}, and {2,3,6,7}\{2,3,6,7\}, and it is easy to check that this satisfies the problem's conditions.

* A58−4≠A14A_5^8 - 4 \neq A_1^4: Without loss of generality, assume A={1,2,3}A = \{1,2,3\} and A58−4={1,2,4}A_5^8 - 4 = \{1,2,4\},
so A={1,2,3,5,6,8}A = \{1,2,3,5,6,8\}. In this case, the elements of F\mathcal{F} that are subsets of AA are exactly {1,2,5,6}\{1,2,5,6\},
{1,3,6,8}\{1,3,6,8\}, and {2,3,5,8}\{2,3,5,8\}, and it is easy to check that this satisfies the problem's conditions.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.