Maths Olympiad Prep

Library / /1 of 2

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Romania

Let kk and mm be integers greater than 11. Consider kk pairwise disjoint sets S1,S2,,SkS_1, S_2, \dots, S_k; each of these sets has exactly m+1m+1 elements, one of which is red and the other mm are all blue. Let F\mathcal{F} be the family of all subsets FF of S1S2SkS_1 \cup S_2 \cup \dots \cup S_k such that, for every ii, the intersection FSiF \cap S_i is monochromatic; the empty set is monochromatic. Determine the largest possible cardinality of a subfamily GF\mathcal{G} \subseteq \mathcal{F}, no two sets of which are disjoint.

Solution

We now prove that G2m1(2m+1)k1|\mathcal{G}| \le 2^{m-1}(2^m + 1)^{k-1} for any G\mathcal{G} satisfying the conditions in the statement. For convenience, write M=2m+1M = 2^m + 1. Let rir_i denote the red element of SiS_i, and let BiB_i be the set of blue elements in SiS_i.
For every subset XiBiX_i \subset B_i and every jZMj \in \mathbb{Z}_M, define the sets

TXi,j={{ri},if j=0;Xi,if j0 and j is even (considered as a number in [1,M1]};BiXi,if j0 and j is odd (considered as a number in [1,M1]}. T_{X_i, j} = \begin{cases} \{r_i\}, & \text{if } j = 0; \\ X_i, & \text{if } j \ne 0 \text{ and } j \text{ is even (considered as a number in } [1, M-1]\}; \\ B_i \setminus X_i, & \text{if } j \ne 0 \text{ and } j \text{ is odd (considered as a number in } [1, M-1]\}. \end{cases}

Note that, for every ii and every jj, the sets TXi,jT_{X_i,j} and TXi,j+1T_{X_i,j+1} are disjoint. Now, for every sets XiBiX_i \subset B_i and every elements jiZMj_i \in \mathbb{Z}_M, i=1,2,,ki = 1, 2, \dots, k, denote
F(X1,X2,,Xk,j1,j2,,jk)=i=1kTXi,ji.() F(X_1, X_2, \dots, X_k, j_1, j_2, \dots, j_k) = \bigcup_{i=1}^{k} T_{X_i, j_i}. \quad (*)

Claim. Every set FFF \in \mathcal{F} has exactly 2mk2^{mk} representations of the form (*).

Proof. Set Fi=FSiF_i = F \cap S_i. If Fi={ri}F_i = \{r_i\}, then there are 2m2^m possible choices for XiX_i, and one should necessarily have ji=0j_i = 0. Otherwise, there are only two possible choices for XiX_i, namely Xi=FiX_i = F_i and Xi=BiFiX_i = B_i \setminus F_i, and for each of them there are 2m12^{m-1} possible choices for jij_i. So, whatever FF, there are 2m2^m possible choices for each pair (Xi,ji)(X_i, j_i) all of which can be made independently, whence a total of 2mk2^{mk} possible tuples (X1,X2,,Xk,j1,j2,,jk)(X_1, X_2, \dots, X_k, j_1, j_2, \dots, j_k). This proves the Claim.

The Claim implies that each FFF \in \mathcal{F} has the same number of representations of the form (*). Thus, it suffices to show that, among all N=2km(2m+1)kN = 2^{km}(2^m + 1)^k tuples (X1,X2,,Xk,j1,j2,,jk)(X_1, X_2, \dots, X_k, j_1, j_2, \dots, j_k), at most 2m12m+1N\frac{2^{m-1}}{2^m+1}N satisfy
F(X1,X2,,Xk,j1,j2,,jk)G. F(X_1, X_2, \dots, X_k, j_1, j_2, \dots, j_k) \in \mathcal{G}.
To this end, split all these tuples into length MM cycles
(F(X1,X2,,Xk,j1,j2,,jk),F(X1,X2,,Xk,j1+1,j2+1,,jk+1),,F(X1,X2,,Xk,j1+M1,j2+M1,,jk+M1)), (F(X_1, X_2, \dots, X_k, j_1, j_2, \dots, j_k), F(X_1, X_2, \dots, X_k, j_1+1, j_2+1, \dots, j_k+1), \dots, F(X_1, X_2, \dots, X_k, j_1+M-1, j_2+M-1, \dots, j_k+M-1)),
and note that any two adjacent sets of a cycle are disjoint. Hence each cycle contains at most M/2=2m1\lfloor M/2 \rfloor = 2^{m-1} sets from G\mathcal{G}. This provides the desired upper bound and completes the solution.

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.