# Thread: Colored points proof help

1. ## Colored points proof

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.

2. ## Re: Colored points proof

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:

$\text{The induction step is: First, assume the inductive hypothesis: } f(n) = n.$

$\text{Next ASSUME, gearing for a contradiction, that } f(n+1) = f(n).$

$\text{Consider a no-bad-rectangle coloring of } S_{n+1} \text{ in } f(n+1) = f(n) = n \text{ colors.}$

$\text{On } S_{n+1} \text{ consider the } y=n+1 \text{ top horizontal row.}$

$\text{That row must be colored using an infinite number of some color, say green.}$

$\text{We'll hereafter restrict our attention only to those countable number of x such that }$

$\phi(x, n+1) = \text{ green.}$

$\text{If, on } S_n, \phi \text{ used green only a finite number of times, then discard those x's, and will have}$

$\text{and infinite number of x such that } \phi \text{ colors } S_n \text{ without using any green.}$

$\text{But now that's a coloring in } n-1 \text{ colors over an infinite subset of } \mathbb{Z}, \text{ and so could've been}$

$\text{used to construct an } n-1 \text{ coloring of } S_n, \text{ contrary to } f(n) = n.$

$\text{Therefore, on } S_n, \phi \text{ uses green for an infinite number of x.}$

$\text{(Note that that infinity isn't even counting the top horizontal row of } S_{n+1} \text{ that's colored infinitely often in green.}$

$\text{Thus one of the n rows of } S_{n} \text{ must have an infinite number of green coloring.}$

$\text{In particular one such row has at least 2 colorings in green.}$

$\text{Since that reasoning is done after restricting ourselves to only those x's where the n+1 row is colored green,}$

$\text{we get that those two green colorings form a bad green rectangle, which is a contradiction.}$

$\text{Thus the assumption }f(n+1) = f(n) \text{ has produced a contradiction.}$

$\text{By the initial observation, it follows that } f(n+1) = f(n)+1 = n+1.$

$\text{This proves that } f(n) = n \text{ implies that } f(n+1) = n+1.$

$\text{And, with } f(2)=2, f(3) = 3 \text{ established, that completes the proof by induction.}$

3. ## Re: Colored points proof help

Hey there thanks a lot for helping me out!
I understand it a lot better now