On Friday, I mentioned Michael Albert's "Candy Nim" as a way to entertain yourself when you're losing a game of Nim.
The idea works as follows: you are in a losing Nim position (and the other player seems to know "the trick" to keep on winning). You decide to come up with a secondary goal: try to eat (take) as many of the remaining objects (pieces of candy) as possible. Michael proves that in this case, there is a way to eat at least half of the remaining objects!
Consider the case where there are two piles of objects, both with the same number (they have to be the same, otherwise you're not in a losing position). In this case, no matter how many you eat, the other player will take the same amount, and you'll eat exactly half the candy.
In some cases, there is a better "strategy". For example, if there are three piles, and one of them has size 1, then the other two must look like 2k and 2k + 1 for some k. Now, there is a way to net a 3-to-1 advantage in this situation: take 3 from the pile with 2k+1.
Then our piles go from: 1, 2k, 2k+1 to: 1, 2k, 2k-2. To counter this move, and not lose, the opposing player will take 1 from the second pile. The situation is now: 1, 2k-1, 2k-2 = 1, 2(k-1) + 1, 2(k-1). So long as k-1 isn't 0, lather, rinse, repeat! Continuing this leads to the losing player eating 3k+1 candies, while the winning player eats k+1 candies over the course of the game.
Are there any other good entertainment "games" you can play as a losing player?
Jokes from the Audience
4 days ago
Just wanted to correct a small error in the last post. You said: "He found interesting properties of the game when playing with three piles (most notably that it's always best to take candy from the biggest pile)."
ReplyDeleteActually, that's not correct -- what's interesting is that it's not always correct to take from the biggest pile.
What's even more interesting is that the three heap case already seems non-trivial to solve (though, as we all know, the meaning of "non-trivial" can change as soon as someone has a clever idea).
Someone just wrote a paper on candy nim.
ReplyDeletehttps://arxiv.org/abs/1805.07019