Math puzzle: chances of meeting up with a friend (and game theory puzzle extension)

Some nights that I go out to the bars it seems like I end up running into everyone. Other nights it’s the exact opposite where I get out of sync and miss meeting my friends.

The dynamics of meeting friends is rather interesting, and here is a probability puzzle that captures some of that essence.

On a Friday night, two friends agree to meet up in a bar between midnight and 1 am. Each forgets the exact time they are supposed to meet, so each shows up at a random time.

Suppose that after arriving randomly, each waits 10 minutes for the other person before leaving. What is the chance the two will meet at the bar?

Can you solve it?

I’ve covered a lot of math puzzles recently, and I have to say I had a lot of fun solving this one . There is some fascinating math which I will explain in the various solution methods presented below.

Give it a try before reading on.

I should also mention there is an interesting game theory extension to the question. This is an independent problem that you can also try to solve.

Game theory extension

If both friends are rational, and they want to maximize the chance of meeting the other, what strategy should each pursue? If they play optimally, what is the chance they will meet each other? (Assume each person is aware the other will wait 10 minutes before leaving.)

In a sense, this part of the puzzle is more practical. It can be attacked using logical thinking and the result tremendously surprising.

Even if you are not interested in math, I highly suggest you read the section Game theory solution.

When you are ready, read the rest of this article for the solutions.

Solution method 1: geometric probability

I feel this is the most elegant way to solve the problem.

If we let x denote the time one person arrives at the bar, and y the other, we can use the notation (x, y) to denote the time in minutes, after midnight, that each person arrives at the bar.

The trick now is that we can model the situation geometrically in the Cartesian plane. The x-axis can be labeled from the time 0 minutes until 60 minutes, as can the y-axis.

Now any coordinate in the 60×60 square represents a time that the pair arrives at the bar. The coordinate (0,9) means one person shows up at midnight, the second at 12:09, and clearly they will meet because the times are within 10 minutes of each other. The coordinate (1, 51), on the other hand, corresponds to one showing up at 12:01 and the other at 12:51, a time the two will not meet.

What is the set of coordinates for which the two will meet?

The notation affords a very simple way to describe the event. We want the two coordinates to be within 10 minutes of each other. We either want the x coordinate to be 10 units smaller than y, or 10 units bigger than y. The succinct way of writing that is we want all coordinates such that | x – y | ≤ 10.

We will draw the lines y = x – 10 and y = x + 10 and shade the area in between these two lines to denote the event.

The resulting figure is as follows:

The probability of meeting is precisely the ratio of the shaded area to the total square.

This is fairly easy to calculate. The big square is 60×60 = 3,600 in area. Rather than finding the shaded area, let us calculate the unshaded area and subtract. The unshaded area consists of two isosceles right triangles with sides of 50. This means each triangle has an area of (0.5) x (50×50) = 1,250 and the total unshaded area is double that, 2,500.

The shaded area is found by subtracting the unshaded area from the total : 1,100 = 3,600 – 2,500.

Thus we conclude the chance the friends will meet is 1,100 / 3,600 = 11/36, or about 30.6 percent.

Having nearly a one in three chance to meet is actually not that bad!

I find the geometric solution to be the most elegant, but it should not surprise you there are other ways to solve this puzzle.

Later in the article I will explain two other solution methods.

For now, I want to highlight another interesting fact. The math shows that even two mindless friends have a rather good chance of meeting up with each other.

In the game theory extension, I asked how likely it would be if the friends were completely rational and reasoned carefully. The surprising thing is the friends, if they reason carefully, are guaranteed to meet!

Here is why.

Game theory solution

I credit my aunt for offering a strategic answer to this mathematical problem, inspiring this extension.

In the real world, people don’t show up randomly. They will use some heuristics and reason out a strategy to increase the chances of meeting their friend.

I’ve asked this puzzle to many people, and their reactions are quite interesting. The first thing that people notice is that it’s a bad idea to show up too early or too late. Why is that?

You probably figured this logic out when solving the puzzle. If you show up right at midnight, you will only win if your friend ends up showing up after you. If you show up somewhere in the middle, you win if your friend shows up 10 minutes or less after you AND if your friend had happened to show up 10 minutes or less before you.

Similarly, you can reason it’s a bad idea to show up at 1 am or near the end, in which case you win only if your friend showed up before you.

So which times are not good strategies? Let’s be specific and list the out.

Dominated strategies

One time that is very stupid to show up is right at midnight. You will only win if your friend shows up during the first ten minutes–we can denote this as the interval [0, 10] for shorthand.

Rather than showing up right at midnight, you would do better to show up at 12:01. In this case you still win if your friend shows up at midnight, as he will be waiting for you. But you will also win if he shows up any time before 12:11. In short, that means you win if he shows up during the first 11 minutes of the night–corresponding to the interval [0,11].

