3

"Each square of a 4-by-19 chessboard is colored either green, yellow or red. Prove that the board must contain a rectangle consisting of at least four squares, and such that its four corner squares have all the same color."

I began by noticing that I can use pigeonhole to show that in permutations of the colours, I'll have G, Y, R, and either G, Y, or R repeated for four colours in each column. When I think about it though, there are so many combinations of these colours that become problematic (like RRRR since that already creates a rectangle) and others which only become problematic when placed with others like them (ex. R,B,G,R and R,G,B,R where both are placed anywhere on the chessboard).

I want to show that a rectangle must be contained by trying to disprove the question - i.e. removing all the problematic permutations of colours, but is this the correct way to go about it / how do I eliminate those permutations without missing one? At this point, I'm just arranging permutations manually and looking to see which ones would cause problems when I put them together.

Questioneer
  • 57
  • 1
    To me it looks like "a rectangle consisting of at least four squares, and such that its four corner squares ..." leaves it ambiguous whether a $1\times4$ rectangle is considered here: it does consist of four squares but on the other hand it does not contain four corner squares as implicitly required. – JiK Jan 16 '15 at 19:17
  • 1
    On a second thought the problem becomes too trivial if $1\times k$ rectangles are considered, because a $1\times 19$ row surely contains two squares of the same color at least distance $4$ apart. – JiK Jan 16 '15 at 19:19

2 Answers2

2

Consider each row of 4 squares. Two of these must be the same colour. These two squares can appear in ${4 \choose 2} = 6 $ different paired locations. Using the three different colours, we can avoid a coincidence of the repeated colours on other rows for $3 \times 6 = 18$ rows. However, we cannot add a 19th row without a repeat of an earlier configuration, so there will an aligned set of identically-coloured squares, giving the required rectangle.

Joffan
  • 39,627
0

Hint: There are $19$ columns. Consider the numbers of columns that have at least $2$ green squares, at least $2$ yellow squares, and at least $2$ red squares.

JiK
  • 5,815
  • 19
  • 39