Putnam 1994

------
 
 
Problem A3

X is the set of points on one or more sides of a triangle with sides length 1, 1 and √2. Show that if X is 4-colored, then there must be two points of the same color a distance 2 - √2 or more apart.

 

Solution

Fairly easy.

Let the vertices be A, B, C with angle B = 90 degrees. Let the point on AB a distance k = 2 - √2 from A be D. Let the point on AC a distance k from A be E. Let the point on AC a distance k from C be F, and let the point on BC a distance k from C be G. It is easy to check that DF = EG = DG = k.

We show that these 7 points cannot be colored with 4 colors so that no two points the same color are a distance k or more apart. A and C are each a distance k or more from all the other points, so they use up two colors. D and G are a distance k apart so they must be different colors. E is a distance k from G and F is a distance k from D, so E and F must be different colors, but now there is no color left for B, which is a distance greater than k from E and F.

[This result is best possible. Color [A, D) and [A, E) color 1, color [C, F) and [C, G) color 2, color [E, F] color 3, and color [B, D] and [B, G] color 4. Then the only two points of the same color a distance k or more apart are D and G. ]

 


 

Putnam 1994

© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998