Colored points proof help

**gfbrd** · October 19th 2012, 10:48 AM

Hey there I need some help with another problem

Every point in the plane is colored either red green blue or yellow. Prove that there exists a rectangle in the plane such that all 4 of its vertices are the same color.

so far I know that the color repeats after the 5th point but I'm not sure how to use this to progress the problem further. Hope someone can guide me through this problem so I understand how to do it.

**johnsomeone** · October 19th 2012, 03:38 PM

Interesting problem. I haven't proven it (*edit* - I have now - at the bottom), but I think this is a way to work toward a solution. Here's what comes to mind:

$\text{Consider the strips of integer verticies }S_n = \mathbb{Z} \times \{1, 2, ..., n \}.$

$\text{Define } f : \mathbb{Z}_{\ge 2} \rightarrow \mathbb{Z}_{\ge 2} \text{ by } f(n) = \text{ the minimum number colors for which }S_n$

$\text{can be colored without making a "bad" rectangle (a rectangle whose vertices are all the same color).}$

$\text{An m-coloring is just a map } \phi : S_n \rightarrow \{ 1, 2, ..., m \}, \text{ where we think of the range as a set of m colors.}$

$\text{Have } f(2) = 2, \text{ as can color }S_2 \text{ by } \phi(x, 1) = \text{red}, \phi(x, 2) = \text{blue} \forall x \in \mathbb{Z},$

$\text{and obviously any coloring of } S_2 \text{ by in just one color will have many (all!) rectangles being "bad"}.$

$\text{First observation: For all }n \ge 2, f(n) \le f(n+1) \le f(n) + 1.$

$\text{Proof: If can color } S_{n+1} \text{ in } f(n+1) \text{ colors w/o a bad rectangle, then that colors}$

$S_n \text{ in } f(n+1) \text{ colors w/o a bad rectangle, so }f(n) \le f(n+1).$

$\text{If } \phi \text{ colors } S_{n} \text{ in } f(n) \text{ colors w/o a bad rectangle, then } S_{n+1} \text{ can be colored}$

$\text{in } f(n)+1 \text{ colors w/o a bad rectangle, by keeping the coloring } \phi \text{ on } S_{n} \text{ while coloring the}$

$\text{top horizontal line of } S_{n+1} (=\mathbb{Z} \times \{ n+1 \})\text{ with a single new color.}$

$\text{Therefore } f(n+1) \le f(n)+1.$

$\text{Claim: } f(3) = 3.$

$\text{Proof: Assume f(3) = 2. Let } \phi \text{ be the coloring in 2 colors of } S_3 \text{ without a bad rectangle.}$

$\text{Obviously, 3 points of the same color can only happen above an x at most once for each color.}$

$\text{Thus for infinitely many x, there are two of one color, one of the other above x.}$

$\text{WLOG (Without Loss Of Generality) say red appears exactly once above infinitely many x.}$

$\text{Then for infinitely many x, there's some } y_0 \in \{1, 2, 3 \} \text{ such that}$

$\phi(x, y_0) = \text{ "red", and } \phi(x, y) = \text{ "blue" for } y \ne y_0.$

$\text{That's because there's exactly one red above infinitely many x,}$

$\text{so that red couldn't occur for only finitely many x in all 3 possible rows.}$

$\text{But that means that for infinitely many x, }\phi \text{ will color the other two rows blue,}$

$\text{and that's for an infinite number of x's. Thus there's a bad "blue" rectangle.}$

$\text{So the assumption } f(3) = 2 \text{ leads to a contradition. Thus } f(2) \ne 2.$

$\text{But by the first observation, } 2 = f(2) \le f(3) \le f(2)+1 = 3.$

$\text{Therefore } f(3) = 3.$

$\text{What do you want to bet that } f(n) = n?$

$\text{In particular, if } f(5) = 5, \text{ then you'll know that on } S_5,$

$\text{any coloring with 4 colors produces a "bad" rectangle.}$

$\text{Since } S_5 \subset \mathbb{Z} \times \mathbb{Z} \subset \mathbb{R} \times \mathbb{R}, f(5) = 5, \text{ would give the desired proof.}$

$\text{However, merely proving that } f(k) = 5 \text{ for some } k \text{ would suffice.}$

$\text{It would be ideal to prove that } f(n) = n \text{ by induction.}$

$\text{Based on the initial observation, one need only show that } f(n+1) \ne f(n).$

----------------------------------

$\text{Aside: I see a proof that it's true by induction, } f(n) = n \text{ for all }n \ge 2.$

Spoiler: