# 5x5 binary grid with every 2x2 sub-grid occurring once

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?

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.

• Correct and well done! This is also known as De Bruijn Torus. Jun 17 '21 at 6:48
• Here's an SVG version of the torus pattern, repeated. Jun 17 '21 at 18:18
• Dmitry: a tessellation with a cross of St Brigid design.
– smci
Jun 17 '21 at 22:19

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.

• Can you explain more the connection between the second and the third spoiler box? Jun 17 '21 at 5:25
• @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. Jun 17 '21 at 6:01
• 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)? Jun 17 '21 at 6:06
• @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. Jun 17 '21 at 6:14
• Correct answer. I accepted Jaap's solution for the extra torus connection. Jun 17 '21 at 6:48