# Counting ant movements

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?

• yep, correcting it now. it should be 2x10 – astralfenix Apr 11 '16 at 14:28
• The bell rings once and all ants move simultaneously, yes? – Ian MacDonald Apr 11 '16 at 14:29
• Can an ant choose not to move? – Trenin Apr 11 '16 at 15:07
• They can't move diagonally and can only move one square – astralfenix Apr 11 '16 at 15:07
• @Trenin each ant must move. – astralfenix Apr 11 '16 at 15:13

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.

• Your function $A(n)$ has a closed form solution of $\frac{(1+\sqrt2)^n+(1-\sqrt{2})^n}{2}$, which can further simplified to $\sum_{k=0}^{n/2}\binom{n}{2k}2^k$. Not sure if the last formula offers any insight to the original problem. – Mike Earnest Apr 11 '16 at 16:57
• $A(x)=A(x-1)+2[A(x-2)+A(x-3)+\ldots]=A(x-1)+A(x-2)+A(x-2)+2[A(x-3)+\ldots]=A(x-1)+A(x-2)+A(x-1)$ – f'' Apr 11 '16 at 17:19

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.

• This is the elegant solution =D – justhalf Apr 21 '16 at 9:15

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.