Nim (Part 2) - harder

So, how can you figure out the solution to the more complex 'nim' game? (See my previous post for info on the game).

It's actually amazingly simple (well - somewhat simple) but needs a bit of background in binary numbers to appreciate.

First, a reminder that a binary number is composed of a 'ones' column (the right-most digit in the number), then a 'twos' column, then a 'fours' column, etc, like below:

So this is 1 'four' plus 0 'two' plus 1 'one' = 5 (in decimal)

In decimal of course, we have the 'ones' column, 'tens' column, etc, like below:

And this would be 1 'hundred' plus 1 'one' = 101 (in decimal)

Now for the solution. All you do is write out the number of toothpicks in each pile in binary, one below the other. Then add up the columns to see whether each column is even (0, 2, 4, etc) or odd. Finally, if all column sums are even then we call the overall sum 'even'. Everything else will be 'odd'.

Two things that I will note (but not prove):
1. If the overall sum is 'even', then if you take 1 or more toothpicks from any pile you will make the overall sum 'odd'.
2. If the overall sum is 'odd', then there is always a way to take away from one pile so that you make the overall sum 'even'.

So if you can make the sum 'even' on your turn, you can also always do that on your next turn since your opponent will always make it 'odd' on their turn.

a) If you follow this strategy you will win the game where the last person to take a toothpick wins.

Here's an example with three piles of 3, 5 and 8 toothpicks respectively:

Pile 1 (3)	0	1	1
Pile 2 (5)	1	0	1
Pile 3 (8)	1	0	0
	Even	Odd	Even

If you take away 2 from pile 1 you change it from binary 011 to binary 001 and now the sum of all the columns is even. If you keep this up, you will always leave toothpicks in at least 2 piles until you force your opponent to take the second-last pile and you then take the last one.

b) If you are playing the more common version of nim where the person to take the last toothpick loses, then play as above until only one heap has a size of 2 or more. Then remove all toothpicks from the larger heap and you win.

Finally, if you are playing a version of the game where you can only take away up to 'k' toothpicks at a time, then first (in your mind) reduce the size of each heap modulo k + 1 (that is, remove all multiples of k + 1 until you just have a remainder that is between 1 and k). Assuming that you are playing the 'last person to take a toothpick loses' version, then:
- If this makes all the heaps of size zero just take k objects from one of the heaps.
-Otherwise, follow the above strategy 'a'.

This is just an intro to nim, but should be enough that the explanations you read elsewhere make sense (e.g. the wikipedia nim entry)

Nim (Part 1) - easy

Nim is "a game in which two players alternately take one or more objects from one of a number of heaps, each trying to take, or to compel the other to take, the last remaining object".

(This post looks at an 'easy' version of Nim and how to solve it. My next post looks at the solution to the harder variants.)

My first experience with Nim was the simple version ('easy') where you start with a pile of (say) 15 toothpicks. You are allowed to take away 1, 2 or 3 toothpicks in your turn and then it is the other player's turn. You continue taking turns until someone has to take the last toothpick (and they lose).

This type of game is pretty easy to analyze. You can see that if you leave your opponent 1 toothpick you win. And if you leave them 1+4 = 5 toothpicks you also win (since if there are 5 toothpicks and they take 'x', you just take '4-x' on your turn and that leaves 1...giving you the win). So the winning strategy is to leave your opponent with 1 + (some multiple of 4) in the pile. If the pile starts with 15 and you get to go first, take 2 (leaving 13 = 1 + 4(3)) and you are already in a winning position.

Finally, if you are allowed to take 'k' toothpicks on each turn, then just leave 1 + some multiple of (k+1) toothpicks and you win. (And if the rules are that you need to take the last toothpick yourself to win, then just leave 1 + some multiple of k.)

The next variant I had heard of (call it 'hard') extended this game to 3 piles. The version I played had piles of 3, 5 and 8. During your turn you can take 1, 2, or 3 toothpicks from any one pile. Again, the objective of the game was to leave your opponent with the last toothpick.

I'll leave the analysis of this to be a simple case of the 'hardest' case:

