2
$\begingroup$

I have a combinatorics problem to solve, and I'm realy not sure how to do it. Here's the problem:

In [0,0] of a plane is a black piece and in [n,n] is a white one. The black moves each second per 1 to the right or up (equal probability). The white moves also each second per 1 to the left or down (equal probability). Determine the probability of their encounter.

First thing I started with was the conditions. They can't meet unless: n >= 0 and time is n seconds.

Next I tried to test the first few n: for n=0..3 the probability is {1, 2/4, 6/16, 14/100}, which didn't helped me much.

So how to approach this? I'd be much thankfull for any help..

  • 1
    @Ondrej Sotolar: Yes, and ideas on how to do this have already been posted as answers by others. If you want to compute individual terms on the diagonal, look at the answer by Michael Lugo. But one can calculate directly. The number of paths from $(0,0)$ to $(n,n)$ is $\binom{2n}{n}$, since we will take $2n$ steps, of which $n$ are North and $n$ are East, and we must decide at which *set* of $n$ steps goes East.2011-12-17

3 Answers 3

4

The following is a minor twist on the standard idea.

Alan lives at $(0,0)$ and Beti lives at $(n,n)$. Alan tosses a fair coin $n$ times. Whenever he gets a head, he goes one block North, and whenever he gets a tail he goes one block East.

Beti also tosses a fair coin $n$ times, and goes one block West whenever she gets a head, and one block South whenever she gets a tail. What is the probability that Alan and Beti end up at the same place?

They end up at the same place precisely if the total number of heads that they toss between them is $n$. But the probability of getting exactly $n$ heads in $2n$ tosses of a fair coin is $\binom{2n}{n}\left(\frac{1}{2}\right)^{2n}.$

2

Hint: it is easier if you consider one piece to be fixed and only move the other one. Say you move black. What is the chance that the path goes through (n,n)?

  • 0
    To get to (n,n) you need n steps up and n steps right out of the 2n. That is what I think is easier to see about moving only one piece.2011-12-17
1

If they meet, they do so at time $n$. First, find the probability that both players are at the position $(n-k, k)$ at time $k$. Then sum over $k$; Vandermonde's identity will be helpful.