Suppose there is only one stack of coins and it's your turn, obviously you'll win.
If there are two stacks of coins and its your turn then what should you do... well lets make it easier still. Put the same number of coins in each stack, if there is only one coin in each stack, you'll loose but what if their are two? since the stacks are identical it doesn't matter which one you choose and no matter if you take 1 or both then you'll loose, in fact, a little thought will show that the way to win with two stacks of coins is to ensure your opponent is always left with equal size stacks.
But this game need not have 2 stacks, it can have any number, so one strategy is to ensure that all pairs of stacks are the same size when it is your opponent's go. Now that may not seem possible in most cases (e.g. if there are an odd number of stacks) but there is a little trick here: there are lot of stacks within stacks (that is any stack of 5 has stack(s) of 4 ,3,2,and 1 in it.. (in fact 32 stacks altogether!)) Keeping all possible sub stacks in pairs would certainly work because the whole game is broken up into a series of trivial sub games of the 2 stack variety, but there are so many substacks, and removing any coins will nearly always effect the balance of many pairs of substacks, this approach seems intractable. Well there maybe a usable compromise between defining a stack as the a whole pile of coins or as any sub pile. This is where we can use the power of 2's,.
If we can pair up substacks of as big a size as possible and then discount them from further comparisons, we'll significantly reduce reduce the number of pairings we have to do and impose some order on the proceedings. Effectively we will be considering non overlapping trivial (i.e. two equal stack) subgames, eliminating the biggest ones first. This will work because we are reducing the entire game to a series of these trivial subgames, all we have to do is ensure that there are always pairings of equal size substacks when it is our opponents go.
One way we could break up the stacks into substacks is say base 3 arithmetic, so a stack of 8 would be 2 stacks of three and 1 stack of 2... but pairing up substacks base three would be more complex than necessary, to see why try it with a sample set of stacks of say 8,6 and 3 coins... so base 2 is the way to go because there either is (1) or is not (0) a substack of a given size in an actual pile of coins. Lets look at the structure for a 8,6,3 game
8 6 3 pairs? ----------------- 8's 1 0 0 No 4's 0 1 0 No 2's 0 1 1 Yes 1's 0 0 1 NoOne way (there are often a few optimal moves) of evening up these pairs is to pick on the 8 coin stack: get rid of the 8, find another 4 and another 1. that is a net deficit of 3. So an optimal move is to take 3 coins from the 8 stack. The resulting configuration...
5 6 3 pairs? ----------------- 8's 0 0 0 Yes 4's 1 1 0 Yes 2's 0 1 1 Yes 1's 1 0 1 Yes...consists of pairs of trivial subgames, none of which our opponent could win. Writing a program to play this game is a great project for a competition or brighter students, as it is a non trivial exercise in logic. By looking at the problem in different ways in this case playing about with the substacks and the concept of the (trivial) games within the game. Here is another example
9 6 4 10 pairs? --------------------------- 8's 1 0 0 1 Yes 4's 0 1 0 0 No 2's 0 1 1 1 No 1's 1 0 1 0 Yeswe need to knock out a 4 and a 2, i.e. 6, and we can take 6 from the 9,6, or 10 columns so there are three optimal moves we can make in this case.
Bill Taylor
This page was created on 18 March 1995, last modified on 18 March 1995 and is supported by Bill Taylor