The manager of the local sweetshop, one Minty Ball, has announced a grand closing down sale. They sell $n$ varieties of sweets: toffees, sherbets, fudge, and so on. Let's just call the varieties $V_1,\dots,V_n$.
On the final day of the sale, Minty Ball announces the ultimate prize: the lease on the premises will pass to whoever manages to eat the last sweet left in the shop. Half the population of the town scrambles down there to buy sweets. One local magnate tries to buy all the sweets in the shop, but Minty Ball tells him that certain rules are in place, as follows.
Each purchase must consist only of sweets of one variety. You can buy as many toffees as you want in one go, from just one to all of them, but you can't buy both a toffee and a sherbet at the same time.
Every time you make a purchase, you have to eat all the sweets you've bought. You can't just stuff them in your pocket and make another purchase.
After hearing about these rules, the crowd thins. Few people want to make themselves sick by gorging on sweets. But the prices are good, so many people buy single packets of sweets and leave. One or two keep on buying, eating, and buying again in the hope of staying all the way to the last sweet.
Finally there are only two shoppers left: Rand and Gamow. Both are hungry for the ultimate goal of eating the final sweet. At this point there are $S_i$ sweets of type $V_i$ remaining for each $i$. The two hopefuls, having eliminated all competition, agree that they will take turns to make a purchase. Gamow is the later arrival of the two; he has eaten fewer sweets over the course of the day but has been gorging himself in the last couple of hours, so he allows Rand to make the first purchase.
For what values of $n,S_1,\dots,S_n$ can Rand be the one to take the final sweet?
Assume that both Rand and Gamow have sufficient money to make all the purchases they need, and that neither is worried about making himself sick by eating too many sweets. All they care about is to take over the sweetshop premises and start their own business there.
Answer
This game is the famous NIM game: http://en.wikipedia.org/wiki/Nim
The game has been fully analysed at the end of the 19th century. It has been discussed in some of the Martin Gardner books and in many other books on recreational mathematics. It might be the most popular mathematical game known all over the world. Google shows 300.000 pages that describe the solution strategy for NIM. It is virtually impossible to find a puzzle-lover who has never seen the NIM game and its winning strategy before.
Translate the values $S_1 , \ldots, S_n$ into binary, and compute their XOR (which is also known as NIM-sum). You win the game, if you always leave an XOR value zero.
The wikipedia says that the name NIM was coined by Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The name is probably derived from the German word "nimm" meaning "take [imperative]", or the obsolete English verb nim of the same meaning.
The only new contribution of the above puzzle is the story around the game.
No comments:
Post a Comment