## October 2002

<<September
**October**
November>>

The answer depends on whether M and N are even or odd.

Let X=(M-1)/M, and let ** denote exponentiation.

Let F(M,N) be the desired probability.

If N is even and M is even,

F(M,N) = M/(2M-1) - (1/(4M-2))*X**(N-M).

If N is odd and M is even,

F(M,N) = (M-1)/(2M-1) - (1/(4M-2))*X**(N-M).

If N is even and M is odd,

F(M,N) = M/(2M-1) - (1/(4M-2))*X**(N-M+1).

If N is odd and M is odd,

F(M,N) = (M-1)/(2M-1) - (1/(4M-2))*X**(N-M+1).

One way of attacking the problem is to take each even integer 2k less

or equal to N, and compute the probability that it 2k the last player

chosen, namely (1/M) * ((M-1)/M)**(N-2k) if 2k is at least M, and

(1/M) * ((M-1)/M)**(N-M) if 2k is smaller than M, and then sum that;

part of the sum will be a geometric series, and part will be just a

multiple of the (1/M) * ((M-1)/M)**(N-M) term, with the dependence on

parity of M and N showing up in the limits of the sums.

Another way is to fix M (either even or odd) and use induction on N.

Use N=M as the base case.

For N>M, compute F(M,N) from F(M,N-1) by saying that with probability

(1/M) player N is the last one to exit, and with probability (M-1)/M,

the last player chosen was one of the other M-1 players in that last

game, and the probability that this player has an even number is the

same as F(M,N-1).

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com