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?
2 Answers
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.
-
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 2RingJun 17, 2021 at 18:18
-
1$\begingroup$ Dmitry: a tessellation with a cross of St Brigid design. $\endgroup$– smciJun 17, 2021 at 22:19
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.
-
1$\begingroup$ Can you explain more the connection between the second and the third spoiler box? $\endgroup$– justhalfJun 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$– BubblerJun 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$– justhalfJun 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$– BubblerJun 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