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