11. On a certain planet there are 100 countries. They all agree to form unions, each with a maximum of 50 countries, and that each country will be joining a number of unions, so that every two different countries will belong to a same union. At least how many unions must be formed?
(1 mark)
11. On a certain planet there are 100 countries. They all agree to form unions, each with a maximum of 50 countries, and that each country will be joining a number of unions, so that every two different countries will belong to a same union. At least how many unions must be formed?
(1 mark)
11. 6
11. First, observe that at least 6 unions must be formed. If a country joins only 2 unions, then it is in a common union with at most \(49 \times 2 = 98\) countries. So each country must join at least 3 unions, and thus the smallest possible number of unions is \(100 \times 3 \div 50 = 6\).
Next, 6 unions are enough. We can divide the 100 countries into 4 groups of 25 countries each. Choose 2 of the 4 groups at a time, and put the 50 countries in the 2 groups into a union. This gives \(C_{2}^{4} = 6\) unions. It is easy to see that in this way, any two countries belong to some union in common. It follows that the answer is 6.