5
$\begingroup$

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!

$\endgroup$
  • 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 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$ – greenturtle3141 Sep 20 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$ – Dmitry Kamenetsky Sep 20 at 4:27
4
$\begingroup$

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.

$\endgroup$
  • $\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$ – Dmitry Kamenetsky Sep 25 at 6:15
2
$\begingroup$

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:
enter image description here
If a solution exists, it will have to include a $4\times 10$ subconfiguration of the above, or similar.

$\endgroup$
  • $\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 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$ – Arnaud Mortier Sep 20 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 at 8:49
  • $\begingroup$ @hdsdv well, sure, but this is clearly not doable by hand, which was my intended purpose. $\endgroup$ – Arnaud Mortier Sep 20 at 9:19
  • 2
    $\begingroup$ @ArnaudMortier I just almost made 10x10 by hand, without one in corner. $\endgroup$ – Jan Ivan Sep 20 at 9:38
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes a solution exists :) $\endgroup$ – Dmitry Kamenetsky Sep 20 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.