Ponder This Challenge - October 2002 - Tournament of N with <=M players

Ponder This Challenge:

This month's problem was sent in by Sudipta Das from Calcutta:

In a certain tournament, N players have been numbered 1 through N.
But, only M players can play the game together (1<M<N).
So, Players 1 through M start the game.
One of them goes out, and Player (M+1) joins the game.
This continues until there is no one left to join the game.

As a function of N and M, what is the probability that the game ended with an even-numbered player going out?

Closed-form solution is preferred (expressed without sums or recursion).

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  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

Solvers

• Kunal Shroff (10.02.2002@02:36:15AM EDT)
• Nancy Zvi (10.02.2002@09:13:12AM EDT)
• Michael Brand (10.02.2002@10:15:21AM EDT)
• Jonathan A. Wildstrom (10.02.2002@12:14:45PM EDT)
• Hazem D. Elmeleegy (10.03.2002@06:07:06AM EDT)
• Wu Zheng (10.03.2002@01:23:43PM EDT)
• John G. Fletcher (10.03.2002@05:51:54PM EDT)
• Manish Tayal (10.03.2002@06:23:49PM EDT)
• Christie Bolton (10.04.2002@02:01:54PM EDT)
• Gyora Benedek (10.06.2002@09:36:37AM EDT)
• Hassan Masum (10.06.2002@07:13:47PM EDT)
• Soonho You (10.07.2002@09:32:00PM EDT)
• Joseph DeVincentis (10.07.2002@10:15:48PM EDT)
• Chris Shannon (10.08.2002@01:47:29AM EDT)
• Michael Swart (10.08.2002@09:33:50AM EDT)
• Christopher Howe (10.08.2002@10:29:38AM EDT)
• Francis Golding (10.08.2002@05:52:49PM EDT)
• Ashish Mishra (10.08.2002@09:56:53PM EDT)
• Karl Dsouza (10.08.2002@12:08:06PM EDT)
• Kennedy (10.09.2002@01:10:50AM EDT)
• Yuvraj Singh Dhillon (10.09.2002@01:31:15PM EDT)
• Utku Diril (10.10.2002@11:04:20AM EDT)
• Bartolini Claudio (10.10.2002@01:16:10PM EDT)
• Sriram Rallabhandi (10.10.2002@02:51:56PM EDT)
• Jayavel Sounderpandian (10.12.2002@04:17:53AM EDT)
• Sarang Aravamuthan (10.12.2002@12:01:35PM EDT)
• L.T. Pebody (10.14.2002@05:36:59PM EDT)
• Michael Lieberman (10.14.2002@10:47:34PM EDT)
• Christopher Yao (10.18.2002@06:35:21PM EDT)
• Cervenansky Pe (10.21.2002@11:08:58AM EDT)
• ter (10.21.2002@11:08:58AM EDT)
• Hagen von Eitzen (10.21.2002@01:45:32PM EDT)
• Deepu Sebastian Joseph (10.21.2002@02:35:36PM EDT)
• Maxim G. Smith (10.25.2002@02:53:11PM EDT)
• JP Sugarbroad (10.29.2002@02:58:26PM EDT)
• Aditya Utturwar (10.30.2002@11:04:16AM EDT)
• ILB Working Group (10.30.2002@03:24:12PM EDT)
• Stephen Martin (10.31.2002@09:43:55AM EDT)
• Peter Huggins (10.31.2002@02:17:48PM EDT)