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?

  • $\begingroup$ Do the sides of the rectangle have to be parallel to the grid lines? $\endgroup$ – Ankoganit Jun 5 '17 at 11:39
  • $\begingroup$ @Ankoganit I'm looking at the case when the sides do have to be parallel. $\endgroup$ – michaelhowes Jun 5 '17 at 11:41

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?

| cite | improve this answer | |
  • $\begingroup$ Thank you very much for your answer. I have found such a four by four arrangement. $\endgroup$ – michaelhowes Jun 5 '17 at 12:34

The number of points occupied by a colour in a given column implies that a certain number of possible pairings have been produced, for possible matching to the same pair in another column. So with $\{0,1,2,3,4,5,6\}$ points of a single colour you have $\{0,0,1,3,6,10,15\}$ pairings respectively.

For a six-by-six rectangle, there are $\binom 62 = 15$ possible pairings in a column. As soon as one colour has enough entries to accumulate $16$ pairings from its column entries, as above, there will be a matched pairing between columns giving the monochrome rectangle. Between the two colours, once total pairings reaches $31$ there will be a monochrome rectangle. Splitting the colours evenly ($3$ each) produces the lowest net pairings of $6$ per column, but clearly with six columns we have at least $36$ net pairings and must have a monochrome rectangle.

For a five-by-six rectangle, using the same arguments, we have $\binom 52 = 10$ possible pairings per column and at least $4$ net pairings per column, reaching at least $24(>2{\times} 10)$ net pairings by the sixth column and the certainty of a monochrome rectangle.

For a five-by-five square, one colour will have at least $13$ entries which you can show leads to at least $11$ pairings across the $5$ columns:

$\begin{array}{c|c|c} \text{col entries} & \text{pairings} \\ \hline (5,2+,\ldots) & 11+ \\ (4,4,\ldots) & 12+ \\ (4,3,3,2,1) & 13 \\ (4,3,2,2,2) & 12 \\ (3,3,3,3,1) & 12 \\ (3,3,3,2,2) & 11 \\ \end{array}$

and $11$ or more pairings over the 5 columns will mean that some $2$ pairs will align, giving a monochrome rectangle.

Finally a four-by-six rectangle can avoid a monochrome rectangle, guided by the above:

enter image description here

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.