31st IMO shortlist 1990/2 solution

31st IMO 1990 shortlist

Problem 2

11 countries each have 3 representatives. Is it possible to find 1990 committees C₁, C₂, ... , C₁₉₉₀ such that each committee has just one representative from each country, no two committees have the same members, and every two committees have at least one member in common except for the pairs (C₁, C₂), (C₂, C₃), (C₃, C₄), ... , (C₁₉₉₁, C₁₉₉₂), (C₁₉₉₂, C₁)?

Answer

Yes

Solution

Consider the more general case of m countries and n committees. A committee can be represented as a sequence of m digits, where each digit is 1, 2, or 3 (so the kth place determines whether the member from country k is the 1st, 2nd or 3rd). No two sequences can be identical and if we arrange them in a circle, then adjacent sequences have no match, whereas other pairs match in at least one place.

A little experimentation suggests it is possible provided n is not too big relative to m. Assuming it is possible, there are two approaches to this type of problem. One must either find some explicit solution, often using mod. Or one must show how a solution for (m, n) gives rise to a solution for larger (m, n).

Suppose A₁, A₂, ... A_n is a solution for (m, n) and k <= m (so each A_i is a sequence of m digits chosen from 1, 2, 3). Then consider:
A₁ 3
A₂ 1
A₃ 2
A₄ 1
A₅ 2
...
A_k-2 1
A_k-1 2
A_k 3
A_k-1 1
A_k-2 2
...
A₃ 1
A₂ 2

For A₂ down to A_k-1 we alternate between 1 and 2 for the n+1th country to ensure that adjacent committees do not overlap (so depending on whether k is even or odd, we will end up with 2 (as shown) or 1 for A_k-1. From the bottom A₂ up to A_k-1 we alternate between 2 and 1, so that each A_i appears once with 1 and once with 2 (for 1 < i < k), thus ensuring no duplicate committees. For A₁ and A_k we cannot use 1 or 2 for country n+1, so we use 3. Thus we derive a solution for (2k-2, n+1) from the solution for (m, n). (Finally, note the slight subtlety that this even works for m = k, even though in that case we do not have any overlap between A₁ and A_k, because we get the overlap on country n+1.)

Note that 2¹⁰ = 1024, but we do not quite double m each time, so starting from (3, 1) (with the trivial solution 1, 2, 3) looks tight. Indeed we get (4, 2), then (6, 3), so at best (6·256, 11) which is not good enough). However, it is not hard to construct (6, 2): 11, 22, 31, 12, 21, 32. Now we get successively, (10, 3), (18, 4), (34, 5), (66, 6), (130, 7), (258, 8), (514, 9), (1026, 10), (1990, 11).

31st IMO shortlist 1990