Notice that by picking 12:01 instead of 12:00 exactly, you’ve increased your chances of meeting without sacrificing anything–you get an extra minute of time you will meet.

This argument shows that 12:00 is not a good strategy–it performs worse than 12:01 REGARDLESS of when the other person shows up.

We casually say arriving at 12:00 is a stupid idea. In game theory jargon, such a stupid strategy is dubbed as a dominated strategy.

(Note: it is vital that each person is aware the other person will wait 10 minutes before leaving–the rules of the game should be common knowledge)

Elimination of dominated strategies

Obviously dominated strategies should never be played. They perform worse than some other strategy, and hence they can be removed from consideration.

The above logic showed that 12:00 was dominated by 12:01. We can similarly show that 12:01 is dominated by 12:02, and in fact we can ultimately prove that showing up any time before 12:10 is a bad idea.

By exactly symmetric reasoning, we can prove that showing up any time after 12:50 is a dominated strategy. You are better off coming just a bit earlier to increase your odds of meeting up.

So that leaves us with the 40 minute interval from 12:10 to 12:50 in which both players could arrive.

If we assume the players show up randomly in this interval, then we can use a geometric argument as in Solution 1 above to find the probability of meeting jumps up to 7/16 = 43.75 percent.

But can the players do even better?

In fact they can! Here is why.

ITERATED elimination of dominated strategies

Surely the friends have reasoned this far, they are not going to stop thinking now.

We can continue to apply the same logic as before to try to trim the scope of good strategies. I have talked about iterated elmination of dominated strategies before, so check out this post about beauty contests for an introduction.

I will go through the reasoning again for the sake of completeness.

Remember we argued that 12:00 was a bad time to show up because it was the earliest possible time. So we concluded it was never a good idea to show up before 12:10.

That means in this reduced game that 12:10 is now the earliest time either friend would ever show up. Both friends should realize this, and we can repeat or iterate the logic again! The logical process is known as the mouthful iterated elimination of dominated strategies.

Basically 12:10 in this reduced game is very similar to 12:00 in the original game. Since no person shows up before this time, you only win if a friend shows up after you. It would make more sense to choose 12:11 to increase your chances of meeting your friend.

You are probably getting the idea, so I’ll skip a few steps and get to the end result.

In the reduced game, we can prove that showing up any time before 12:20 is a bad idea. Similarly, we can prove that showing up any time after 12:40 is a bad idea.

By iterating the process of removing bad strategies, we have derived a smaller strategy space and come up with a sharper prediction of play.

The solution: iterate one more time

Notice we are down to a 20 minute interval of time from 12:20 until 12:40. There’s no reason to stop here–let’s iterate the decision process one more time to see if we can get any better.

In this reduced game, the earliest time one of the players will show up is 12:20. Again, we can demonstrate it’s a bad idea to show up too close to the starting point of the interval. Using the same logic as before, we can see it is best to show up only at 12:30 or later.

Using similar logic, the latest time a friend will show up is 12:40. You can see what’s coming here: we can reason that it’s never a good idea to show up at 12:30 or later.

Putting these two facts together, we end up with a remarkable conclusion: 12:30 is the unique arrival time (i.e. Nash equilibrium) that the friends will show up!

This solution is absolutely marvelous to me, and it even has a few other interesting properties:

–this is an efficient time, as wait time is ZERO

–showing up at the middle is an obvious point (known in game theory as a focal or Schelling point)

–the friends are GUARANTEED to meet up: probability of meeting is 100 percent

So two friends who are reasonable enough to think can figure out how to meet for sure without relying at all on cell phones. You can see why the world of game theory is so seductively attractive to thinking people.

I feel the fact that people cannot arrive at similar success in the real world says something about the human condition.

But anyway, let me get to some other mathematical solutions to the non-game theory version. I find these are also very satisfying.

(Extra credit: The logic is not only for 10 minutes. This would also apply for 1 minute. In fact, you can show that if each person waits for any time ε > 0, then the unique equilibrium strategy is arrive at 12:30, leading to the outcome both people meet)

Method 2: Conditional probability

My uncle came upon this analytic solution. For narration sake, I will give a less than formal explanation–I am sure you can fill in the details.

Let’s consider the game from one friend’s perspective. We know the other player can show up at any time on the interval (remember in the non-game theory version any time is possible).

How likely are we to meet the other player? We can split up the cases in terms of conditional probability.

Case 1: If the other person shows up in the first 10 minutes (10/60 = 1/6 of the time), the average time of showing up is 12:05. We will meet if I show up any time from 12:00 to 12:15. This interval is 15 minutes out of 60, or 1/4 of the time.

