All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Play or Pass (Posted on 2013-05-28)
A game consists of two players taking turns, each time removing a limited number (1 to k) candies from either of two plates, initially containing m and n candies (m>=n).

The player who removes the last candy (or candies) wins.

The player to make the 1st move is defined by a toss of a fair coin and has the unique option, after counting the candies, either to start playing or to waive his turn and let his rival to begin.

Both players have correctly analyzed the game and play according to the best available strategy.

What is the probability that the player designated to go first decides to waive his turn?

Rem: You may assume that both m and n are 2-digit numbers and k is a one digit number over 4.

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Addressing the problem (spoiler) | Comment 3 of 4 |
The winning strategy for any m,n,k is to always leave a position where the difference between the piles is a multiple of (k+1).  If the difference between the piles is a multiple of (k+1), then the next player (who can only take 1 to k candies) must make the difference between the piles equal to 1, 2 ... or k (mod k+1) and the winning player can always restore the difference to 0 (mod k + 1).

If the initial position has a difference that is a multiple of (k+1), then the initial player passes.  If m and n are chosen randomly without limit, then this will occur with probability 1/(k+1).

However, the calculation is more complicated if m and n are constrained to be two digit numbers, especially if n is chosen randomly and then m is randomly chosen between n and 99.  But, even if they are independent, the calculation is not straightforward.  For instance, let n = 6.  The probability of passing cannot be exactly 1/7, because there are 90*90 = 8100 different combinations of two numbers between 10 and 99, and 8100 is not evenly divisible by 7.  I worked this out earlier today, and then lost my worksheet, but I think it comes to 1158/8100 = .14296296296..., which is slightly higher than 1/7.

 Posted by Steve Herman on 2013-05-28 22:29:00

 Search: Search body:
Forums (0)