Author 
Topic: Take the last chip (Read 2884 times) 

BNC
Uberpuzzler
Gender:
Posts: 1732


Take the last chip
« on: Dec 25^{th}, 2002, 6:58am » 
Quote Modify

Hi, I LOVE riddles  and may I say: great site. Found this somewhere else. I didn't see it here, and figures u guys may like it. Enjoy, BNC Turkey Sandwich was worried about an upcoming test in Discrete Mathematics and was finding it hard to get to sleep. Turkey 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. Hello Turkey it said, would you like to play a little game? This pile contains 43546758343209876 chips and the bottom chip represents your immortal soul. The rules are quite simple. The first player takes some chips, but not all of them. After that we take it in turns to take some 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 Turkey. Can you give Turkey a strategy for playing no matter how many chips there are?

« Last Edit: Aug 30^{th}, 2003, 2:41pm by Icarus » 
IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: New (?) Take the last chip
« Reply #1 on: Dec 25^{th}, 2002, 8:02am » 
Quote Modify

I think I'll go second.. As for strategy.. Well, if the first player takes an odd number, take 1, that way you'll eventually get the last... I don't know about the even case yet..

« Last Edit: Dec 25^{th}, 2002, 8:16am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



orbital
Newbie
Gender:
Posts: 2


Re: New (?) Take the last chip
« Reply #2 on: Dec 25^{th}, 2002, 8:14am » 
Quote Modify

Possible solutions for an odd number of chips in the pile: First I am not sure if 'some chips' defines the minimum of chips set to two. If 'some chips' includes the use of only one chip, then one way to get the last chip is to simply be the first to take a turn and take one chip at the time. Considering the rule that a player cannot take more in his turn than the previous player took, Turkey would be able to get to the last chip like that. If the term 'some chips' means that you have to take away at least two chips, then (considering that number of chips (n) in the pile can be counted properly), you would have to take the half of (n1). Again, the next player cannot take more than you did, the last chip is yours in your next turn. These solutions are of course not sufficient... all I can think of right now


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: New (?) Take the last chip
« Reply #3 on: Dec 25^{th}, 2002, 9:54am » 
Quote Modify

working backwards.. 1; 1:win 2; 1:loose, 2:win 3; 1:win, 2:loose, 3:win 4; 1:loose, 2,3:loose, 4:win 5; 1:win, 2,3,4:loose, 5:win 6; 1:loose, 2:win, 3,4,5:loose, 6:win 7; 1:win, 2:loose, 3:win, 4,5,6:loose, 7:win 8; 1:loose, 2,3,4,5,6,7:loose, 8:win 9; 1:win, 2,3,4,5,6,7,8:loose, 9:win 10; 1:loose, 2:win, 3,4,5,6,7,8,9:loose, 10:win 11; 1:win, 2:loose, 3:win, 4,5,6,7,8,9,10:loose, 11:win 12; 1:loose, 2:loose, 3:loose, 4:win, 5,6,7,8,9,10,11:loose, 12:win My intuition tells me Turkey can win if he starts first and takes 4. Since 43546758343209876 is an odd multiple of 4 you will win if the homunculus also always takes 4. If at any point he takes three or one there will be an odd number, which you can win by taking 1 ever after. If he takes two at any point you will have an odd multiple of two, and so if you both keep taking two everytime you will win. And if at anypoint the homunculus would switch to taking one you will have an odd number and thus also win.. So in conclusion, if the number of chips is not a power of 2, start first and take the highest power of two which is a factor of the number, else start second.. I think that covers it all. Even if it isn't always the optimal way to win, I think it's a sure way..

« Last Edit: Dec 25^{th}, 2002, 9:59am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



BNC
Uberpuzzler
Gender:
Posts: 1732


Re: New (?) Take the last chip
« Reply #4 on: Dec 25^{th}, 2002, 10:37am » 
Quote Modify

And about this variant: What if a player can take up to twice the number of chips that the previous player took. What is the best strategy now? BNC


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: New (?) Take the last chip
« Reply #5 on: Dec 28^{th}, 2002, 5:21am » 
Quote Modify

Interesting. Argh, I keep thinking I've seen this puzzle before in a different form but I can't remember. It's like a onerow Nim but with that rule added. Still thiinking.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



TimMann
Senior Riddler
Gender:
Posts: 330


Re: New (?) Take the last chip
« Reply #6 on: Jan 4^{th}, 2003, 5:21am » 
Quote Modify