Case 2: Similarly, if the other person shows up in the last 10 minutes (10/60 = 1/6 of the time), the average time of showing up is 12:55. We will meet if I show up any time from 12:45 to 1:00. This interval is 15 minutes out of 60, or 1/4 of the time.

Case 3: Finally, if the person shows up in the middle 40 minutes (40/60 = 2/3 of the time), the average time of showing up is 12:30. We will meet if I show up any time from 12:20 until 12:40. This interval is 20 minutes out of 60, or 1/3 of the time.

These three cases cover the various conditional events. We can thus compute the probability of meeting as:

Pr(meeting) = Pr(Case 1) * Pr(meeting in Case 1) + Pr(Case 2) * Pr(meeting in Case 2) + Pr(Case 3) * Pr(meeting in Case 3)

Pr(meeting) = (1/6)(1/4) + (2/3)(1/3) + (1/6)(1/4) = 11/36

Again, we arrive at the same solution of 11/36.

Method 3: Combinatorics

This is a solution I came upon when I was considering the practical implications of the geometric solution above.

I loved how elegant the geometric solution was, but the fact that time had to be continuous was something odd to me. I mean it is possible to show up at 12:33 and 1.14159 seconds, but who keeps track of time that accurately? And would you really be able to leave exactly 10 minutes later at 12:43 with 1.14159 seconds?

No, in the real world we are going to do some rounding, probably to the level of minutes.

So I set up a combinatorial problem as follows. Suppose each player can pick one of the minutes to arrive randomly from 0, 1, 2, …, 60, and each person waits 10 minutes for the other person. What is the chance they will meet then?

This is a discrete version of the continuous geometric problem, so let’s solve it.

Solution to discrete problem in minutes

We can proceed simply by counting the number of pairs (x, y) such that |x – y| ≤ 10 as in the continuous case.

For simplicity, let’s consider the perspective of the person showing up first and count the number of integers the other person can arrive after. This will count half the cases, and we can double the result to count all cases.

–If the first person picks 0, then the person arriving second can pick times 0, 1, 2, …, 10–there are 11 times corresponding to 0

–If one person picks 1, then the person arriving second can pick times 1, 2, …, 11–there are 11 times corresponding to 1

–If the first person picks anything from 2 to 50, there will be 11 possible times for the person arriving second

–If the first person picks 51, the person arriving second can pick 51, 52, … 60, or 10 cases

–If the first person picks 52, the person arriving second can pick 52, 53, …, 60, or 9 cases

–This pattern will continue so we have 53 having 8 cases, 54 having 7 cases and so on.

To summarize, for the person arriving first, there are this many ways for the person arriving second to choose:

–For the numbers 0 to 50, there will be 11 cases

–For the numbers 51 to 60, there will be 10, 9, 8, 7, …. 1 cases, respectively

We need to double this to find the total number of winning pairs. Thus we have:

Number of times friends meet = 2[ (50)(11) + 10 + 9 + 8 + ... + 1] = 2(616) = 1,232

This has to be divided by the total number of pairs. As each person can pick among 61 numbers, the total number of pairs is 61 x 61 = 3,721.

Thus the probability the friends meet in the discrete case is 33.1 percent = 1,232 / 3721.

This is actually pretty close to the continuous case. Could there be a relation between the two problems?

Solution to discrete problem in arbitrary interval

I got to thinking, what would happen if we instead split up the interval into finer points, like into seconds or so on?

I did the calculation for seconds, and I will spare you the details, but it ends up at roughly 30.6 percent. This is very, very close to the answer of the continuous model.

What would happen if the interval was divided into N pieces? And what would happen if we let N go to infinity?

If the interval was divided up as 0, 1, 2, … , N, then we need to remember that 10 minutes corresponds to 1/6 of the total time, which means it will translate into (1/6) N intervals (for simplicity, let N be a multiple of 6).

Using the same logic as in the discrete case of minutes, we can count the number of ways the person arriving second could meet the person arriving first. It is:

–For the numbers 0 to (5/6) N, there will be (1 + (1/6)N) integers of times for the person arriving second so they meet

–For the numbers (5/6) N + 1 to N, there will be (1/6)N, (1/6)N – 1, …. 1 times, respectively

Again, we need to double this number to account for the symmetric case. This means we have in all:

We need to divide this by the total number of cases which is (N+1)^2 = N^2 + 2N + 1. So the limiting case is:

When we take the limit as N goes to infinity this is 11/36, just as in the continuous case!

For some people it will just seem “obvious” that the discrete problem converges in limit to the continuous problem.

But anyone who has studied financial models knows that discrete versions are not the same and may not converge to the same as continuous models. (see here for long discussion of discrete and continuous)

So this is an interesting result, and it’s amazing how many different ways this puzzle can be solved.

If you have made it this far, I am sure you have enjoyed the puzzle as much as I have. Please share your comments. Especially appreciated would be alternate solution methods.