Seventeenth ROMANIAN MASTER OF MATHEMATICS

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

$$T_{X_i,j}=\{\begin{array}{ll}\{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{array}$$

Note that, for every $i$ and every $j$, the sets $T_{X_i,j}$ and $T_{X_i,j+1}$ are disjoint. Now, for every sets $X_i\subset B_i$ and every elements $j_i\in {\mathbb{Z}}_M$, $i=1,2,\dots ,k$, denote $$F(X_1,X_2,\dots ,X_k,j_1,j_2,\dots ,j_k)=\bigcup _{i=1}^k{T}_{X_i,j_i}.(\ast )$$

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

Proof. Set $F_i=F\cap S_i$. If $F_i=\{r_i\}$, then there are $2^m$ possible choices for $X_i$, and one should necessarily have $j_i=0$. Otherwise, there are only two possible choices for $X_i$, namely $X_i=F_i$ and $X_i=B_i\setminus F_i$, and for each of them there are $2^{m-1}$ possible choices for $j_i$. So, whatever $F$, there are $2^m$ possible choices for each pair $(X_i,j_i)$ all of which can be made independently, whence a total of $2^{mk}$ possible tuples $(X_1,X_2,\dots ,X_k,j_1,j_2,\dots ,j_k)$. This proves the Claim.

The Claim implies that each $F\in \mathcal{F}$ has the same number of representations of the form ($\ast$). Thus, it suffices to show that, among all $N=2^{km}(2^m+1{)}^k$ tuples $(X_1,X_2,\dots ,X_k,j_1,j_2,\dots ,j_k)$, at most $\frac{2^{m-1}}{2^m+1}N$ satisfy $$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 $M$ cycles $$(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 $\lfloor M/2\rfloor =2^{m-1}$ sets from $\mathcal{G}$. This provides the desired upper bound and completes the solution.