Let k and m be integers greater than 1. Consider k pairwise disjoint sets S1,S2,…,Sk; each of these sets has exactly m+1 elements, one of which is red and the other m are all blue. Let F be the family of all subsets F of S1∪S2∪⋯∪Sk such that, for every i, the intersection F∩Si is monochromatic; the empty set is monochromatic. Determine the largest possible cardinality of a subfamily G⊆F, no two sets of which are disjoint.
Solution
We now prove that ∣G∣≤2m−1(2m+1)k−1 for any G satisfying the conditions in the statement. For convenience, write M=2m+1. Let ri denote the red element of Si, and let Bi be the set of blue elements in Si. For every subset Xi⊂Bi and every j∈ZM, define the sets
TXi,j=⎩⎨⎧{ri},Xi,Bi∖Xi,if j=0;if j=0 and j is even (considered as a number in [1,M−1]};if j=0 and j is odd (considered as a number in [1,M−1]}.
Note that, for every i and every j, the sets TXi,j and TXi,j+1 are disjoint. Now, for every sets Xi⊂Bi and every elements ji∈ZM, i=1,2,…,k, denote F(X1,X2,…,Xk,j1,j2,…,jk)=i=1⋃kTXi,ji.(∗)
Claim. Every set F∈F has exactly 2mk representations of the form (∗).
Proof. Set Fi=F∩Si. If Fi={ri}, then there are 2m possible choices for Xi, and one should necessarily have ji=0. Otherwise, there are only two possible choices for Xi, namely Xi=Fi and Xi=Bi∖Fi, and for each of them there are 2m−1 possible choices for ji. So, whatever F, there are 2m possible choices for each pair (Xi,ji) all of which can be made independently, whence a total of 2mk possible tuples (X1,X2,…,Xk,j1,j2,…,jk). This proves the Claim.
The Claim implies that each F∈F has the same number of representations of the form (∗). Thus, it suffices to show that, among all N=2km(2m+1)k tuples (X1,X2,…,Xk,j1,j2,…,jk), at most 2m+12m−1N satisfy F(X1,X2,…,Xk,j1,j2,…,jk)∈G. To this end, split all these tuples into length M cycles (F(X1,X2,…,Xk,j1,j2,…,jk),F(X1,X2,…,Xk,j1+1,j2+1,…,jk+1),…,F(X1,X2,…,Xk,j1+M−1,j2+M−1,…,jk+M−1)), and note that any two adjacent sets of a cycle are disjoint. Hence each cycle contains at most ⌊M/2⌋=2m−1 sets from 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.