"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.
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.