• you have any number of piles
• each pile has some number of toothpicks
• during your turn you can take any number of toothpicks from any one pile

What is the winning strategy?

I'll leave this to my next post...but it's actually a fairly easy(!) solution - if you're good at converting numbers to binary and then adding up columns to see if they are even or odd.

Specific Solutions for the Broken Combination Lock problem

So how to come up with an actual solution for an n x n x n cube? (Assume n is odd, it's easier/symmetrical if even). At a high level:

1. Pick a corner (let's say, starting at (1,1,1)) of a cube of size (n+1)/2 that is in a corner of the overall large cube), and solve according to below, then
2. Pick the 'opposite' cube (the opposite corner of the overall large cube - say, starting at ((n+1)/2,(n+1)/2,(n+1)/2)) which will be a cube of size (n-1)/2), and solve it as below too.
3. The combination is the total solution. 

So let's do it. Starting at one corner (for simplicity, assume (1,1,1) then keeping 'z' constant, for each guess add 1 to each of x and y a total of (n+1)/2 times (or (n-1)/2 times for the second cube...let's just call it 'N' for now).
Then add 1 to z and start x,y at x+1, y+0 from the starting point of your first guess at z=1. Continue adding 1 to each of x and y, 'rolling over' if you go over N.
Continue for each z until z= N, starting each level with x at 1 more than the previous level.
So for n=7, a solution is:
(1,1,1), (2,2,1), (3,3,1), (4,4,1),
(2,1,2), (3,2,2), (4,3,2), (1,4,2),
(3,1,3), (4,2,3), (1,3,3), (2,4,3),
(4,1,4), (1,2,4), (2,3,4), (3,4,4),
- the above handles the cube of size (n+1)/2
(5,5,5), (6,6,5), (7,7,5),
(6,5,6), (7,6,6), (5,7,6),
(7,5,7), (5,6,7), (6,7,7)
- handles the rest

Two notes initially:
1. The selection of an (x,y,z) covers all guesses (x,y,?), (x,?,z), and (?,y,z) where ? represents any value from 1 to n
2. The guess can be seen to be within a 'sub-cube' of m x m x m (where 'm' = max value of x,y,z).

(sidebar) To help viusalize, imagine initially that n is even, and you divide the cube into 8 equal 'sub-cubes' of size n/2 x n/2 x n/2 by cutting the larger cube along the lines of symmetry. (See below...also the second diagram in my previous post)

a) The selection of an (x,y,z) within a 'sub-cube' covers guesses in 4 of the 8 'sub-cubes' (the one in which the selection is made, plus the three others that contain the same 'x and y', 'x and z' and 'y and z'...in other words, the volume shown within the red lines above), but will never cover any guesses in the other 4 'sub-cubes' (symmetrical).
b) The minimum number of guesses to cover the selected 'sub-cube' (and the 3 other sub-cubes affected) must be equal to the area of one side of the 'sub-cube' (n/2)**2, since each guess can only cover one square in this cross-sectional area.
c) To complete the overall cube, you must also cover the other 4 'sub-cubes' that are 'opposite' from your first guesses. As noted, this can be done in (n**2 / 4) guesses by selecting the 'sub-cube' that contains (n/2+1,n/2+1,n/2+1) through (n,n,n). The selection of guesses in any other 'sub-cube' will, by definition, not complete the cube.

Now, back to the general proof. The 'sub-cube' selected (for your x,y,z guess) does not have to be of size n/2. In fact, the cube can be solved by solving any two 'sub-cubes' where one is of size 'i' (i<=n) (starting at 1,1,1 for simplicity) and the other of size n-i which is 'opposite' to the first 'sub-cube' within the large cube. In these cases, the same '3-dimensional L' visualization applies (although the big cube is not divided into 8 sub-cubes now, just 2 sub-cubes of different size plus the other volumes that get 'filled' as you solve each sub-cube). The solution is
S = solution for first sub-cube + solution for second sub-cube
 = i**2 + (n-i)**2
 = n**2 -2ni +2(i**2)
