7
$\begingroup$

Can you paint a $5 \times 5$ grid in two colors, such that each of the $2 \times 2$ possible sub-grids ($2^4 = 16$ combinations) occurs exactly once in the grid?

$\endgroup$
0

2 Answers 2

8
$\begingroup$

It is also possible to do this on a 4x4 torus grid (i.e. a 4x4 with wrap-around edges). This gives the solution:

0 0 0 1
0 0 1 0
1 0 1 1
0 1 1 1

As a 5x5 solution (just making the 5th row/column a copy of the 1st) this becomes

0 0 0 1 0
0 0 1 0 0
1 0 1 1 1
0 1 1 1 0
0 0 0 1 0

Of course

you can cyclically rotate the rows and/or columns of the 4x4 grid to get equivalent solutions which will look different from each other when shown as a 5x5 grid.

$\endgroup$
3
  • 2
    $\begingroup$ Correct and well done! This is also known as De Bruijn Torus. $\endgroup$ Jun 17, 2021 at 6:48
  • 3
    $\begingroup$ Here's an SVG version of the torus pattern, repeated. $\endgroup$
    – PM 2Ring
    Jun 17, 2021 at 18:18
  • 1
    $\begingroup$ Dmitry: a tessellation with a cross of St Brigid design. $\endgroup$
    – smci
    Jun 17, 2021 at 22:19
5
$\begingroup$

The short answer is:

Yes, with one possible solution being the following:

0 0 1 1 0
0 0 1 1 0
1 0 0 1 1
0 0 1 1 0
1 1 0 0 1

If we list out all the possible subgrids in the 4×4 layout, it looks like this:

0 0   0 0   0 0   0 0
0 0   0 1   1 0   1 1

0 1   0 1   0 1   0 1
0 0   0 1   1 0   1 1

1 0   1 0   1 0   1 0
0 0   0 1   1 0   1 1

1 1   1 1   1 1   1 1
0 0   0 1   1 0   1 1

Then each tile goes to the corresponding row number as shown below:

1 3 2 4
2 1 4 3
3 4 1 2
4 2 3 1

which is a

Latin square.

$\endgroup$
6
  • 1
    $\begingroup$ Can you explain more the connection between the second and the third spoiler box? $\endgroup$
    – justhalf
    Jun 17, 2021 at 5:25
  • $\begingroup$ @justhalf The first row in the main answer contains four tiles (in the second box) labeled 1 (in the third box), the second row contains those labeled 2, and so on. $\endgroup$
    – Bubbler
    Jun 17, 2021 at 6:01
  • $\begingroup$ Ah, I see. But what about the order within each row? Seems quite arbitrary to me. It's not column-wise, and it's not by traversing the 4x4 grid in order. So seems like this is not a path to the solution, but just a nice observable properties of which tiles went where in a solution you found previously (perhaps via trial and error)? $\endgroup$
    – justhalf
    Jun 17, 2021 at 6:06
  • 2
    $\begingroup$ @justhalf I just went row-by-row, spending four tiles at once. I randomly picked the tiles that would go to the first row (those just looked nice), and looking at the diagonal crossed out I immediately thought "oh, looks like a Latin square pattern might work", and it simply did (I didn't have to backtrack at all). The column order in each row happens to be some cyclic shift of 1 2 4 3. $\endgroup$
    – Bubbler
    Jun 17, 2021 at 6:14
  • 1
    $\begingroup$ Correct answer. I accepted Jaap's solution for the extra torus connection. $\endgroup$ Jun 17, 2021 at 6:48

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.