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