Chocolate is love <3
In this game of Poisoned Chocolates there are 5 stacks with 4 , 3 , 1 , 7 , 1 1 pieces of perfectly safe chocolate respectively. Underneath the 5 stacks, there is a large bar of poisoned chocolate.
You alternate turns with an opponent; each turn, the player on the move can eat as many of the chocolate pieces as they want (but at least 1 ) from one of the stacks, but they cannot take from multiple stacks on the same move . If (at the start of a player's move) the stacks are gone, the current player is forced to eat the poisoned chocolate and loses.
If you're the first player, can you win this game (assuming optimal play on both sides)?
Bonus : Generalize this.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
7 solutions
Perhaps also add what the winning move(s) are. It's not clear if the Nim score is 0010 or 1010 and in the latter case there is only one winning move.
Log in to reply
The Nim score is 1 0 1 0 2 in binary, or 1 0 in decimal.The first player's winning move is to take 1 0 chocolates from the pile containing 1 1 , leaving piles of 4 , 3 , 1 , 7 , 1 (this position has a Nim score of 0 ). What the subsequent moves are depend on the plays made by the opponent. You should try a few options, and see how/that it works as I have described.
Log in to reply
What happens if the opponent takes 5 from the pile of 7 (leaving 4,3,1,2,1)? How will the first player be able to make a Nim score of 0?
Log in to reply
@Joshua Lowrance – Take 3 from the 4 pile, leaving 1 , 3 , 1 , 2 , 1 , which has a Nim score of 0 .
@Joshua Lowrance – I might add that if you read (find it online) the proof of the strategy for Nim, you will find that the proof provides a method for working out what move works in each case.
I guess having a Nim score of 10 and removing 10 chocolates from the biggest pile is just a coincidence. Can someone come up with a strategy for making the Nim score 0 either in binary or decimal. I do have one which works with binary but only upto 3 stacks.
Log in to reply
My solution, which is the standard one, and which works for any number of stacks, is based on bitwise addition modulo 2 , which is in binary. If you look on the Internet for proofs of this standard Nim strategy, you will find a method for finding the correct move at each stage.
What I understand to be the strategy is that you calculate the nim score for the set of stacks, you then bitwise xor that score with the number from each stack individually. Whichever one results in a number less than what's in the stack, you remove the difference for that stack. In the example case, with a nim score of 10, only the 11 stack is greater than 10 xor itself, and results in 1 so you remove 10 from the stack to make it 1 as the first player. I think it is a coincidence that they're both 10.
Keep in mind that the arithmetic is bitwise. One can subtract (8 + 2) or one can subtract (8-2) from the largest pile. The generalization would be: if 2^k is the largest power of 2 in the bit score, there will be at least one pile with at least 2^k chocolates. For 2^l part of the bit score with l < k, if 2^l is part of the binary expansion of that pile, add 2^l to the amount taken away from that pile, otherwise, subtract 2^l from the amount taken away from that pile.
For example, if the Nim score is 37 = 32 + 4 + 2 + 1, and there is only one pile with at least 32 chocolates in it, and it has 45 chocolates in it, since 45 = 32 + 8 + 4 + 1, one removes 32 + 4 - 2 + 1 = 27 from this pile.
The question is quite simple, to work it out you add each of the numbers. 11+7+1+3+4 = 26. Because 26 is we can assign player 1 even numbers and player 2 odd numbers. As such the last safe chocolate is eaten by player 1 and player 2 is to eat the poison.
The sum is not enough information to conclude which player wins. Study Mark Henning‘s solution to learn why.
I believe it's very simple. Since on each turn you can eat (at least 1) but as many as you want from a stack. I'll argue that optimum play would be to force yourself to win, which would be eating all chocolates from any stack.
For even number of stacks : Regardless of what first player does (including optimum move) second player would always eat all the chocolates in any stack (optimum move) this would make all stacks empty on first player's turn. So first player loses.
For odd number of stacks : First player will always win by playing optimum move (eating all chocolates in any stack), second player can never win even if they make the optimum move on each turn.
Number of stacks is the key variable here, not the number of chocolates, or number of chocolates eaten on a turn. Interesting would be to generalize this for k number of players.
So this game is kind of rigged, as long as you choose your turn carefully by checking how many stacks are there, you can never lose.
Consider this explicit example: 2 stacks with each 1 chocolate. Clearly player 2 wins. With 2 stacks and the first one 1 chocolate and the second one 2 chocolates, however, clearly player 1 wins.
Yes but your opponent can always choose to leave one nonpoison chocolate in the stack effectively changing how many turns there are in the game.
this is my first explanation so it might be not a good explanation....
You want your opponent to eat the 3rd bar so you would play 3 then your opponent would eat the last one then play 3 and the opponent eats the 3rd bar then 6 then he plays 1 then 11 and he eats the poisoned bar.
Pretty simple. The number of stack is the real variable here not the number of chocolate in the stack. Another variable in the number of stack with only one chocolate Moreover, players can eat as much as chocolate as he wants so now three configuration
(1) there is an even number of stack and an even number of stack with only 1 chocolate.
Player 1 looses.
(2) there is an even number of stack and an odd number of stack with only 1 chocolate. Player 1 wins.
(3) there is an odd number of stack. Player 1 wins.
Explanation.
Your have to simplify the problem as follow the goal is for player 1 to bring player 2 in a loosing combination. Now let us come back to every configuration and simplify them.
(1) Let us take the example where you have 2 stacks of which 2 have only one chocolate. In this case player 1 loose whatever he plays. Or if we have 2 stacks of which none has only one chocolate. In this case if (a) player 1 eats all the chocolate from.one stack player 2 just has to eat all chocolate from the leftover stack to win the game. If (b) Player 1 choose to eat all chocolate expect one then player 2 can do the same.on the leftover stack and so win the game (same combination as upper). If (c) player 1 eat X number of chocolate but that more than 1 is left on the stack then player 2 has just to eat X number of the leftover stack -- which by definition contains more than 1 chocolate. By doing so he come back to the same configuration as before.
(2) if there is 2 stacks of which one contains only 1 chocolate player 1 just has to left one chocolate left in the other stack. In doing so he wins the game.
(3) there is only 1 stack which contains any number of chocolate except 0. Player 1 just has to eat all chocolate to win. If now we have 3 stacks. There is two possibilities. (a) we have an even number of stack with only one chocolate. In this case players one has to eat every chocolate except one from any stack to win the party (back to combination 2). (b) we have an odd number of stack with only one chocolate. In this case in this case player 1 can either eat all chocolate either player 1 eats a full stack (back to combination 2). Or he eats a full stack with only one chocolate (back to combination 3). [N.B. any other move and player 2 wins because he become in combination 3]
Now you might wonder just how does this generalise? To win the player has to choose one of the strategy described upper based on the number of stack and the number of stack containing only one chocolate. Once this understood player can play everytime to come into one of the final move as described. By following the exact same strategy, the player is sure to win.
Your argument contains some subtle flaws which makes your solution invalid. In fact, the game actually depends on the exact number of chocolates in each stack.
An example that contradicts your solution is the following: 2 stacks - 2 chocolates in the first one and 3 chocolates in the second one. Your solution (1) states that player 1 would be losing. But in fact the opposite is true. If player 1 eats one chocolate from the 3 stack, player 2 is obviously losing.
The flaw in your argument (1, c) is that we don't necessarily "come back to the same configuration as before". In this example, after player 2 eats "X number of the leftover stack" we are no longer in a (1) situation.
There is a solution by Mark Hennings which explains the winning strategy if you are curious.
I thought I could solve this puzzle in an alternate way but then realised all of them were based on the assumption that the opponent will act only in some of the possible ways and ignored the other moves which he could make which could bring me in a position where I am going to lose whatever I do. Now I understand that you can win only if you have a nonzero score and on every move should reset it to zero. If you have a score of zero no matter what you do your opponent can bring it back to zero. However if your opponent is not aware of the concept of Nim score or makes a mistake then you can start winning it by making it zero. Another point which I think may be causing confusion is that in this example to change a Nim score of 10 to zero 10 chocolates needed to be removed but that is not always the case. For example three stacks having 16, 8, 3 chocolates would have a Nim score of 27 but the maximum number of chocolates one can remove is 16 so this does not work. If I am correct then to make any Nim score equal to zero we can only use binary method which I think is as follows. Correct me if I am wrong. 1. Write all the numbers in binary with the highest number on the top and then others below in descending order. 2. Look at the left most column and count the number of 1s in it. a. If there are an odd number of 1s go to step 3. b. If there are an even number of 1s come to the column immediately right to it and count the number of 1s and act accordingly. 3. Take the highest 1 in that column and change it to 0. 4. Go to the column right of this and count the number of 1s. a. If the number of 1s in that column is odd then make it even by changing 1 to 0 or vice versa and then move to the column right to it and count the number of 1s and just repeat the process. b. If there are even number of ones just move to the column on the right of that and count the number of 1s and repeat step 4. 5. Continue the process till you reach the right most column. In the end you should be left with even number of 1s or no 1s in each column.
On further thinking I think my solution though intunitive, was actually wrong.
The way I came to the solution was rather simple: Player 1 takes one safe chocolate first, thus reducing the total pool of safe chocolate by one. This means that player 2 will invariable get the last safe chocolate.
If player 1 takes 1 safe chocolate first he actually loses. This can be seen with the argument given by Mark Hennings.
This suggestion is based on the assumption that the opponent will be forced to take one at each turn which is not the case.
Its quite simple actually. The problem states that you may eat as many chocolates as you want. This means you can choose to eat zero chocolates. If you, player one, refuse to eat a chocolates the entire time, then this is how it CAN happen:
P1 = Player One P2 = Player 3
P1: Eats no chocolates
P2: Eats all chocolates in a stack
P1: Eats no chocolates
P2: Eats all chocolates in a stack
P1: Eats no chocolates
P2: Eats all chocolates in a stack
P1: Eats no chocolates
P2: Eats all chocolates in a stack
(Final Stack)
P1: Eats no chocolates P2: Eats all chocolates in a stack
This leaves player one to eat a chocolate, but at this point, player two had eaten all normal chocolates, causing player one to eat the poison chocolate and lose.
This is one way to make player one lose. It never said you have to eat a chocolate in your turn for the problem.
Log in to reply
I have rephrased the problem to exclude the possibility of choosing 0 chocolates. Otherwise, the question would not make sense as the game would not terminate.
We are playing the game of Nim here. The strategy for this game requires us to calculate the bitwise XOR sum of the numbers of pieces of chocolate in each stack. In other words, we convert the stack counts into binary, and then calculate the XOR sum of each place in the binary expansion, and then calculate the binary number so obtained. This is also known as performing bitwise addition modulo 2 .
For example, the stack sizes 4 = 0 1 0 0 2 , 3 = 0 0 1 1 2 , 1 = 0 0 0 1 2 , 7 = 0 1 1 1 2 and 1 1 = 1 0 1 1 2 have Nim score 1 0 1 0 2 = 1 0 , while the stack sizes 3 1 = 1 1 1 1 1 2 , 2 4 = 1 1 0 0 0 2 , 1 0 = 0 1 0 1 0 2 and 1 7 = 1 0 0 0 1 2 have Nim score 1 1 1 0 0 2 = 2 8 , while the stack sizes 7 = 1 1 1 2 , 6 = 1 1 0 2 and 1 = 0 0 1 2 have Nim score 0 0 0 2 = 0 .
The key point is this:
Plenty of proofs of these results can be foung on the Internet.
Thus a player is in a winning position if she is faced with a nonzero Nim score (she can always play, and present her opponent with a Nim score of zero, which means that either there is no safe chocolate left for her opponent to eat and she has won, or else her opponent must play and give her back a position with a nonzero Nim score.
Since the starting position for this game of Nim has a nonzero Nim score of 1 0 , the f i r s t player should win.