1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user418131 Oct 12 '17 at 13:52
  • $\begingroup$ So should I think of it as colouring in the diagonals in each direction? $\endgroup$ – Natash1 Oct 12 '17 at 13:53
  • 1
    $\begingroup$ 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? $\endgroup$ – user418131 Oct 12 '17 at 13:58
  • 1
    $\begingroup$ 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$)? $\endgroup$ – Natash1 Oct 12 '17 at 14:04
  • 1
    $\begingroup$ Yeah, that's it! $\endgroup$ – user418131 Oct 12 '17 at 14:14
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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