1
$\begingroup$

Prove that no matter how we color the chess board, there must be two L-regions that are colored identically.

Explanation: An L-region is a collection of $5$ squares in the shape of a capital L. Such a region includes a square (the corner of the L) together with the two squares above and the two squares to the right.

Related Topics: Pigeonhole principle

  • 1
    Can the two L's partly overlap? If so, there are $36$, then use Pigeonhole.2012-11-19
  • 0
    i don't think it matters whether they overlap or not as long as we show such two L's exist. how do you get 36?2012-11-19
  • 0
    Consider the location of the "middle" square. It can be on any of the little squares in the bottom left $6\times 6$ subsquare of the original chessboard. It has to start the third row down, and can occupy $6$ positions in that row. Same for next row down, and so on all the way to the bottom.2012-11-19
  • 0
    So basically the question can be answered like this: Since there are 2^5 = 32 ways to color an L figure and there are 36 L's possible on the board, by the pigeonhole principle, there are always two L's that are covered identically. Is that complete and correct in your view?2012-11-19
  • 0
    The question can be answered as in the post by Amr, except that the $64$ (and $\gt 64$) has to be replaced by $36$. But that's big enough, though not by much. I just saw your edited comment. It is coloured identically, not covered. And probably you need to explain why $36$.2012-11-19
  • 0
    but you agree that there are exactly 36 possible L-regions on the chessboard?2012-11-19
  • 0
    Yes, of course, if you look back to the very first comment, I asserted there are $36$.2012-11-19
  • 0
    great then your first comment was enough to answer the question, thanks! really appreciate it!2012-11-19

1 Answers 1

2

Let A be the set of L-regions and S be the set lower left 6x6 squares. Define a function $f:A→ S$ such that f sends each L-region to the square at its corner. Clearly, f is onto. Therefore $|A|>=|f(A)|>=|S|=36$.

Number of ways to color an L region is $2^5=32$

Thus, by the pigeonhole principle we know that there are two L-regions with the same color

  • 0
    OH. I just read his question again and I noticed that he specified directions ( 2 right and 2 above). I thought that 2 below 2 left is possible as well2012-11-19
  • 0
    Actually, if orientation does not matter. We can deduce that we have three with the same color2012-11-19
  • 0
    I will edit my answer, but I have to leave now. Thank you2012-11-19
  • 0
    can you please edit your answer quickly? thanks, much appreciated!2012-11-19