wu :: forums
« wu :: forums - Coins on a table »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 12:00pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Grimbal, Eigenray, william wu, towr, ThudnBlunder, Icarus, SMQ)
   Coins on a table
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Coins on a table  (Read 9867 times)
Stefan Kneifel
Newbie
*





   


Gender: male
Posts: 25
Coins on a table  
« on: Aug 30th, 2003, 2:10pm »
Quote Quote Modify Modify

There are n coins lying on a table. Mr. A and Mr. B are playing the following game:
 
Mr. A begins by removing an arbitrary number of coins, except that he is not allowed to remove all coins in the first move. From then on, every player removes one or more coins, but not more than twice as many as the preceding player has taken with his last move. The player who removes the last coin wins.
 
1.) Who will win the game, depending on n?
2.) What is the optimal strategy?
 
 
Greetings from Switzerland Smiley
 
Stefan
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Coins on a table  
« Reply #1 on: Aug 30th, 2003, 2:49pm »
Quote Quote Modify Modify

Welcome to the Forum!  
 
Unfortunately this puzzle, with a different story, is one of the HARD Riddles.
 
It's a good puzzle, though.
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
visitor
Guest

Email

Re: Coins on a table  
« Reply #2 on: Aug 30th, 2003, 5:50pm »
Quote Quote Modify Modify Remove Remove

Actually, it's not quite the same riddle. Here you're allowed to take twice as many chips as the other person. In the thread discussing the original riddle, BNC raised this variation, but no one answered him.  
It looks more complicated.  
Here's my guess at the winning strategy:
The starting positions that must lose grow by the Fibonacci series: If the starting number is any other number, either take off to reach the nearest Fibonacci number, or, when you can't take off that many, think of that number as 0 and consider the fibonacci series that starts at that point. Lather, rinse, repeat as necessary.

IP Logged
Stefan Kneifel
Newbie
*





   


Gender: male
Posts: 25
Re: Coins on a table  
« Reply #3 on: Aug 30th, 2003, 10:24pm »
Quote Quote Modify Modify

on Aug 30th, 2003, 2:49pm, Icarus wrote:
Unfortunately this puzzle, with a different story, is one of the HARD Riddles.

Hmm.... sorry... I made a search with "Fibonacci" through the posts, and as I couldn't find this riddle, I posted it Smiley
 
Besides that: Congratulations to "visitor" Cheesy
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Coins on a table  
« Reply #4 on: Aug 31st, 2003, 11:18am »
Quote Quote Modify Modify

on Aug 30th, 2003, 5:50pm, visitor wrote:
Actually, it's not quite the same riddle. Here you're allowed to take twice as many chips as the other person. In the thread discussing the original riddle, BNC raised this variation, but no one answered him.  

 
Sorry - I missed that. With the different limit, it is a different puzzle. As is evidenced by the different solution you provided.
 
My apologies, Stefan! And well done, visitor.
 
(By the way, with all the posts you've put in (assuming they are all the work of the same person), why haven't you registered?)
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Stefan Kneifel
Newbie
*





   


Gender: male
Posts: 25
Re: Coins on a table  
« Reply #5 on: Aug 31st, 2003, 12:33pm »
Quote Quote Modify Modify

For the curious:
 
The riddle is due to R.E.Gaskell and M.J.Whinihan and was originally published in "Fibonacci Quarterly", 1 (December 1963), pp. 9-12.
IP Logged
Barukh
Guest

Email

Re: Coins on a table  
« Reply #6 on: Sep 2nd, 2003, 5:34am »
Quote Quote Modify Modify Remove Remove

I would suggest the following generalization: at every move, the player takes no more than L times as many coins as the preceding player.  Roll Eyes
 
So far, we know the answer for L = 1 the first player looses on powers of 2, and L = 2 the first player looses on Fibonacci numbers.
IP Logged
DH
Newbie
*






   


Gender: male
Posts: 19
Re: Coins on a table  
« Reply #7 on: Sep 2nd, 2003, 11:01am »
Quote Quote Modify Modify

on Sep 2nd, 2003, 5:34am, Barukh wrote:
I would suggest the following generalization: at every move, the player takes no more than L times as many coins as the preceding player.  Roll Eyes

 
I think that the losing configurations are going to get more and more complex but it's not hard to compute them using dynamic programming. I think it can be done in O(n) time and O(n) space.
 
IP Logged
visitor
Guest

Email

Re: Coins on a table  
« Reply #8 on: Sep 2nd, 2003, 1:00pm »
Quote Quote Modify Modify Remove Remove

For L>2 the losing numbers seem to form a sort of a Fibonacci series, except for which two numbers in the series are added.
For L=3 the losing numbers are
1,2,3,4,6,8,11,15,21,29,40,55...
 
For L=4
1,2,3,4,5,7,9,12,15,19,24,31,40,52...
 
For L=5
1,2,3,4,5,6,8,10,12,15,19,24,30,38,48,60...
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board