Suppose you have an infinite plane, and each point on the plane has been arbitrarily painted one of two colors.

Prove that there exists an equilateral triangle whose vertices are all the same color.

What is the fewest number of points needed to prove this?

This proof uses 8 points; I don't know if that's minimal:

Take a grid of points at the vertices of tesselated equilateral triangles of side length 1. Take one equilateral triangle with sides 2 units long. Either all three vertices are the same color (in which case we've met the desired condition) or two are one color and one is another. Call the two of the same color A and the odd color B, and set the points (as well as 5 neighboring points of the grid labeled with digits) out as below:

    2 A


   4 1 3


    B 5 A

Point 1 must be either color A or color B.

If it is color A, then point 2 must be color B to avoid the triangle 1,2,top-existing-A from being all A; and point 3 must be color B to prevent 1,3, top-existing-A from being all A. But then triangle 2,3,original-B form an equilateral triangle that's all B.

If on the other hand point 1 is color B, then point 4 must be color A to avoid 1,B,4 from being all B; and point 5 must be color A to prevent 1,5,B from being all color B. But then triangle 4,5,original-top-A is all A.

This exhausts the alternatives: somewhere along the line we had an equilateral triangle with vertices of all one color.

Posted by Charlie on 2003-08-25 13:17:23