Posted by: anthonygenello | October 27, 2008

## Course-related interview question about an ant

Since I’ve been preparing for finance interview-type questions lately, I thought I’d invent one related to our course. Then I tried to solve it. Hopefully I’m right. Here it goes:

Part 1: This is a question about polygons and an ant. Suppose a 2 dimensional ant is placed on the side of a regular polygon whose center of gravity is inside the polygon (so the ant won’t fall off if he walks around the perimeter). Also suppose that the ant walks to a side of the polygon which is adjacent to his starting side. He immediately forgets where he started from and can walk either forwards to the next side or backwards to the other adjacent side. Suppose that it takes the ant one minute exactly to move from adjacent side to side (i.e. it would take him at least 4 minutes to circumnavigate a square). In each minute following the time the ant becomes lost, he must walk either forward a side or backward a side along the perimeter of the polygon. The movements are random such that there is an equal chance that he will walk to either adjacent side. What is the expected amount of time it takes for the ant to find his way back to the starting side after he first becomes lost?

Solution: This is really a question about random walks and recursion. It’s easiest to understand how to solve by using the triangle as an example. So the ant is one side away from his starting side of the triangle. He can either walk backwards to where he started in one minute or forward in one minute. If he walks forward, he will still be one side away from where he started. Thus we are faced with the same problem over again. We can represent this recursion with an equation:

E = 0.5(1) + 0.5(1 + E)

E = 2

Thus, we expect the ant to take 2 minutes in order to find his way back. If he were on a square, we would expect him to take 3 minutes. For a pentagon – 4 minutes. That’s how the simple cases worked out for me. I suspect that for an n-gon we expect the ant to take n-1 minutes to find his way back. I couldn’t figure out how to prove. I’d be impressed if someone could.

Part 2: Same as part one, but for the tetrahedron, cube, octahedron, dodecahedron, and icosahedron.

Solution: The methodology is the same as in part 1, but now we’re dealing with 3-D. Here were my answers:

Tetrahedron: 3 minutes

Cube: 5 minutes

Octahedron: 7 minutes

Dodecahedron: 11 minutes

Icosahedron: 19 minutes

Hey, they’re all integers, and prime at that! Can someone check this?

## Responses

1. I really like this puzzle. Here’s a general proof for the polygon.

Let’s generalise the problem to label the sides $0, 1, .... , n$. Then if the ant starts on side $k$, we’ll call the expected number of steps to get to side 0 by the name $E_k$. So $E_1$ is what this problem asks for. Now, slightly generalising what we saw in the post, we have the relationship

$E_k = 1/2 (E_{k-1}) + 1/2 (E_{k+1}) + 1$

Rearranging this, we get a recurrence relation

$E_{k+1} = 2( E_{k} ) - E_{k-1} - 2$

We can also say that $E_0 = 0$, since the ant is already on side 0 if he starts there.

If we give $E_1$ the variable name $x$, then we can calculate the first few terms of the sequence using the recurrence relation:

$0,x,2x-2, 3x-6, 4x-12, 5x - 20, \ldots$

We can look at the pattern and conjecture that the $k$-th term is

$kx - k(k-1).$

We can verify this conjecture by induction. (How did I know it? I am just very familiar with the sequence 1,3,6,10,…)

Ok, but so far we haven’t used the fact that the polygon has $n$ sides. There are various ways to throw this into the mix. We could say that

$nx - n(n-1) = 0$

since we know $E_n = 0$ (the n-th side is the same as the 0-th side since the polygon has n sides).

Then, we can solve for $x$ and get

$E_1 = x = n-1.$

Does anyone have a simpler proof? I think there must be a simpler one out there.