6
$\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!

Improve this question
$\endgroup$
3
  • 7
    $\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 ♦
    Commented 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$
    – greenturtle3141
    Commented 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$
    – Dmitry Kamenetsky
    Commented Sep 20, 2019 at 4:27

3 Answers 3

Reset to default
5
$\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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Sep 25, 2019 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.

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes a solution exists :) $\endgroup$
    – Dmitry Kamenetsky
    Commented Sep 20, 2019 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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