19
$\begingroup$

Amy will walk south and east along the grid of streets shown. At the same time and at the same pace, Binh will walk north and west. The two people are walking in the same speed. What is the probability that they will meet?

Grid showing the position of the two people

I tried using Pascal's triangle but I have no idea how to proceed.

$\endgroup$
5
  • 3
    $\begingroup$ ... with the same speed, right? $\endgroup$ – user66081 May 2 '17 at 15:28
  • $\begingroup$ Yes, both are walking in the same speed. I just saw I made a type and instead of writing pace I wrote place. $\endgroup$ – Sarhad Salam May 2 '17 at 15:28
  • 1
    $\begingroup$ So please add this information to the problem description. $\endgroup$ – miracle173 May 2 '17 at 15:29
  • $\begingroup$ It is explained here youtu.be/F_kt51Qj1RI $\endgroup$ – Thomas Wagenaar May 2 '17 at 20:38
  • 7
    $\begingroup$ There's missing information in your problem description (though I can guess what it is). First, you can't walk North and West at the same time (because of the grid). Presumably you mean that there's a 50% chance of each choice being taken by A and B. You need to state that. $\endgroup$ – Francis Davey May 2 '17 at 22:02
22
$\begingroup$

Here's one possible way that Amy and Binh can meet:

red-blue paths

Together, the red and blue path make up a path from point $A$ to point $B$. There are $\binom{10}{5} = \frac{10!}{5!\,5!}$ such paths, because each path consists of $5$ vertical steps and $5$ horizontal steps, and there are $\binom{10}{5}$ ways to choose which steps are vertical.

There are $2^{5+5}$ ways to choose which $5$ steps Amy takes, and which $5$ steps Binh takes. Of them, $\binom{10}{5}$ result in them meeting. So the probability is $\binom{10}{5}/2^{10} = \frac{252}{1024} = \frac{63}{256}.$

$\endgroup$
3
  • 11
    $\begingroup$ For those trying to follow along, one unstated fact is that Alice and BInh can only meet after each person has walked exactly 5 blocks. To prove that fact, you could think about an expression based on their coordinates like Ax + Ay + Bx + By, and show that the expression is invariant (always equal to 10). So if they meet (A's coords are equal to B's coords), then we have Ax + Ay = 5, so Amy has walked exactly 5 steps, and same thing goes for Binh. Therefore, the first 5 steps taken by each person determine whether or not they will meet, and that's why 2^5 is relevant. $\endgroup$ – David Grayson May 3 '17 at 0:20
  • 1
    $\begingroup$ Hi, can you please explain to me why this answer is wrong? "All the possible ways for them is $\binom{10}{5}*\binom{10}{5}$, and in only $\binom{10}{5}$ of them they meet each other. So the probability is $\dfrac{1}{\binom{10}{5}}$ $\endgroup$ – Soroush khoubyarian May 3 '17 at 13:59
  • $\begingroup$ @Soroushkhoubyarian There's an unstated assumption here, which is that Amy and Binh are equally likely to pick either direction until they run into an edge. If they pick uniformly random routes, then the denominator should be $\binom{10}{5}^2$ instead. But after they meet each other in $\binom{10}{5}$ ways, they have more ways to finish their path, so your approach should lead to a bigger answer than $\frac{1}{\binom{10}{5}}$. $\endgroup$ – Misha Lavrov May 7 '17 at 15:51
5
$\begingroup$

It's first worth noting that the number of ways to make $Y$ moves vertically and $X$ moves horizontally is $\binom{X+Y}{Y}$ (think of it like writing $X+Y$ move-slots and choosing $Y$ of them to be vertical movements, which means the rest are horizontal).

Amy and Binh must make $10$ moves each, which means they can only meet after $5$ moves.

Assuming they meet: If Amy makes $Y$ moves down and $X$ moves to the right (cumulatively), Binh must make $X$ moves up and $Y$ moves to the left (cumulatively). There are $\binom{X+Y}{Y}^2 = \binom{5}{Y}^2$ ways for both people to arrive at such a meeting point.

