Can you paint a 10x10 grid with 3 colours such that it doesn't contain any rectangles whose corners are all the same colour? Rectangles must be 2x2 or greater and parallel to the grid's sides. Computers are allowed :)

A similar question about 2 colours is here: Painting a 4x6 grid with 2 colours

Good luck!

  • 6
    $\begingroup$ Is there a clever way to accomplish this task? "Computers are allowed" makes it seem like the question is intended to be solved by brute-force search, rather than any creativity. $\endgroup$
    – Deusovi
    Sep 20, 2019 at 2:57
  • 1
    $\begingroup$ There is likely a clever method given the combinatorial feel of the problem. If such a method exists, computers ought not to be allowed. $\endgroup$ Sep 20, 2019 at 4:21
  • 1
    $\begingroup$ @Deusovi good question. Even a brute force search program will struggle to find this due to the large search pace, but there are clever algorithms that can solve this. However, there could still be a way that a human can solve this and it will be interesting to see if anyone can do it. By the way, the 4x6 problem I linked to can be done by hand. $\endgroup$ Sep 20, 2019 at 4:27

3 Answers 3


Solution (not mine):

10x10 solution
Source: Rectangle Free Coloring of Grids, https://arxiv.org/abs/1005.3750 page 28
The authors of that paper found the solution by placing one color manually and letting a computer program figure out the other two colors.

  • $\begingroup$ Indeed this is the paper that inspired me to look into this problem. Originally they posted a challenge for the first person to find a solution for 4 colors on a 17x17. It turns out that even 18x18 is possible! $\endgroup$ Sep 25, 2019 at 6:15


By the pigeonhole principle, every row and every column contains at least four squares of the same colour.
Let us look at this particular colour for each column : this gives a list of $10$ colours. By the pigeonhole principle, at least four of these colours are the same.
In an attempt to prove that it's impossible: in a $10\times 4$ grid, can you place four yellow dots per column in such a way that no four dots are the corners of a rectangle?
It turns out you can place four yellow dots per column in up to five columns while satisfying this condition:
enter image description here
If a solution exists, it will have to include a $4\times 10$ subconfiguration of the above, or similar.

  • $\begingroup$ rot13(Vs lbh pna rahzrengr nyy gur cbffvoyr 10k4 fbyhgvbaf, gura sbe nal bar bs gurz gb or va gur yrsgzbfg 4 pbyhzaf, vg'f evtugzbfg 3 pbyhzaf zhfg zngpu gur yrsgzbfg 3 pbyhzaf bs nabgure 10k4 fbyhgvba. Fvzvyneyl, vg'f evtugzbfg 2 pbyhzaf zhfg zngpu gur yrsgzbfg 2 pbyhzaf bs nabgure 10k4 fbyhgvba. Naq vgf evtugzbfg pbyhza zhfg zngpu gur yrsgzbfg pbyhza bs nabgure 10k4 fbyhgvba. Guvf vf orpnhfr jungrire pbyhzaf 5-7 ner, nal 4-jvqgu fhofrpgvba zhfg or bar bs gur 10k4 fbyhgvbaf.) $\endgroup$
    – hdsdv
    Sep 20, 2019 at 8:08
  • $\begingroup$ @hdsdv Not sure I understand: ROT13(gur cvtrbaubyr cevapvcyr qbrf abg nyybj lbh gb fnl fbzrguvat nobhg rnpu naq rirel 4k 10 fhopbasvthengvba). $\endgroup$ Sep 20, 2019 at 8:44
  • $\begingroup$ Lrf, ohg vs jr pna rahzrengr nyy 10k4 fbyhgvbaf, gura nal 4 pbyhzaf bs gur pbzcyrgrq tevq zhfg or bar bs gubfr 10k4 fbyhgvbaf. $\endgroup$
    – hdsdv
    Sep 20, 2019 at 8:49
  • $\begingroup$ @hdsdv well, sure, but this is clearly not doable by hand, which was my intended purpose. $\endgroup$ Sep 20, 2019 at 9:19
  • 2
    $\begingroup$ @ArnaudMortier I just almost made 10x10 by hand, without one in corner. $\endgroup$
    – Jan Ivan
    Sep 20, 2019 at 9:38

Partial - I don't think one can solve it by hand. Closest one I could find, but missing 3x3 (in 12x12, so "maximum" is 12x9 or 9x12):


So, is there a solution? I tried to switch rows and columns, but that leads nowhere.

  • $\begingroup$ Yes a solution exists :) $\endgroup$ Sep 20, 2019 at 10:44

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.