Counting ant movements

Question

On a $2\times10$ horizontal grid, there are $10$ ants on the top row, one on each square. The bottom row is initially empty. When a bell sounds, each ant moves to a vertically or horizontally adjacent square, with the following restrictions:

• No ant can move outside the 2x10 grid
• Ants cannot collide, i.e. if an ant is going right, the ant to his right cannot go left. If an ant is going left, the ant to his left cannot go right.
• After the moves are complete, there can be no more than one ant on any square
• The bell only rings once, and all ants move simultaneously.

In how many ways can this be done?

Answer 1

If I understood the problem correctly, the ants have

3363 possibilities.

Reasoning:

Let the ant in the top-left move right. The ant to its right can only go right or down. If this ant chooses to go right, the next ant can only go right or down, and so on. This means we can split our ants into some groups of consecutive ants:

In a right-group, the ants go (from left to right) right, right, right, ..., down.
In a left-group, the ants go down, left, left, ..., left.

The ant on the top-left can belong to a group of any size, and that group can be a left or a right group. If we take care to notice that the left and right groups of size 1 are the same (one ant moving down) we get the recurrence relation:

$A(0) = 1$
$A(x) = A(x-1) + 2 [ A(x-2) + A(x-3) + ... + A(0) ]$

Evaluating this we get A from 0 to 10 being 1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363.

PS: Looking at the values, the recurrence can also be simplified to $A(x) = 2A(x-1) + A(x-2)$, although I don't know how to justify that other than by showing it's equivalent to the first one.

Answer 2

Justification for the simpler recursive formula in @ffao's answer:

Imagine that there is another empty column on the left. Let $A_L(x)$ be the number of ways where the first ant moves left, $A_D(x)$ the number of ways where the first ant moves down, and $A_R(x)$ where the first ant moves right. Then the original function $A(x)$ is equal to $A_D(x)+A_R(x)$, with $A_L$ excluded because the extra column isn't actually there.

Now if the first ant moves down or left, this is essentially the case for $x-1$ ants with an extra column, so $A_D(x)=A_L(x)=A(x-1)+A_L(x-1)$.

If the first ant moves right, then all the normal ways for $x-1$ ants are possible, except for those where the third ant moves left; these require that the second ant moved down, so they are only counted once. So $A_R(x)=A(x-1)-A_L(x-2)$.

Finally,$$A(x)=A_D(x)+A_R(x)\\=[A(x-1)+A_L(x-1)]+[A(x-1)-A_L(x-2)]\\=A(x-1)+[A(x-2)+A_L(x-2)]+A(x-1)-A_L(x-2)\\=2A(x-1)+A(x-2)$$as desired.

Answer 3

You can generalize this problem to a $2\times n$ grid, where ants on the top row move subject to the same rules. In general, the number of possible movements is $$ \sum_{k=0}^{n/2}\binom{n}{2k}2^k=\binom{n}02^0+\binom{n}22^1+\dots+\binom{n}{2\lfloor n/2\rfloor}2^{\lfloor n/2\rfloor} $$ I got the inspiration for this proof from ffao's answer, where it is noted that any coordination of ant movements breaks into consecutive blocks where a series of ants all move the same direction.

We can specify a way to move all the ants in the following fashion:

• Choose a number $k$, where $0\le k\le n/2$.

• Choose a subset of $2k$ of the ants. Number them $a_1,a_2,\dots,a_{2k}$ from left to right. For all $1\le i\le k$, let $B_i$ be the set of ants between $a_{2i-1}$ and $a_{2i}$, inclusive.

• For each $1\le i\le k$, choose a direction Left or Right. If Left is chosen, then all ants in $B_i$ move left, except the leftmost ant $a_{2i-1}$ moves down. Similarly, if Right is chosen, all but the rightmost ants move right.

• All other ants move down.

The number of ways to carry out the above algorithm is exactly counted by the displayed formula.