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

For Q3 here’s (what I believe) is a nice little close form solution https://imgur.com/a/E1e2IlH

I’ve omitted the calculation and proof of e_j’s geometric series but writing the first few terms should demonstrate the general idea. I also simplified 4(1/2)^{j+1} as (1/2)^{j-1}

LikeLike