A conference is attended by 1,000 delegates from various countries. It’s known that any three delegates can speak together without help, though one of the three may have to serve as interpreter for the other two. Prove that all the attendees can be accommodated in double rooms so that the two occupants of each room can speak to each other.
|
SelectClick for Answer |
Choose three delegates at random. Two of them must share a language. Put those two together into a room. Now 998 delegates remain. Again choose three and put the two who can communicate together into a room. Continue until four delegates remain. Call these A, B, C, and D. If all four speak the same language then assign them arbitrarily to the last two rooms. And if (say) A and B can’t communicate directly then both C and D can serve as their interpreters, so we can lodge A with C and B with D.
From D.O. Shklyarsky, N.N. Chentsov, and I.M. Yaglom, Selected Problems and Theorems in Elementary Mathematics, 1979.
|
