Take the 2-minute tour ×

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

share|improve this question
Can the two L's partly overlap? If so, there are $36$, then use Pigeonhole. –  André Nicolas Nov 19 '12 at 4:37
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? –  UH1 Nov 19 '12 at 4:48
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. –  André Nicolas Nov 19 '12 at 4:52
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? –  UH1 Nov 19 '12 at 4:53
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$. –  André Nicolas Nov 19 '12 at 4:56

1 Answer 1

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

share|improve this answer
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 well –  Amr Nov 19 '12 at 4:46
Actually, if orientation does not matter. We can deduce that we have three with the same color –  Amr Nov 19 '12 at 4:47
I will edit my answer, but I have to leave now. Thank you –  Amr Nov 19 '12 at 4:47
can you please edit your answer quickly? thanks, much appreciated! –  UH1 Nov 19 '12 at 4:49
Thank you Andre Nicolas –  Amr Nov 19 '12 at 6:12

Your Answer