==> if n is even, this is optimal (minimum) at i=n/2

If n is odd (actually, even is just a special case of odd)
S = solution for first sub-cube + solution for second sub-cube
 = i**2 + (n-i)**2 (where i <> n-i)
 = n**2 -2ni +2(i**2)  (as before)
==> this is optimal (minimum) at |n-2i|=min, or in other words, when the two sub-cubes are closest in size.

This comes down to the familiar equations of
S = n**2 / 2   (for n=even)
S = (n**2+1) / 2  (for n=odd)

The Broken Combination Lock problem

(well...*one* of the broken bicycle lock problems)
(AKA rooks on a 3-D chessboard problem)

You have a combination bike lock of the type which has 3 rings, each with numbers 1 through 8. Normally with this kind of lock you have to line up 3 numbers in the right order to open it. The number of possible combinations is 8x8x8.

But, this lock is broken in such a way that you only have to match any 2 of the 3 numbers in order to open it. Obviously you could do it in 64 tries (8x8) by just using any 2 of the rings, but surely you can do better than that.

1. What is the minimum number of combinations you have to try to ensure that you can open the lock?

2. What is the general solution for a 3-ring lock 'broken' as above, but with 'n' numbers on each ring
 a) if 'n' is even?
 b) if 'n' is odd?

(This is the same type of problem as the 'rooks on a 3-dimensional chessboard'. It is known that N rooks may be placed on a 2-dimensional NxN chessboard so that every square is controled by at least one rook. What's the minimal number of rooks on 3-D chessboard NxNxN to meet this condition?)

One thing I found interesting was how to visualize this problem. Basically, you start with an 8 x 8 x 8 cube. Each guess at a combination 'cuts out' a line of 1 x 1 x 1 cubes in each of the 'x', 'y' and 'z' directions from the specific (x, y, z) cube selected. That is, if you select a cube - say (1,1,1) - then you are selecting all cubes that have the same x,y but a different z (the vertical bar in the diagram below), all cubes that have the same x,z but different y (the bar going into the page) and all cubes that have the same y,z but different x (the bar going left to right). Together, these make a '3-dimensional L' shape.

Here's a diagram (it's 4 x 4 x 4, but you get the idea).

In this case, you can see that all guesses where (say) x, y, z <= 2 will carve out a larger '3-dimensional L' shape.

So you only need to make guesses in the x, y, z <= 2, plus (from symmetry) guesses in the x, y, z >= 3 quadrant to complete the solution.

To help visualize, think of a 2 x 2 x 2 cube first. If you pick (1,1,1) and then (2,2,2) you make two '3-dimensional L' shapes that cover the entire cube.

Now looking at the 4 x 4 x 4 cube...the number of guesses you need to cover the x, y, z <= 2 quadrant cannot be less than 4 (the area of any 2 x 2 'end' to the 3-dimensional L). It's easy to see there are many solutions of 4 (more on this later), so the full solution is (2x2)x2 = 8. And for an 8 x 8 x 8 cube the answer is (4x4)x2 = 32.

For an n x n x n cube where n is even, this gives (n/2)(n/2)x2 = (n**2)/2.

If n is odd, a similar approach gives the solution (noting that the two quadrants you are selecting in should be as near to the median as possible, so for a 9 x 9 x 9 cube you could select 16 guesses in the x, y, z <= 4 quadrant, and 25 guesses in the x, y, z >4 quadrant.

For an n x n x n cube where n is odd, this gives ((n-1)/2)**2+((n+1)/2)**2 = (n**2+1) / 2

And finally, the reason that the two quadrants should be the same size (if n is even) and as close as possible to the same size (if n is odd) is simply because the (sum of the) products of the sides of the quadrant (i.e. the sum of the area of one side of each quadrant) is a minimum in that case. 'An exercise left to the reader' - though I can send you the math if you want. See also my next post.

Next post will look at how to generate specific solutions, and more on why you need to select these 3-dimensional L's as close in size as possible to each other to minimize the number of guesses needed in the solution.

And it is nowhere near to clear (to me) for n x n x n x n. More on that even later.