Problem B1
Each pair from 17 people exchange letters on one of three topics. Prove that there are at least 3 people who write to each other on the same topic. [In other words, if we color the edges of the complete graph K17 with three colors, then we can find a triangle all the same color.]
Solution
Take any person. He writes to 16 people, so he must write to at least 6 people on the same topic. If any of the 6 write to each other on that topic, then we have a group of three writing to each other on the same topic. So assume they all write to each other on the other two topics. Take any of them, B. He must write to at least 3 of the other 5 on the same topic. If two of these write to each other on this topic, then they form a group of three with B. Otherwise, they must all write to each other on the third topic and so from a group of three.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
25 Sep 1998
Last corrected/updated 24 Sep 2003