Putnam Math Challenge

Here's a cool math question I encountered taking the Putnam exam in college. As I recall (it was a long time ago) there were 6 questions on the exam. I remember this one because it was one of the only questions for which I got (partial) points. That sounds pitiful, but getting a few points on the Putnam, even on a single question, is quite an accomplishment.

Maybe you'll have fun with it too.
If every point in the X-Y plane is painted one of 3 colors, must there necessarily always be 2 points 1 inch apart having the same color?

My wording is not exact but that's the gist of it. My assumptions were that "1 inch" means "some arbitrary distance D", and every infinitesimal point (every point having real numbers as coordinates) is painted.

SPOILER ALERT: If you want to think about this before reading a solution, stop reading now, because what comes next is a solution. I say "a" solution because there may be others.

Now some whitespace to put the solution below the fold of your screen...

.

.

.

.

.

.

.

.

.

.

The first thing that came to mind is a circle of radius D - lots of points all equidistant from the center. But if none of the points along the circle are the same color as the center, we haven't proven anything. Since there are only 3 colors, that would mean the points along the circle alternate between the other 2 colors. There's no rule that says they can't all be the same, but if they were, each diameter of the circle would have 2 points of the same color distance 2*D apart, and one inch being some arbitrary distance, that's as good as D.

This led to 2 other thoughts:

  • What about points along the circle that are distance D apart?

  • An approach to a proof: devise some configuration of points that MUST be colored a certain way in order to prevent any 2 points distance D apart from being the same color, and show that this forces 2 other points some other distance apart to be the same color.

    • Let's take the first. If we mark the points along the circle that are distance D apart, where D is equal to the radius, we get a hexagon inscribed inside the circle. Each of the points on this hexagon must be a different color from the center, and they must alternate between the 2 remaining other colors. Like this:

    We could fill the entire X-Y plane with this design of hexagons, and no two points at 2 adjacent vertices would be the same color. But now look at it as equilateral triangles instead of hexagons. There are little triangles (drawn with black lines) but there are also big triangles spanning the little ones. The three blue dots along the hexagon make an equilateral triangle. Like this:

    Thus we have blue points that are exactly distance X apart from each other. X > D, but it doesn't matter because D itself was arbitrary.

    In fact, we've created an infinite number of points exactly distance X apart having the same color. Like this:

    And now we get to the second point from above. By showing how the colors MUST be arranged in this hexagon pattern for some arbitrary distance D, we have demonstrated that this REQUIRES points a bigger distance apart to be the same color. Since D was arbitrary, we can say X is 1 inch. Thus we have the answer: YES: no matter how you color the points, if you only have 3 colors then there must necessarily always be 2 points 1 inch apart having the same color.

    BTW, if you're one of those folks who like algebra (even more rare than folks who like math), you can figure out what X is if D is 1. By my calculation, it's the square root of 3, but that's not really material to this question.