Given points P1, P2, ... , Pn on a line we construct a circle on diameter PiPj for each pair i, j and we color the circle with one of k colors. For each k, find all n for which we can always find two circles of the same color with a common external tangent.
Solution
Answer: n > k+1.
There are n-1 circles with diameter PiPi+1. Obviously, each pair has a common tangent. If n-1 > k, then two of them must have the same color.
If n-1 ≤ k, then color all circles with diameter PiPj and i < j with color i. Then if two circles have the same color, then both have a tangent at one of the points. Hence one lies inside the other and they do not have a common external tangent.
© John Scholes
jscholes@kalva.demon.co.uk
24 Oct 2002