Teaser Tuesday! September 9, 2014
I hope everyone finds this one challenging! Enjoy!
Note: If you could all please input your answers using the previously noted html code it will allow others to answer without having a spoiler. Copy it verbatim and do not stick any " or ' in your answer and it will work.
Question
Billy the future banker was worried about an upcoming test in Discrete Mathematics and was finding it hard to get to sleep. Billy awoke early in the morning, aroused by devilish laughter, only to see an impish looking homunculus sitting at the bottom of the bed next to a seemingly infinite pile of chips. The creature then asked Billy if he would like to play a little game? It went on the explain that the pile contained 1,343,546,758,343,209,876 chips and the bottom chip represented his immortal soul. Further, the rules are quite simple: The first player takes some chips, but not all of them. After that they alternate turns to take more chips.
The only rule now is that a player cannot take more in their turn than the previous player took. The winner is the player who takes the last chip. If I win I get to keep your soul and if you win, you get an A in the test. Would you like to go first or second? This seemed a reasonable bet to Billy. Can you give Billy a strategy for playing no matter how many chips there are?
Good Luck!
so only the first person can't take all the chips? or every turn you are not allowed to take all the chips?
Some of the answers would be valid only if the players were told how much the starting chip count was and how much each player took each turn.
@"Michal-Dubisz" and @"MM08" are close but not correct.
[let total number of chips be n]
Justification: Case 1: Total n is odd (and greater than 1). Then obviously first person has winning strategy. Simply take one chip. Second player is forced to take only one chip. This continues until first person picks up the winning chip.
This implies that one can NOT pick up only one chip if that chip is an even number. Otherwise the next player to pick up a chip will be picking up one chip on an odd number, turning this into case 1. Therefore if there are an even number of chips remaining, player should pick up an even number.
Consider when the 1st player picks up 2 chips for an even number of total chips. The 2nd player can only pick up 1 or 2. If the 2nd player picks up one, this turns into case 1 for the 1st player and they simply alternate taking one chip until 1st player wins. Therefore the 2nd player takes 2. This will continue until the last chip is taken.Thus 1st player wins when n/2 is odd.
To summarize: If n is odd, 1st player wins If n is even and n/2 is odd, 1st player wins.
More complicated when n is even and n/2 is even. For example, when n=4 or 8, 2nd player wins. But when n=12, 1st player wins (since he takes 4 reducing it to n=8).
@"Frabbit"
If n is even, n/2 is odd if and only if n=2. In such a case, only the second person has a winning strategy, the first player always loses.
@"mikesswimn" "If n is even, n/2 is odd if and only if n=2."
This is false... eg. 6, 10, 14, etc.
I should amend my earlier post: If n is even and n/2 is odd also greater than 2, 1st player wins.
@"Frabbit"
Ah, there you go, clearly not thinking well this morning.
Sit distinctio qui reprehenderit facilis recusandae tempora nemo. Perferendis atque similique voluptatem. Pariatur et eum aperiam vero adipisci eius. Ut consequatur necessitatibus consequatur. Non tenetur numquam consequatur magni ex dolorum.
See All Comments - 100% Free
WSO depends on everyone being able to pitch in when they know something. Unlock with your email and get bonus: 6 financial modeling lessons free ($199 value)
or Unlock with your social account...