On planet $X$, there are 100 alien countries in conflict with each other. To prevent a world war, these countries organize themselves into military alliance groups for mutual protection. We know that the alliances follow these rules:

1) No alliance contains more than 50 countries.
2) Any two countries belong to at least one alliance.

a) Is it possible for a country to participate in fewer than three military alliances?

b) What is the minimum number of alliances possible for these two conditions to be satisfied?
Solution

a) It is not possible. Suppose that country $A$ belongs to at most two alliances. In this case, since each alliance has at most 50 countries, country $A$ is a member of the same alliance with at most $49+49=98$ countries. Since there are 99 countries distinct from $A$, at least one of them will not be in an alliance with $A$, which conflicts with rule (2).
b) Since each country participates in at least 3 alliances, if we sum the number of participations of all countries in all alliances, we will get at least the number $3 \cdot 100=300$. On the other hand, each alliance accounts for at most 50 participations. Thus, the minimum number of alliances cannot be less than $\frac{300}{50}=6$. To verify that this number is indeed the smallest possible, it suffices to exhibit an example of a configuration in which it is achieved. Divide the 100 countries into 4 groups of 25 countries: $A$, $B, C, D$. Now, form the alliances of 50 countries consisting of all 6 combinations of two of these groups:

$$
A \cup B, A \cup C, A \cup D, B \cup C, B \cup D \text { and } C \cup D
$$