Multiplying ducks on a 3d grid

Question

There is a 3-dimensional grid (semi-infinite in all the three directions). Each cell of the grid contains at most one duck. You are allowed to remove a duck from a cell, but only if the cell above it, the cell to the right of it, and the cell in front of it are all empty. If you do remove a duck from a cell, you must place three ducks, one in each of the three empty cells mentioned before.

Initially, there is only one duck in the grid at the bottommost, leftmost, backmost cell. Can you empty the cells shown in the picture (including the hidden cells behind them) in finitely many moves?

---

Source: inspired by this math.SE post.

Answer 1

Given any configuration of ducks in the grid,

assign it a score by summing over all occupied cells the value $3^{-n}$, where $n$ is the Manhattan distance of the cell to the initial corner cell.

We can make four key observations:

1. The initial score is $3^{-0}=1$.

2. The score is invariant: replacing a duck scoring $3^{-n}$ with $3$ ducks each scoring $3^{-(n+1)}$ does not change the total score.

3. The total possible score of all cells in the grid is$$\begin{align}\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{k=0}^\infty3^{-(i+j+k)}&=\sum_{i=0}^\infty3^{-i}\sum_{j=0}^\infty3^{-j}\sum_{k=0}^\infty3^{-k}\\&=\left(\sum_{i=0}^\infty3^{-i}\right)^3\\&=\left(\frac1{1-3^{-1}}\right)^3\\&=\frac{27}8.\end{align}$$

4. The total possible score of the cells shown is $1\cdot3^{-0}+3\cdot3^{-1}+6\cdot3^{-2}=\frac83$.

Based on these observations,

the score of any configuration in which the cells shown are all empty is at most $\frac{27}8-\frac83=\frac{17}{24}<1$, so it is impossible to empty the cells shown starting with the initial duck.

Answer 2

First, we assign a "weight" to each cell

of $\frac{1}{3^d}$, where $d$ is the cell's Manhattan distance from the bottom-left-back corner.

Moving a duck from a cell with distance $k$, and therefore weight $1/3^k$, will result in three cells with distance $k+1$ and weight $1/3^{k+1}$, so the total weight is preserved under moving ducks.

Initially, we have $1$ unit of weight. So, to move all ducks outside the given area, we need to

find a set of cells outside the given area whose weights sum to 1. For all the cells at any given distance $k$, we have $k+1$ cells in a diagonal line on the bottom layer, $k$ cells on the second layer, and eventually $1$ cell on the $k+1$th layer. So, the number of cells with distance $k$ is $$ 1 + 2 + ... + k + (k+1) = \sum_{i=0}^{k+1} i = \frac{(k+1)(k+2)}{2}$$ And their total weight is $ \frac{(k+1)(k+2)}{2 \cdot 3^k} $, so the total weight of all cells outside the given area is $$ \frac{10}{3^3} + \frac{15}{3^4} + \frac{21}{3^5} + \frac{28}{3^6} + ... = \sum_{i=3}^{\infty} \frac{(i+1)(i+2)}{2 \cdot 3^i}$$ And to move to move the entire weight of $1$ outside the given region, this sum needs to be larger than $1$.

Now, some algebra:

The ratio of two consecutive terms is $ \lim_{i\to\infty} \frac{\frac{(i+1)(i+2)}{2 \cdot 3^i}}{\frac{(i)(i+1)}{2 \cdot 3^(i-1)}} = \lim_{i\to\infty} \frac{i+2}{3i} = \lim_{i\to\infty} \frac{1}{3}+\frac{2}{3i} = \frac{1}{3}$ which is less than $1$ so by the ratio test this sequence converges to some sum $S$. Now, let $$ S = \sum_{i=3}^{\infty} \frac{(i+1)(i+2)}{2 \cdot 3^i} = 3 \sum_{i=3}^{\infty} \frac{(i+1)(i+2)}{2 \cdot 3^{i+1}} = 3 \sum_{i=4}^{\infty} \frac{i(i+1)}{2 \cdot 3^i} = \\ 3 \sum_{i=4}^{\infty} \frac{(i+2)(i+1) - 2(i+1)}{2 \cdot 3^i} = 3 \left(S - \frac{10}{27} - \sum_{i=4}^{\infty} \frac{i}{3^i} - \sum_{i=4}^{\infty} \frac{1}{3^i}\right) = 3\left(S - \frac{10}{27} - \frac{1}{12} - \frac{1}{54}\right) = 3 S - \frac{17}{12} \implies 2 S = \frac{17}{12} \implies S = \frac{17}{24} < 1 $$ So the weight outside the given area is less than 1 and it's impossible to clear the area of ducks.