Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By johnsomeone

Math Help - Colored points proof help

  1. #1
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    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.
    Last edited by gfbrd; October 19th 2012 at 02:15 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    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.}
    Last edited by johnsomeone; October 19th 2012 at 08:59 PM.
    Thanks from gfbrd
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Colored points proof help

    Hey there thanks a lot for helping me out!
    I understand it a lot better now
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: March 10th 2012, 05:48 PM
  2. colored lines
    Posted in the LaTeX Help Forum
    Replies: 6
    Last Post: March 25th 2010, 08:56 AM
  3. points proof
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 22nd 2006, 12:34 AM
  4. [SOLVED] Colored Stones
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: April 21st 2005, 06:25 AM

Search Tags


/mathhelpforum @mathhelpforum