# Painting a 10x10 grid with 3 colours

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!

• 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. – Deusovi Sep 20 '19 at 2:57
• There is likely a clever method given the combinatorial feel of the problem. If such a method exists, computers ought not to be allowed. – greenturtle3141 Sep 20 '19 at 4:21
• @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. – Dmitry Kamenetsky Sep 20 '19 at 4:27

Solution (not mine):

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.

• 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! – Dmitry Kamenetsky Sep 25 '19 at 6:15

Partial:

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:

If a solution exists, it will have to include a $$4\times 10$$ subconfiguration of the above, or similar.

• 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.) – hdsdv Sep 20 '19 at 8:08
• @hdsdv Not sure I understand: ROT13(gur cvtrbaubyr cevapvcyr qbrf abg nyybj lbh gb fnl fbzrguvat nobhg rnpu naq rirel 4k 10 fhopbasvthengvba). – Arnaud Mortier Sep 20 '19 at 8:44
• Lrf, ohg vs jr pna rahzrengr nyy 10k4 fbyhgvbaf, gura nal 4 pbyhzaf bs gur pbzcyrgrq tevq zhfg or bar bs gubfr 10k4 fbyhgvbaf. – hdsdv Sep 20 '19 at 8:49
• @hdsdv well, sure, but this is clearly not doable by hand, which was my intended purpose. – Arnaud Mortier Sep 20 '19 at 9:19
• @ArnaudMortier I just almost made 10x10 by hand, without one in corner. – Jan Ivan Sep 20 '19 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):

232311123123
313122123312
121233123231
113232312123
221313312312
332121312231
321123231123
213312231231
132231231312
211221333
322332111
133113222

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

• Yes a solution exists :) – Dmitry Kamenetsky Sep 20 '19 at 10:44