1

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?

Natash1
  • 1,379
  • I wouldn't start with the assumption that the colours must alternate. Rather, think about what an $L$ means in terms of adjacent and non-adjacent colours –  Oct 12 '17 at 13:52
  • So should I think of it as colouring in the diagonals in each direction? – Natash1 Oct 12 '17 at 13:53
  • 1
    Right, the important idea is that if they were not to be alternating (as you originally assumed), then we would automatically have an $L$. So now what? –  Oct 12 '17 at 13:58
  • 1
    Oh I see, so I didn't really have to form any groups. After doing the diagonals, I've painted $32$ squares. Another square being painted would have that coloured square be adjacent to two other coloured squares (forming an $L$)? – Natash1 Oct 12 '17 at 14:04
  • 1
    Yeah, that's it! –  Oct 12 '17 at 14:14

1 Answers1

4

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.

Stefan4024
  • 35,843