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?

Advertisements

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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: