Pigeonhole Principle for a chessboard

666 Views Asked by At

How do I usually approach pigeonhole principle questions in general? Do I always look at the "biggest" case scenario?
If so, I'm unsure what it is for the following problem:
Prove that if $33$ squares on a chessboard are coloured red, there must be three squares forming a red "L" (in any direction).

So I think a chessboard has $64$ squares. It looks like I want to split up into $32$ pigeonholes (looking at the $33$). So I coloured the chessboard in a way so that it's checkered (alternating colours).
Then I form groups containing two squares horizontally (or vertically) which would give $32$ groups. Then a 33rd red square must fall in one of these groups.
I feel like this is a really clunky way to approach these problems. Is there a better way?

1

There are 1 best solutions below

0
On BEST ANSWER

Divide the chessboard in $16$ squares of size $2 \times 2$. Then by Pigeonhole Principle there is at least one square with $3$ small $1 \times 1$ squares coloured red. Now prove that these red coloured squares must be in an $L$ shape.