# Combinatorics question concerning two square-board game pieces

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..

-
Hint: if they meet (after $n$ seconds), then the $n$-step path taken by the black piece plus the (reversed) $n$-step path taken by the white piece makes a single $2n$-step path from $(0,0)$ to $(n,n)$, where each move is to the right or up. How many such paths are there? Compare this to the total number of choices for the first $n$ seconds. – mjqxxxx Dec 17 '11 at 20:38
I think there is more than the amount of 2n-length paths composed of (n-length path)+(reversed n-length path) paths – Ondrej Sotolar Dec 17 '11 at 21:06
You are right, the number of possibilities should always be 2^(2n), which would correspond for n=3 to 64. – Ondrej Sotolar Dec 17 '11 at 22:36
@Ondrej Sotolar: And for $n=3$ there are $20$ paths, $1$ through each of the remaining corners and $9$ each through the remaining $2$ points on the diagonal. – André Nicolas Dec 17 '11 at 22:52
@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. – André Nicolas Dec 17 '11 at 23:13

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}.$$

-

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)?

-
I'm afraid I don't see the difference, because the paths running through [n,n] must fulfill the same conditions: the length n-1 and they must start and finish in the corners. – Ondrej Sotolar Dec 17 '11 at 20:42
@OndrejSotolar: You are right they are equivalent, but it is easier to see the condition for success/failure in the case only one moves. Since the white one is always at (n,n) the black one has to be there after 2n [not 2n-2] moves. What fraction of the 2n move sequences result in this? – Ross Millikan Dec 17 '11 at 20:47
for n=0 : 1/1, for n=1 : 2/2, for n=2 : 6/8 ... is that what you meant? – Ondrej Sotolar Dec 17 '11 at 21:01
For n=1, only 2 of 4 paths go through (1,1), up/right and right/up. The others do not. For n=2, only 6 of 16 paths go through (2,2).... – Ross Millikan Dec 17 '11 at 21:13
well yes, thats the number of possible paths in the original problem. but after setting white stationary and allowing only connected 2n length paths from black to white, we get only the numbers above. To return to the original problem, how do I find what is the n-th element paths ammount? Please don't give up on me, I sometimes take longer to understand things ;) – Ondrej Sotolar Dec 17 '11 at 21:21

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.

-