Suppose a person leaves from home to the health club (eight blocks east and five blocks north). Furthermore, suppose this person wants to keep the route as short as possible but likes to vary it:

enter image description here

There are $C(13,8)$ routes. My question is what the probability would be of two people meeting if one (say, Matt) left from the home to the health club, and someone else (say, Tine) left from the health club to the home. This is similar to a question asked yesterday where there was a square grid.

My thought here was that the probability of Matt and Tina meeting would be $\frac{C(13,8)}{2^{13}}$, but that doesn't seem right given that Matt and Tina can walk on different paths even though they will only ever meet 6.5 blocks into their walk. Any idea about how to deduce what the probability would be here?

  • $\begingroup$ @N.Shales What you have suggested does not seem easy/clear to me without going about it in brute computational way. How can you determine which legs people must take? There seem to be a large number of options. $\endgroup$ – interrogative May 4 '17 at 0:46
  • $\begingroup$ Hmm, seems there may be a discrepancy. I will check and reinstate my answer when I can be sure it's right. Good question though. $\endgroup$ – N. Shales May 4 '17 at 1:57
  • $\begingroup$ Thinking about the problem further reveals that the probability is potentially different if they take a random direction at each intersection compared with if they each choose their paths randomly before leaving off. $\endgroup$ – N. Shales May 4 '17 at 14:01

The issue is that the choice of possible paths is not $2^{13}$ as we are limited by the vertical steps.

Assume Matt and Tine both walk a path of length $6$. Then we also need that they are in crossing position.

For Matt, the options are:

  • NNNNNE - $6$ ways
  • NNNNEE - $15$ ways
  • NNNEEE - $20$ ways
  • NNEEEE - $15$ ways
  • NEEEEE - $6$ ways
  • EEEEEE - $1$ way

Total: $64-1=63$ ways. Similarly for Tine.

This solves the problem for rectangles $m\times n$, where $m+n$ is even, as by this stage they have met.

For $m+n$ odd, we have that after $6.5$ legs, we have the same number of possibilities as after $7$ legs, which is $128-1-7=120$.

Probability is then $\dfrac{1287}{14400}\approx 0.0894$.

  • $\begingroup$ Why not NENENE? $\endgroup$ – David G. Stork May 4 '17 at 19:22
  • $\begingroup$ NENENE is 1 of the 20 ways from NNNEEE $\endgroup$ – JMP May 5 '17 at 3:32

The red dots show the only locations the two can meet:

enter image description here

and the green numbers the number of routes from Home to that point.

For each meeting point, you find the number of Matt's routes that go through that point, and the number of Tine's routes that go through that point. The green numbers show the number of routes for Matt to get to that point; note you must then find the number of total routes through that point. Divide each of these by the total number of routes for Matt and for Tine. This gives the probabilities for each. You multiply those probabilities to find they meet at each such point, then add all those probabilities.

The total number of routes for Matt is: ${13 \choose 8} = 1287$, and likewise for Tine.

So the probability they meet at the red point at the lower right is $P[Matt] \cdot P[Tine] = {6 \over 1287} \cdot {6 \over 1287} = {36 \over 1287^2}$. And likewise for the other points.

Then just add them up to get the total probability they meet somewhere.


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.