# When will the matrix turn to black?

For the following pattern of filling the $5*5$ matrix, how many steps does it take to turn all cells of the matrix to black? The first piece moves to the right, the second moves down, the third moves left, the fourth moves up, and so the fifth probably moves right. The letters and numbers are the sum of X and Y coordinates respectively, with the upper left corner being coordinate $(1,1)$ or $(A,1)$. Each image introduce its new element at the position given by the coordinate sum of the previous image. Both movement and new positions wrap around, so when a piece would move over the border it appears next to the opposite border, similarly a piece that appear at for instance $(H,11)=(8,11)$, will wrap around to $(8mod5,11mod5)=(3,1)=(C,1)$.

I guess after some steps next pointed cell that need to be colored, may not be white.

PS. Question is much like one of my previously made questions: Find the pattern of matrices.

• 24? Maybe? Anyone wanna prove this? – warspyking Oct 16 '14 at 16:46
• But cells with a different directions collide, will they both co-exist? I mean will they both become 2 cells when they go in different directions or will one of them "merge" into the other – skv Oct 17 '14 at 5:19
• they wont merge. they will be override only in one step – Rafe Oct 17 '14 at 14:51

Here's an alternate interpretation. Like @Florian, I assume that two black squares can share the same position, and in then next step they will continue their independent paths. However, in the description of the pattern:

"Each image introduce its new element at the position given by the coordinate sum of the previous image"

I interpret this to mean that you count which squares have something covering them rather than the position of the squares that are doing the covering. In other words, overlapping squares only count once for the purpose of determining the position of the new square. This throws off the pattern discovered by Florian, and makes it possible to get enough squares in different positions to eventually cover the grid.

Rather than figure it all out by hand, I used the following Python code to figure it out for me:

dirs = [(1,0),(0,1),(-1,0),(0,-1)] #Which direction the squares move in
spots = [(2,2),(4,3)] #The two initial squares

while len(set(spots)) < 25 and len(spots) < 100:
newspot = tuple(map(lambda x: (sum(x)-1)%5+1, zip(*set(spots))))
spots = [tuple(map(lambda x: (sum(x)-1)%5+1, zip(spot, dirs[i%4]))) for i, spot in enumerate(spots)]
spots.append(newspot)

print len(spots)
# Prints out 61


I verified that this correctly simulates the first four steps, so I'm quite confident that under this interpretation it will take 61 total squares to completely cover the grid (i.e 59 steps after the initial setup of two squares).

It will never turn black.

I assume that black squares can superpose on the same position. They will cross, each following its own direction.

What happens is that the 23rd square falls exactly on the position of the 3rd one, and it moves in the same direction. The 24th square then falls exactly on the position of the 4th, and again moves in the same direction. In fact, from the 23rd on, all squares superpose with the square created 20 steps before.

The reason is that new squares are generated according to the sum of all coordinates. These coordinates move. But every group of 4 consecutive squares moves in all 4 directions, so that their movements compensate. The sum of the 4 successive coordinates remains constant. And it happens that 5 such groups sum up to 0. That means that you can forget the last 20 squares, you still get the same result. And therefore the squares are generated exactly like 20 squares before. The generation repeats an endless cycle of size 20. In fact 20 is 4x5, 4 is the number of directions, 5 is the size of the board.

The result is that only the 22 first squares count. The following only superpose on existing squares. So there are never more than 22 squares covered at any time on the board.

• I just verified this with a simulation. Nice work! – Rob Watts Oct 18 '14 at 2:48