Amoebas in a 2D Grid

Consider a two dimensional grid of squares. The grid has 4 rows but infinitely many columns.
An amoeba in square $(x, y)$ can divide itself into two amoebas to occupy the squares $(x+1,y)$ and $(x+1,(y+1) \bmod 4)$, provided these squares are empty.
The following diagrams show two cases of an amoeba placed in square A of each grid. When it divides, it is replaced with two amoebas, one at each of the squares marked with B:

Originally there is only one amoeba in the square $(0, 0)$. After $N$ divisions there will be $N+1$ amoebas arranged in the grid. An arrangement may be reached in several different ways but it is only counted once. Let $C(N)$ be the number of different possible arrangements after $N$ divisions.
For example, $C(2) = 2$, $C(10) = 1301$, $C(20)=5895236$ and the last nine digits of $C(100)$ are $125923036$.
Find $C(100\,000)$, enter the last nine digits as your answer.

This is a problem involving dynamic programming and combinatorics. The main idea here is to count all possible legal arrangements of amoebas.

This problem involves modulo operation. Let’s define this: we often consider the problem in modulo $10^9$. This basically means we only care about the last nine digits of the answer.

One way to approach this problem is to store the states involved and derive a recursive formula to calculate the number of positions. $f(N, i, s_1, s_2, s_3, s_4)$ is the number of ways to place amoebas in a $N \times 4$ grid with the $i-th$ column be $s_i$, where $s_i$ is a binary number indicating the ith column.

# The iterative version of the dynamic programing solution is:

““
f[N+1, i, s_1, s_2, s_3, s_4] += f[N, i, s1, s2, s3, s4]
““

# if i-th cell in the first row is 0 (empty), and the $s_1$ is blocked in the next 3 rows in the i-th column:
““
f[N+1, i, s_1+2^(i-2), s_2+2^(i-1), s_3+2^i, s_4] += f[N, i, s1, s2, s3, s4]
““
# if i-th cell in the first row is 0 (empty) and the $s_1$ is blocked in the lower row (blocked means occupied by an amoeba):
““
f[N+1, i, s_1+2^(i-2), s_2, s_3, s_4] += f[N, i, s1, s2, s3, s4]
““
Finally, we obtain the state-transition function. With this function and the initial condition: $f[0, 0, 0, 0, 0, 1]$ , we can calculate $C(100,000)$ iteratively.
Please note that you need a high-performance computer and efficient program implementation to actually run this algorithm. It most likely cannot be solved by hand!

Keep in mind that this problem is a combinatorial problem from a mathematics competition and uses advanced problem-solving techniques, such as dynamic programming, that are typically taught in upper-level computer science and mathematics courses. It is not representative of typical high school mathematics curriculum.

More Answers: