Can You Spread The Squares?

Riddler Classic

This week, get ready to play a game of squares! You start with five shaded squares on an infinitely large grid, in the following formation:

This is generation 1. To go from one generation to the next, you consider every square’s eight neighbors (up, down, left, right and the four diagonal directions). If at least three of those squares are shaded, in the previous iteration, that square will be shaded in the next generation.

That said, here are the first four generations:

How many squares will be shaded in generation 10?

Extra credit: As N gets very, very large, approximately how many squares will be shaded in generation N (in terms of N)?

Solution

I created a simulation.

The table below provides some values.

Generation	New Squares	Total Squares
$1$	$5$	$5$
$2$	$4$	$9$
$3$	$4$	$13$
$4$	$8$	$21$
$5$	$8$	$29$
$6$	$8$	$37$
$7$	$12$	$49$
$8$	$12$	$61$
$9$	$12$	$73$
$10$	$16$	$89$
...	...	...
$N$	$4 \cdot \left\lceil\dfrac{N}{3}\right\rceil$	?

Answer

For $N = 10$, there are $89$ squares.

Extra Credit

It seems that after every generation $N$, where $N\equiv 0 \mod 3$, the number of new squares increases by 4.

Note that the difference between generations 6 and 3 is 24, between generations 9 and 6 is 36, between generations 12 and 9 is 48,...

Let $T(N)$ be the total number of squares of a generation. Using Triangular Numbers:
$$T(N) = 13 + 12 \cdot \left( \dfrac{\left(\dfrac{N}{3} + 1 \right)\cdot \dfrac{N}{3}}{2} - 1 \right)$$
$$T(N) = 13 + 2 \cdot \left(\dfrac{N}{3} + 1 \right)N - 12$$
$$T(N) = \dfrac{2N^2}{3} + 2N + 1$$
$$T(N) = \dfrac{2N^2 + 6N + 3}{3}$$

For $N\equiv 1 \mod 3$, the number of new squares increases from the previous iteration.

Thus:
$$T(N) = \dfrac{2(N-1)^2 + 6(N-1) + 3}{3} + \left(\dfrac{N-1}{3} + 1 \right)\cdot4$$
$$T(N) = \dfrac{(2N^2-4N+2) +(6N-6) +3}{3} + \dfrac{4N+8}{3}$$
$$T(N) = \dfrac{2N^2 + 6N +7}{3}$$

Similarly, for $N\equiv 2 \mod 3$:
$$T(N) = \dfrac{2(N-2)^2 + 6(N-2) + 3}{3} + \left(\dfrac{N-2}{3} + 1 \right)\cdot4\cdot2$$
$$T(N) = \dfrac{(2N^2-8N+8) +(6N-12) + 3}{3} + \dfrac{8N+8}{3}$$
$$T(N) = \dfrac{2N^2 + 6N + 7}{3}$$

I provided specific answers based off$\mod 3$, but as $N$ gets very large, the number of shaded squares is $\approx \dfrac{2N^2}{3}$.

Rohan Lewis

2022.01.30

Code can be found here.