16
$\begingroup$

Colour in a 5 by 5 grid using the colours Red, Blue, Green and Yellow.

Each cell is considered to have 4 neighbours (to the left, right, above and below.) The grid wraps, so e.g. the top right is a neighbour of the bottom right and top left.

Produce a new grid as follows: if a cell is surrounded by 4 of the same colour, it turns (or remains) Red; if surrounded by 3 of the same colour and one different, it turns Blue; if surrounded by 2 of the same colour and any two other colours (e.g. G, G, R, Y or B, B, R, R) it turns Green; and if surrounded by 4 different colours, it turns Yellow.

Colour puzzle example

Question: other than a grid that's coloured all red, is it possible to colour a grid so that the output, i.e. the grid that gets produced after one iteration, is identical to the starting grid? (You don't have to use all of the colours.) And, if not, can you prove that this is impossible?

I don't know the answer to this question, but after having spent some time trying to solve, I suspect it is impossible. (Hopefully I didn't miss something really obvious...) I'm hoping someone can supply a proof!

$\endgroup$
3
  • $\begingroup$ I'm curious how this arose. Is it a pure puzzle, or did it grow out of some interesting research? $\endgroup$ May 24 at 14:40
  • 1
    $\begingroup$ @Scott Sauyet I made this puzzle: reddit.com/r/PictureGame/comments/tfzsux/… for r/picturegame on Reddit and then this one is another variant in the same genre. However I couldn't post it on Picture Game as I didn't have a solution! So it's a pure puzzle. $\endgroup$
    – R1s1ble
    May 24 at 15:28
  • $\begingroup$ I guess there would $4^5^2 = 1125899906842624$ possible grids. $\endgroup$
    – Galen
    May 24 at 16:24

2 Answers 2

16
$\begingroup$

Found a Solution

All the blue squares border 3 blue squares and 1 red square and all the red squares border 4 blue squares.

$\endgroup$
6
  • 1
    $\begingroup$ Nicely done! I puzzled for some time and never hit on this solution. $\endgroup$
    – R1s1ble
    May 22 at 23:53
  • $\begingroup$ I'm also pretty sure this is the only solution beyond the all-red solution. Haven't been able to prove it though. I have managed to figure out that yellow can't be anywhere in a valid solution. Edit: Beyond trivial rotations of this one. $\endgroup$ May 23 at 1:45
  • $\begingroup$ With MIP, I confirm there is no 3-color or 4-color solution. $\endgroup$
    – xd y
    May 23 at 8:13
  • 4
    $\begingroup$ I did a quick brute force search, and the three kinds of solution so far (this one, Magma's solution, and the all-red solution) are the only ones up to rotation/reflection/translation. $\endgroup$ May 23 at 10:12
  • 1
    $\begingroup$ @iBug It's on a torus, so you can cyclically shift everything (e.g. move everything down a row and put the bottom row on the top, or similarly with the columns). $\endgroup$ May 23 at 10:53
17
$\begingroup$

Here's one more solution that isn't the all-red one:

green on a zigzag path repeating two right one down, blue otherwise

$\endgroup$
0

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.