[ky3]

A grid with 19 columns is enough. Every column at worst has all 3 colors, one of them used twice. Once we fix that one color, there are C(4,2)=6 ways of filling out the rest of the entries. Since there are 3 colors, there are exactly 6*3=18 worst possible columns. With 19 columns a repetition is guaranteed, yielding the desired rectangle.

For fun, try strengthening the result to a square.