Two colouring of a 6 by 6 grid without a monochromatic rectangle This question Monochromatic Rectangle of a 2-Colored 8 by 8 Lattice Grid shows that any two colouring of a 7 by 7 grid must have a rectangle whose vertices are all the same colour. Note that we are only considering rectangles whose sides are parallel to the sides of the grid. Can the same result be shown to hold for a 6 by 6 grid? If not, what is an example of a colouring of a 6 by 6 grid that does not contain a monochromatic rectangle? Furthermore, if it turns out that every colouring of a 6 by 6 grid contains a monochromatic rectangle, what is the largest $n \in \mathbb{N}$ such that an $n$ by $n$ grid can be coloured such that no rectangles are monochromatic?

For six by six it is quite easy.

Call the colours red and blue. Look at the top row. There will be three points the same colour - say red. Concentrate on those columns. If in any row below there are two out of three points red you have a rectangle. But there are only four possible patterns of three points with at most one red, so two of the five rows must have the same pattern and there will be a blue rectangle.

Since one of the possible patterns of three with at most one red is all blue, and if this is present there will be a blue rectangle anyway, this can be adapted to five by five (which must have three the same in the top row).

Can you find a four by four arrangement with no rectangle?