. For an upcoming international mathematics contest, the participating countries were asked to choose from nine combinatorics problems. Given how hard it usually is to agree, nobody was surprised that the following happened:

- Every country voted for exactly three problems.
- Any two countries voted for different sets of problems.
- Given any three countries, there was a problem none of them voted for.

Find the maximal possible number of participating countries.

## Answer: 56
Certainly, the 56 three-element subsets of the set $\{1,2, \ldots, 8\}$ would do. Now we prove that 56 is the maximum. Assume we have a maximal configuration. Let $Y$ be the family of the three-element subsets, which were chosen by the participating countries and $N$ be the family of the three-element subsets, which were not chosen by the participating countries. Then $|Y|+|N|=\left(\begin{array}{l}9 \\ 3\end{array}\right)=84$. Consider an $x \in Y$. There are $\left(\begin{array}{l}6 \\ 3\end{array}\right)=20$ three-element subsets disjoint to $x$, which can be partitioned into 10 pairs of complementary subsets. At least one of the two sets of those pairs of complementary sets have to belong to $N$, otherwise these two together with $x$ have the whole sets as union, i.e., three countries would have voted for all problems. Therefore, to any $x \in Y$ there are associated at least 10 sets of $N$. On the other hand, a set $y \in N$ can be associated not more than to 20 sets, since there are exactly 20 disjoint sets to $y$. Together we have $10 \cdot|Y| \leq 20 \cdot|N|$ and

$$
|Y|=\frac{2}{3}|Y|+\frac{1}{3}|Y| \leq \frac{2}{3}|Y|+\frac{2}{3}|N|=\frac{2}{3}(|Y|+|N|)=\frac{2}{3} \cdot 84=56 .
$$

Remark: The set of the 84 three-element subsets can be partitioned into 28 triples of pairwise disjoint sets. From any of those triples at most two can be chosen. The partition is not obvious, but possible.