Here's the answer I get. I'll conceal the interesting part but leave the initial term definitions visible. In this kind of game, it's common to define the set of safe positions as follows: The final winning position (or positions) is safe. Any position from which you cannot get to a safe position in one move is safe; any other position is unsafe. Then the winning strategy is to always leave a safe position after your move. Your opponent can't get to another safe position in one move, so he must leave an unsafe position, from which you can get to another safe position in one move. Eventually you get to the final position and win. In this game, we can define a position as a pair (n, m), where n is the number of chips left in the pile and m is the maximum number the next player is allowed to take. Initially m = n1; thereafter, m is the number of chips the previous player took. You win by taking all the chips, so any position of the form (0, m) is a final winning position. What positions are safe in this game? Answer: Any position that can be written in the form (2^{a}b, c), where a, b, c, are integers, a > 0, b >= 0, and c < 2^{a} is safe. Any position that can't be written in this form is unsafe. I'll give the reasoning for this in a later post.


IP Logged 
http://timmann.org/



TimMann
Senior Riddler
Gender:
Posts: 330


Re: New (?) Take the last chip
« Reply #7 on: Jan 4^{th}, 2003, 2:12pm » 
Quote Modify

p.s. My answer agrees with towr's. I didn't read his before posting.


IP Logged 
http://timmann.org/



That Don Guy
Guest


Re: New (?) Take the last chip
« Reply #8 on: Feb 13^{th}, 2003, 3:51pm » 
Quote Modify
Remove

So in conclusion, if the number of chips is not a power of 2, start first and take the highest power of two which is a factor of the number, else start second.. I think that covers it all. Even if it isn't always the optimal way to win, I think it's a sure way.. That's what I get as well. Bit of induction here: If the number of chips currently in the pile is odd, then the first player takes 1; under the rules, each player is now limited to taking 1 chip on all remaining turns, and the second player will always have an even number (and leave an odd) while the first player will always have an odd number (and leave an even)  eventually the first player will take the last chip. Therefore, such a position is a winning position. If there is an even number, then, since neither player will take one (and leave a winning position for the opponent), consider the game to be played with "2chips", each one equal to 2 chips. If there are an odd number of 2chips, the first player takes 1 2chip (i.e. 2 chips) and now has a winning position. Thus, a number of chips divisible by 2 but not by 4 is a winning position. If the number is divisible by 4 (so there are an even number of 2chips), use 4chips instead of 2chips; if there are an even number of those, use 8chips, and so on until you get an odd number; the first player removes that many chips to leave a winning position  if it's possible. If the number of chips is a power of 2, then the first odd number is 1 "2^{N}chip", but the first player can't take all of the chips, so the first move has to leave the second player with a winning position. The problem has 10886689585802469 "4chips", so the first player takes 4.


IP Logged 



martin chase
Newbie
Posts: 2


Re: New (?) Take the last chip
« Reply #9 on: Sep 5^{th}, 2004, 12:37am » 
Quote Modify

on Dec 25^{th}, 2002, 10:37am, BNC wrote: What if a player can take up to twice the number of chips that the previous player took. What is the best strategy now? 
 how about making it more unfair  let there be N imps, and you can choose your position in the rounds of chip taking amoung them. this way, the imps can take up to N times your chips. some analysis: if the number of chips is 1 mod N, a strategy is to go first and pick 1 chip. i expect there are more optimal solutions than this, but it'll do. so if there's a different number of chips, and assuming the imps are cooperating, you can't let the imps have two turns in front of you to start off with, as the first imp can just take most of them, allowing the second imp to grab up the last few. we could possibly make a rule to prevent this somehow, but otherwise, your choices are limited to going first or second. i lose it after this, though. i'm thinking there are some N's and some numbers of chips for which you cannot win. i'll keep thinking about it, and sorry if this is an obnoxious way for me to end my first post :/


IP Logged 



Ajax
Full Member
Gender:
Posts: 221


Re: New (?) Take the last chip
« Reply #10 on: May 17^{th}, 2005, 4:01am » 
Quote Modify

on Dec 25^{th}, 2002, 9:54am, towr wrote:working backwards.. So in conclusion, if the number of chips is not a power of 2, start first and take the highest power of two which is a factor of the number, else start second.. 
 My opinion is that, if the even number cannot be divided by two, you take first two, if it can be, you take four in every turn until the opponent takes 2 (you then take also two) or 1 (you take also one). I think it is easier and you don't have to divide the whole number with all the powers of 2. You just divide (if it's an even number) the twodigit number formed by the two last digits with 4. If it's an integer, you start with 4, if not with 2 and so on. So, in the present case, you start with 4 (76/4=19).


IP Logged 
mmm



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: New (?) Take the last chip
« Reply #11 on: May 17^{th}, 2005, 6:55am » 
Quote Modify

on May 17^{th}, 2005, 4:01am, Ajax wrote:My opinion is that, if the even number cannot be divided by two, you take first two 
 Oh yes, I wholeheartedly agree, Although I have yet to encounter an even number not divisble by two


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7523


