Maths Olympiad Prep

Library / /18 of 21

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it South Korea

Let A1,A2,,AnA_1, A_2, \dots, A_n be sets. For a subset XX of {1,2,,n}\{1, 2, \dots, n\}, let
N(X)={i{1,2,,n}X:AiAj for all jX}. N(X) = \{i \in \{1, 2, \dots, n\} - X : A_i \cap A_j \neq \emptyset \text{ for all } j \in X\}.
Prove that for every integer 3mn23 \le m \le n - 2, there exists a subset XX of {1,2,,n}\{1, 2, \dots, n\} such that X=m|X| = m and N(X)1|N(X)| \neq 1.

Solution

Let GG be a graph on vertices v1,v2,,vnv_1, v_2, \dots, v_n such that two vertices viv_i and vjv_j are adjacent if and only if AiAjA_i \cap A_j \neq \emptyset and iji \neq j. For a set XX of vertices of GG, let N(X)N(X) be the set of all vertices adjacent to every vertex in XX.
Suppose, on the contrary, that nm+2n \ge m + 2, m3m \ge 3 and N(X)=1|N(X)| = 1 for all subsets X{v1,v2,,vn}X \subseteq \{v_1, v_2, \dots, v_n\} with X=m|X| = m.

Solution 1
A set of vertices is called a clique if every pair of vertices are adjacent in GG. Let TT be a maximum clique of GG. It is trivial that T<m+2|T| < m + 2.

(1) We claim that T=m+1|T| = m + 1. If not, let TT' be a set of mm vertices such that TTT \subseteq T'. Then N(T)N(T') \neq \emptyset and therefore there is a vertex vv adjacent to all vertices in TT. Then T{v}T \cup \{v\} is a clique, contradictory to the assumption that TT is a maximum clique.

(2) No vertex vTv \notin T has more than 1 neighbor in TT. Otherwise, if x,yTx, y \in T are adjacent to vv, then x,yN((T{x,y}){v})x, y \in N((T - \{x, y\}) \cup \{v\}).

(3) Let vTv \notin T and let w1,w2Tw_1, w_2 \in T be two vertices non-adjacent to vv. Since N((T{w1,w2}){v})N((T - \{w_1, w_2\}) \cup \{v\}) can not contain w1w_1 or w2w_2, it must contain yTy \notin T. Then yy is adjacent to at least m1m - 1 vertices of TT, contradictory to (2) because m3m \ge 3. \square

Solution 2
Let did_i be the degree of the vertex viv_i. By considering the number of pairs (X,y)(X, y) of a set XX of mm vertices and a vertex yy adjacent to all vertices of XX, we deduce
i=1n(dim)=(nm). \sum_{i=1}^{n} \binom{d_i}{m} = \binom{n}{m}.

(1) If dimd_i \le m for all ii, then i=1n(dim)n\sum_{i=1}^n \binom{d_i}{m} \le n but n<(nm)n < \binom{n}{m} because 3mn23 \le m \le n - 2. Therefore there exists ii such that dim+1d_i \ge m + 1. We may assume d1m+1d_1 \ge m + 1.

(2) Let SS be the set of all neighbors of v1v_1. Then S=d1m+1|S| = d_1 \ge m + 1. For a subset XX of SS with X=m1|X| = m - 1, since N(X{v1})=1|N(X \cup \{v_1\})| = 1, there exists a unique vertex aSXa \in S - X such that aa is adjacent to all vertices of XX.

If there are distinct subsets X1,X2X_1, X_2 of SS each having m1m-1 vertices such that the corresponding vertices a1,a2Sa_1, a_2 \in S are identical, then a1(=a2)a_1(= a_2) is adjacent to all vertices in X1X2X_1 \cup X_2 and so a subset of X1X2X_1 \cup X_2 with mm vertices will have at least 2 common neighbors, contradictory to the assumption.

Therefore no two vertices aSa \in S corresponding to some subset XX of SS with m1m-1 vertices can be identical and so (d1m1)d1\binom{d_1}{m-1} \le d_1. But this is a contradiction because 2m1d122 \le m-1 \le d_1 - 2. \square

Solution 3
We use (1) of Proof 2 first to show that some vertex has degree at least m+1m + 1.
We proceed by induction on mm.
If m=3m=3, then we use proof 1 to finish the proof.
If m>3m > 3, then let SS be the neighbors of v1v_1. For every subset XX of SS with m1m-1 vertices, we have N(X{v1})=1|N(X \cup \{v_1\})| = 1 and therefore the subgraph G[S]G[S] induced on SS has the property that every set of m1m-1 vertices has exactly one common neighbor. Since Sm+1|S| \ge m + 1, such a graph can not exist by the induction hypothesis. \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 reproduced verbatim; metadata (topic, difficulty) added by this project.