Maths Olympiad Prep

Track / Stage 9 / 8 of 52 #1888 of 1964

Problem 1888

IMO P2/P5; hard shortlist
Combinatorics Difficulty 9.2 Prove it IMO 1J, Independent Study 2 · 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
(AB1)(AB2)(AB3)=A. (A \setminus B_1) \cup (A \setminus B_2) \cup (A \setminus B_3) = A.
Find all n6n \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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

**The answer is n=6,7,8n = 6, 7, 8.** Note that for 6mn6 \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 BFB \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 C2n2C_2^{n-2} different AA's, the total number of (A,B)(A, B) combinations is also C2n2×FC_2^{n-2} \times |\mathcal{F}|.
This means
3C6n=C2n2×FF=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:

* A584=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.

* A584A14A_5^8 - 4 \neq A_1^4: Without loss of generality, assume A={1,2,3}A = \{1,2,3\} and A584={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.

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