1
$\begingroup$

Sandra and Flora are sitting on opposite corners of a $5\times5$ square grid. Sandra moves randomly east or north, and Flora randomly moves south or west. They move at the same rate. Find the probability that they will meet for lunch.

Process: I realized that since they move at the same rate, they can only meet along any of the points on the diagonal. There are $6$ points on the diagonal, and the line is also the 5th line of Pascal's triangle when you are counting the number of ways Sandra or Flora can reach that point, $(1,5,10,10,5,1)$. Each of them have 32 possible routes to reach the diagonal, and after some calculations I got $\frac{63}{256}$ as my final answer. Did you guys get the same thing? I'm not sure if I'm doing this right.

$\endgroup$
  • $\begingroup$ The binomial distribution for your diagonal should be $(1,4,6,4,1)$ since you have a square grid of $5$. $\endgroup$ – RandomUser May 8 '14 at 19:30
  • 2
    $\begingroup$ No I'm pretty sure it's (1,5,10,10,5,1). The grid is 5 by 5 which means that three are 6 points along each line. $\endgroup$ – user148790 May 8 '14 at 19:35
  • $\begingroup$ I thought they were moving on the squares of the grid, not on the edges. In that case, yes, it is the correct distribution. Also, your answer is correct. $\endgroup$ – RandomUser May 8 '14 at 19:37
2
$\begingroup$

I agree with your calculation assuming they move on the lines of the grid.

$\endgroup$
  • $\begingroup$ @user148790 I also agree with $63 / 256$. $\endgroup$ – 6005 May 8 '14 at 19:56
1
$\begingroup$

Label the grid as ordered pairs $(i,j)$ where $i,j = 1,2,3,4,5$ and we increase our numbers from left to right and bottom to top, so the bottom left corner is $(1,1)$ and the top right corner is $(5,5)$.

Now, there is clearly only one way for them to meet at $(1,5)$ or $(5,1)$.

In how many ways can they meet at $(2,4)$ or $(4,2)$? It is clear the answer will be the same for both, and it is also clear that the number of ways either of them can get to the desired point is equal, so let's just consider how many ways Sandra can end up at $(2,4)$.

Let E denote motion east, N motion north. Then there are 4 paths that lead her to $(2,4)$:

  1. E N N N
  2. N E N N
  3. N N E N
  4. N N N E

Thus there are also 4 ways for Flora to get there, so $4*4 = 16$ ways for the meeting to occur at $(2,4)$. Same answer for $(4,2)$.

Now for the center, $(3,3)$. Again let's look at it from Sandra's point of view.

There are 6 paths that lead her to the center:

  1. E E N N
  2. E N E N
  3. E N N E
  4. N N E E
  5. N E N E
  6. N E E N

Thus there are also 6 ways for Flora to get there, so $6*6 = 36$ ways to meet at the center.

There are then $1+ 1+ 16 + 16 + 36 = 70$ ways for them to meet, so the probability is $\frac{70}{256}$

$\mathbf{A \;better \;approach:}$ Notice that to get to the center, Sandra has to make 4 moves, 2 of which must be E; it doesn't matter which one's are E or N so the number of ways for her to get there is $\binom{4}{2}$ = 6. Similarly to end up at $(2,4)$ she must make 4 moves, one of which must be an E, so there are $\binom{4}{1} = 4$ ways for this to happen. Lastly, $\binom{4}{0} = 1$ ways to end up in a corner.

$\endgroup$
0
$\begingroup$

You should have clarified that in 5*5 grid there are 36 points. In general people assume there are 25 points. Anyway, in that case I think your answer is correct as both of them move independently (the hidden calculation follows from a simple argument of independence of probability).

$\endgroup$
  • 1
    $\begingroup$ Agreed, which is what I assumed in my answer. But my method can easily be extended to (what I would call) the $6 \times 6$ case $\endgroup$ – pwerth May 8 '14 at 20:03

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.