This value is the numerator of our probability, and the denominator is the total number of possible paths after $5$ moves, which is $2^5$ per person. Over all $Y$, we have:

$$P = \sum_{Y=0}^{5} \frac{\binom{5}{Y}^2}{(2^5)^2} = \frac{63}{256}$$

$\endgroup$
4
$\begingroup$

Amy walks north and east while Bing walks south and west, so if they meet at all it will be on the diagonal which runs from northwest to southeast.

So consider the probability that they meet in the southwest corner. This requires Amy to walk 5 squares to the south while Bing walks five squares to the east. Assume that Amy walks south and east with equal probability of 1/2 at each step, and similarly Bing walks north and east with equal probability. Then Amy will go to that square with probability $(1/2)^5$, and so will Bing; they'll meet at that square with probability $(1/32)^2 = 1/1024$.

You can do a similar computation for each square along the diagonal and add up the results.

$\endgroup$
3
  • $\begingroup$ I think it is also the case that after 5 steps they will each be on the rising left to right diagonal. And that is the only way they can meet. Seems like there should be a solution from this, but I am unable to find it. There are 6 points on the diagonal. So why not 1/6 chance A is at px after 5 moves, and 1/6 chance B is at px? That means 1/6 * 1/6 chance they meet = 1/36 chance they meet? I see that is wrong, but don't see why :( $\endgroup$ – Sean May 3 '17 at 11:07
  • 1
    $\begingroup$ That would be right if each point on the diagonal was equally likely to be reached in 5 steps. But it's much more likely to reach the points at the middle of the diagonal than the points at the end of the diagonal. $\endgroup$ – Michael Lugo May 3 '17 at 15:35
  • $\begingroup$ Ah, because for instance there is only one possible path to reach bottom left, but many to reach middle points. Got it, thanks! $\endgroup$ – Sean May 4 '17 at 10:40
4
$\begingroup$

If they meet at all, they do on the (rising) diagonal. The number of "successfull" (pairs of) paths equals the number of paths from top left to bottom rigth, which is $10\choose 5$. The total number of (pairs) of paths is $2^{10}$.

$\endgroup$
3
$\begingroup$

Just a silly piece of code, approximating the answer...

#!/usr/bin/python3

from random import choice

A = [0, 0]
B = [5, 5]

N = 100000  # Number of simulations
n = 0       # Number of meetings
for _ in range(N) :
    a = A[:]
    b = B[:]
    while (b != A) & (a != B) & (a != b) :
        a[choice([i for (i, t) in enumerate(a) if (t != B[i])])] += 1
        b[choice([j for (j, t) in enumerate(b) if (t != A[j])])] -= 1
        n += (a == b)

print(n / N)
$\endgroup$
6
  • 1
    $\begingroup$ You are running more simulations than there are cases :) $\endgroup$ – Aurel Bílý May 2 '17 at 19:02
  • 1
    $\begingroup$ Usually simulations to approximate the answer make sense when the answer would be computationally much more difficult to obtain. $\endgroup$ – Aurel Bílý May 2 '17 at 19:19
  • 3
    $\begingroup$ Or when they're just fun $\endgroup$ – thumbtackthief May 2 '17 at 19:34
  • $\begingroup$ @AurelBílý One of the advantages of a well-written simulation is that it can be easily tweaked to answer other questions such as -- what if there is a 3-dimensional grid? What if the grid is larger? etc. $\endgroup$ – John Coleman May 3 '17 at 14:01
  • 1
    $\begingroup$ @JohnColeman I agree, I agree, simulations can be fun and useful in many situations, I cannot argue with that. I was just pointing that it is somewhat amusing in this specific case to run more simulations in order to reach an approximate / inaccurate answer than to evaluate all possible cases to reach the exact answer. $\endgroup$ – Aurel Bílý May 3 '17 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.