Problem: Particles on a Polygon

I recently gave a talk to a group of maths students. These days, I like to use puzzles to break up the monotony, so I presented them with this one:

Have a little think about it first before I reveal the answer.

OK, are you done thinking? No? Then don’t read anymore until you’ve given it a good crack.

If you’re reading this sentence, I assume you’re ready for a solution. So here it is.

We are trying to find the Expected Time E that it takes for the two particles to collide.

We note that there is a 25% chance that the two particles meet after one second. This is when the leftmost particle moves to its right and the rightmost particle moves up to its left.

Note that any other outcome will result in the two particles being exactly two spaces apart from each other on the hexagon. And this is the same as the starting position. So there is a 75% chance that nothing really changes.

This allows us to write the following equation.

E = 0.25 \times 1 + 0.75 \times (1 + E)

Think really carefully about what the above says. It says that there is a 25% chance that it takes 1 second or a 75% chance that after 1 second nothing has changed.

It’s a neat little bit of recursion and it gives us an equation that is pretty easy to solve! If you do this you will find that E = 4.

Let’s generalise this. We looked at the expected meeting time of two particles on a 6-sided shape where the particles are originally 2 lengths away from each other. We could easily generalise the number of sides of the polygon and how far away the particles are to begin with.

Denote by E_{n,k} the expected meeting time of two particles on an n-sided polygon given that they start k lengths away from each other.

So, in this language, what we showed earlier is that E_{6,2} = 4.

Note that we will assume n and k are even, otherwise we might find the particles meeting each other between two vertices.

Alright, here are some problems for you!

Problem 1. Find E_{4, 2}.

Problem 2. Find E_{8, 4}.

Hint: write down a recursive equation for E_{8,2} first and then combine with a recursive equation for E_{8,4}.

Problem 3. Find an asymptotic formula for E_{4n, 2n} as n \rightarrow \infty.

One comment

Leave a Reply

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

You are commenting using your 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 )

Connecting to %s