Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
1  
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
show 3 more comments

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.