Author |
Topic: Take the last chip (Read 2931 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
Take the last chip
« on: Dec 25th, 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 30th, 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 25th, 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 25th, 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 25th, 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 (n-1). 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 25th, 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 25th, 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 25th, 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 28th, 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 one-row 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 4th, 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 = n-1; 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 (2ab, c), where a, b, c, are integers, a > 0, b >= 0, and c < 2a 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://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New (?) Take the last chip
« Reply #7 on: Jan 4th, 2003, 2:12pm » |
Quote Modify
|
p.s. My answer agrees with towr's. I didn't read his before posting.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
That Don Guy
Guest
|
|
Re: New (?) Take the last chip
« Reply #8 on: Feb 13th, 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 "2-chips", each one equal to 2 chips. If there are an odd number of 2-chips, the first player takes 1 2-chip (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 2-chips), use 4-chips instead of 2-chips; if there are an even number of those, use 8-chips, 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 "2N-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 "4-chips", so the first player takes 4.
|
|
IP Logged |
|
|
|
martin chase
Newbie
Posts: 2
|
 |
Re: New (?) Take the last chip
« Reply #9 on: Sep 5th, 2004, 12:37am » |
Quote Modify
|
on Dec 25th, 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 17th, 2005, 4:01am » |
Quote Modify
|
on Dec 25th, 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 two-digit 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 17th, 2005, 6:55am » |
Quote Modify
|
on May 17th, 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: 7526
|
|
Re: New (?) Take the last chip
« Reply #12 on: May 17th, 2005, 8:37am » |
Quote Modify
|
on May 17th, 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 17th, 2005, 9:07pm » |
Quote Modify
|
on May 17th, 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 two-digit 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 2k, with m < 2k. 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 < 2k. 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 2k+1 i + 2k with m > 2k, so for the next move we remove 2k chips, leaving 2k+1 i chips, and 2k < 2k + 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 2k, you have to take away at least 2k chips.
|
| « Last Edit: May 17th, 2005, 9:08pm by Deedlit » |
IP Logged |
|
|
|
brandi
Guest
|
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 19th, 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 23rd, 2005, 3:24am » |
Quote Modify
|
on May 17th, 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 23rd, 2005, 3:40am » |
Quote Modify
|
on May 17th, 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 23rd, 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 2k > 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, 2j 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 2k, then we have to take away a number of chips divisible by 2k. So there's no way of getting around it.
|
|
IP Logged |
|
|
|
asterex
Guest
|
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 23rd, 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 23rd, 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 23rd, 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 23rd, 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 23rd, 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^32-1
At least you can finish go in a day 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print