Re: New (?) Take the last chip
« Reply #12 on: May 17^{th}, 2005, 8:37am » 
Quote Modify

on May 17^{th}, 2005, 6:55am, towr wrote: Oh yes, I wholeheartedly agree, Although I have yet to encounter an even number not divisble by two 
 That would be odd.


IP Logged 



Deedlit
Senior Riddler
Posts: 476


Re: New (?) Take the last chip
« Reply #13 on: May 17^{th}, 2005, 9:07pm » 
Quote Modify

on May 17^{th}, 2005, 4:01am, Ajax wrote: My opinion is that, if the even number cannot be divided by two, 
 When can't an even number be divided by two? Quote: you take first two, if it can be, you take four in every turn until the opponent takes 2 (you then take also two) or 1 (you take also one). 
 what if he takes 3? Quote: I think it is easier and you don't have to divide the whole number with all the powers of 2. You just divide (if it's an even number) the twodigit number formed by the two last digits with 4. If it's an integer, you start with 4, if not with 2 and so on. 
 I'm not sure what the "and so on" signifies here. It's not hard to show that the winning moves are precisely those where you take away m chips and leave a number of chips n divisible by 2^{k}, with m < 2^{k}. Call the set of all such moves I, and call the set of all other moves NI. After any move in I, the next move must be in NI. If the next move takes away i chips, then i < m, and therefore i < 2^{k}. Thus n  i is divisible by the same powers of 2 that i is, and the maximum cannot be more than i. After any move in NI, there is a following move from I. n is of the form 2^{k+1} i + 2^{k} with m > 2^{k}, so for the next move we remove 2^{k} chips, leaving 2^{k+1} i chips, and 2^{k} < 2^{k + 1}. So, a winning strategy consists of taking a move from I; your opponent must choose from NI, which allows you to choose from I, etc. Since all winning moves are from I (zero is divisible by every power of two), you are guaranteed to win. In fact, these are the _only_ winning strategies you can take; if at any point you take a move from NI, your opponent can take a move from I, and claim the winning strategy for himself. It follows that the numbers of chips that have a winning strategy are precisely those that aren't a power of two. So, unfortunately, there is no way to give a winning strategy that doesn't involve going through all powers of two; if the number of chips is divisible by 2^{k}, you have to take away at least 2^{k} chips.

« Last Edit: May 17^{th}, 2005, 9:08pm by Deedlit » 
IP Logged 



brandi
Guest


Re: Take the last chip
« Reply #14 on: May 19^{th}, 2005, 7:27pm » 
Quote Modify
Remove

ummmmmmmmmm it said that you take some chips but not all of them so the person who get the last chip broke the rules


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Take the last chip
« Reply #15 on: May 19^{th}, 2005, 8:41pm » 
Quote Modify

No  the rule is that the first person, on their first turn only, cannot take all the chips. After that, they cannot take more than were taken on the preceding turn. (Though not explicitly stated, we can also assume that the players must take at least one chip each turn.) Therefore the person taking the last chip is always allowed to do so.


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



Ajax
Full Member
Gender:
Posts: 221


Re: New (?) Take the last chip
« Reply #16 on: May 23^{rd}, 2005, 3:24am » 
Quote Modify

on May 17^{th}, 2005, 6:55am, towr wrote: Oh yes, I wholeheartedly agree, Although I have yet to encounter an even number not divisble by two 
 Sorry, my fault, I meant could not be divided by four


IP Logged 
mmm



Ajax
Full Member
Gender:
Posts: 221


Re: New (?) Take the last chip
« Reply #17 on: May 23^{rd}, 2005, 3:40am » 
Quote Modify

