wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Coin Removal
        
(Message started by: Jeremy Randolph on Jan 25^th, 2003, 1:23pm)

Title: Coin Removal
Post by Jeremy Randolph on Jan 25^th, 2003, 1:23pm

You’re playing a game with a friend. A large number of coins are placed in front of you; each person takes turn removing 1 to n coins (the current player decides how many coins to remove). Whoever removes the last coin loses the game. Your opponent gives you the first move. Devise a strategy to maximize your chances of winning.

There are enough coins so that each person will have at least one turn before someone loses.

Title: Re: Coin Removal
Post by BNC on Jan 26^th, 2003, 1:06am

Since "n" is not bounded in this riddle, taking all the coins - 1, leaving you poor friend with a single coin to remove should work.

Title: Re: Coin Removal
Post by jeremy randolph on Jan 26^th, 2003, 10:54am

n is a constant number for each individual game.

maybe my last statment wasn't clear, but basically there are at least 2n coins. both players will have the option of taking a maximum number of coins before someone will lose.

Title: Re: Coin Removal
Post by towr on Jan 26^th, 2003, 11:35am

if there are 2 up to n+1 coins left then you can win by taking all but one coins
for n+2 coins there is no way to win since you have to take at least 1, reducing it to the first case, but for the other player..
for n+3 up to n+n+2 coins you can win by taking all but n+2 coins.
for 2*n+3 coins there is again no way to win, since 1 to n coins will reduce to the former case in which the other player will win.
for 2*n+4 to 3*n+3 you can reduce it to the former case and win..
etc..

you can win if the number of coins is between (inclusive) (i-1)*(n+1)+2 and i*(n+1) for some i, by reducing the number of coins to (i-1)*(n+1) +1

Title: Re: Coin Removal
Post by Misha on Jan 26^th, 2003, 5:19pm

Generally speaking, most games like this allow you to remove 1 to 3 coins only. So you can take one, two, or three coins in your turn. Therefore, you won't be able to take all but one leaving one for your opponant. The best strategy in a two player game is to take the maximum each time til you can make the remainder 5 after taking your 1,2, or 3.
If your opponent takes 1, you can take 3 busting them
If your opponent takes 2, you can take 2 busting them
If your opponent takes 3, you can take 1 busting them.
The strategy here is to be sure you opponent has 5 to choose from on their turn.

I'm sure this strategy can be altered for other numbers (ie: 1 to 4 each turn, 1 to 5 each turn etc). But this is the basic principle of the game.

Title: Re: Coin Removal
Post by towr on Jan 26^th, 2003, 11:54pm

In the n=3 case taking the maximum number of coins untill there are 5 left will often make you lose.
Suppose there are 10 coins, you take the maximum, 3, so there are 7 left, your opponent take 2, leaving 5, you loose..
Whereas taking 1 makes you win.. (because 10=2*(3+1)+2 )

Title: Re: Coin Removal
Post by TimMann on Feb 2^nd, 2003, 3:06pm

The winning strategy is to always make the number of coins remaining after your turn congruent to 1 modulo n+1. If the number is already of that form before your turn, your opponent is winning, so take an arbitrary number and hope he makes a mistake.