0

In a 13 by 8 rectangular grid, each cell can be colored red, white, or blue. Show that there are at least two 2 by 2 squares in the grid colored exactly the same.

What's the best way to start on this? I'm unable to determine anything based on the grid that will help me.

grxxes75
  • 15
  • 1
    I’ll start by giving a hint. Notice that for any $2 \times 2$ square, there are $3^4 = 81$ possible colorings. How many different $2 \times 2$ regions are there? If there are more than 81, you are done by the pigeon hole principle. – Joe Jun 13 '22 at 19:24
  • You can uniquely define each possible $2 \times 2$ square by its top left square - a trick worth noting: in other configurations the defining unit can be something else, but it is always worth looking for defining units which are easy to count. Other problems will be trickier than this. – Mark Bennet Jun 13 '22 at 19:28
  • 1
    @Joe Ah... I see. There are 84 2 x 2 squares. So by the pigeon hole principle, at most four squares can have the same coloring? – grxxes75 Jun 13 '22 at 19:30
  • 1
    Not quite. You are correct that there are 84 squares. Think of the “pigeons” as these squares, and the “holes” as possible colorings. With 84 pigeons and 81 holes, there must be two pigeons in the same hole (hence at least two 2x2 squares have the same coloring). However far more than 4 squares may have the same coloring. What if we made every cell red? Then all 84 would have the same coloring. – Joe Jun 13 '22 at 19:32

0 Answers0