on May 17^{th}, 2005, 9:07pm, Deedlit wrote: what if he takes 3? I'm not sure what the "and so on" signifies here. 
 The case of 3 is the same as with 1 "So on" means that you do as told before. Deedlit, I believe you understand more than enough, or else you wouldn't have solved so many riddles or have at least proposed so many solutions, more than half of which I cannot fully understand, due to my lack of intellect I must admit that I have nothing to do with CS and have long forgotten most of the advanced mathematics I've learnt in University. I am not a Mensa member (I don't know if there is a branch in my third world country), but at least I can understand a proposed solution even when there is a minor fault Do you at least agree with what I suggested or not? P.S. I am a humble servant of my insecurities, please don't make fun of me...


IP Logged 
mmm



Deedlit
Senior Riddler
Posts: 476


Re: Take the last chip
« Reply #18 on: May 23^{rd}, 2005, 7:47am » 
Quote Modify

Honestly, I wasn't trying to make fun of you; the issue isn't how much math you or I understand, it's just about being clear. I thought I knew basically what you were talking about (and it looks like it was the right assumption), but since you made some confusing statements, I thought it was best to ask for a clarification. In my view, making sure we understand each other is always perfectly acceptable behavior, as long as we are being serious. For example, you asked me to clarify whether I was agreeing with your proposed solution or not  no sweat, I'll clarify. You say that you can always win if you take away four chips when the stack is a multiple of four. But why can't your oppoenent apply the same strategy? After all, you're leaving him with a multiple of four, and he can take away four, since you just did. So we need more information to find out who wins in such a case. The answer is, it depends on whether the chips are divisible by 8 or not. If the number of chips are of the form 8k + 4, then taking away four chips is a winning strategy; we don't get the same contradiction as above, since your opponent is in a different situation  the number of chips he gets is 8k, not 8k + 4. So what do you do when the number of chips is divisible by 8? Can we answer this without checking for other divisors? This was the purpose of the proof in my last post. It wasn't to give a winnning strategy  towr already gave one  but to describe all possible winning strategies. I did this by describing a set of moves I. The nifty features of this set are: 1. If one player plays a move from I, the other player must play a move from NI (the set of moves not in I). 2. If one player plays a move from NI, the other is allowed to play a move from I. 3. The winning player has always just played a move from I. From these features, it should be clear that the one and only way to assure victory is to always take a move from I. Since your opponent must then always take a move from NI, you win every game. On the other hand, if, at any point, you take a move from NI, then it is your opponent that has the winning strategy, since he can take a move from I at the next step, and continue taking I until the end of the game. So we have succesfully described all the winning strategies by describing I. My definition if I, Quote:It's not hard to show that the winning moves are precisely those where you take away m chips and leave a number of chips n divisible by 2k, with m < 2k. 
 is perhaps a little inscrutable, so here's a more intuitive definition: Write the number of chips left in binary notation. For instance: n = 101101011000. The winning moves are some nonempty suffix of the above binary number. In this case: 1000 11000 1011000 101011000 1101011000 101101011000 Of course the last is forbidden on the first move. It's not hard to see that, if we remove a suffix of length k (call it i), then the number of chips remaining will have at least k zeroes in the end, so it will be divisible by 2^{k} > i. On the other hand, if we remove something other than a suffix, then the remainder will have a 1 somewhere in the last k zeroes, so if j is the number of trailing zeroes, 2^{j} will be less than i. So I is exactly the set of suffixes. This answers the question of when the first player has a winning strategy: there will always be a proper suffix, unless the number of chips is a power of two. How does this relate to your question about having to check all powers of two? The point is, if the number of chips is divisible by 2^{k}, then we have to take away a number of chips divisible by 2^{k}. So there's no way of getting around it.


IP Logged 



asterex
Guest


Re: Take the last chip
« Reply #19 on: May 23^{rd}, 2005, 7:54am » 
Quote Modify
Remove

The problem with your solution is what happens when the starting number is divisible by 8. If you and your opponent keep taking off 4's, it will be your turn when the total hits 8. You'll take 4, your opponent will take the last 4 and win.


IP Logged 



Ajax
Full Member
Gender:
Posts: 221


Re: Take the last chip
« Reply #20 on: May 23^{rd}, 2005, 9:09am » 
Quote Modify

I must accept that I was wrong. Sorry about my outburst too, I was not in the best mood at that moment and it had nothing to do with the present matter. As for the solution proposed, i hoped that there would be a more easy to calculate one (it's not so easy to play if you have to calculate the maximum power of two that can divide the chips and then take so many in each turn, let's say 2^20 chips.


IP Logged 
mmm



Deedlit
Senior Riddler
Posts: 476


Re: Take the last chip
« Reply #21 on: May 23^{rd}, 2005, 9:21am » 
Quote Modify

I would say that this is really a very simple strategy, compared to the difficulty of most games. For example, a computer would already be given the number in base 2, so it would scarcely have to do anything! Even for a human, finding the order of 2 is O((log n)^{2}), which is not bad at all. (Lots of games are O(exp(n))


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Take the last chip
« Reply #22 on: May 23^{rd}, 2005, 9:36am » 
Quote Modify

And if both players know that they both knows the optimal strategy, they don't even have to play the game. If the number is divisible by two, but not a power of two, then the beginner wins.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Deedlit
Senior Riddler
Posts: 476


Re: Take the last chip
« Reply #23 on: May 23^{rd}, 2005, 9:42am » 
Quote Modify

Of course, that's true of any two person, perfect information, deterministic game. Two players who know the correct strategy to chess and Go need never play. Of course, the correct strategy is a bit less compact.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Take the last chip
« Reply #24 on: May 23^{rd}, 2005, 2:21pm » 
Quote Modify

Well, I'd say, certainly in this game, skipping to the end may be preferred over actually playing it. Especially if you start with numbers like n=2^321 At least you can finish go in a day


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



