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

  • 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
    can you please edit your answer quickly? thanks, much appreciated!2012-11-19