Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Nim has a mathematical solution which uses binary number system and addition modulo 2.I was wondering if there is an alternative solution to this game or at least another interpretation of the solution in binary numbers that will probably be less formal or easily understandable for someone who has little mathematical background .

share|improve this question
    
The theory of nim is simple and elegant, and well suited to practical play down the pub. If you find it too complicated, I'm afraid there is nothing simpler: you will just have to play for small stakes. –  TonyK Apr 1 '13 at 22:14
1  
Are you interested for your own understanding, or because you want to try to explain the solution to someone else who has little mathematical background? –  Brian M. Scott Apr 1 '13 at 22:25
    
Actually , I just want to explain its solution to someone who has no clue about mathematics. –  user1978522 Apr 1 '13 at 23:55

2 Answers 2

Yes, the solution of Nim in terms of binary numbers is a special case of the solution of impartial games in terms of minimal excluded ordinals (where you can replace "ordinals" by "non-negative integers" if you're only interested in finite games like Nim). The Sprague–Grundy theorem asserts that every impartial game is equivalent (in a well-defined sense) to a one-pile game of Nim with a certain number of counters (called a nimber), and the nimber for a position is the least non- negative integer that is not the nimber of one of the positions reachable by a move in that position. You can use this to solve a multi-pile game of Nim by successively determining the nimbers for the possible positions, and you can prove by induction that the resulting solution is the XOR solution.

share|improve this answer

I’ve taught the idea to students in a liberal arts math class, students with typically at most a rusty background in basic algebra, but over a period of two or three weeks. A good starting point is two-heap Nim: it’s not hard to understand that if you always play to leave your opponent heaps of the same size, you’ll win. Many of my students would discover that strategy on their own. We’d call such a position balanced, so that the winning strategy could be briefly expressed as leave your opponent a balanced position. The key idea, of course, is that any move from a balanced position must unbalance it, while any unbalanced position can be balanced with one move.

The next step $-$ and it’s a big one $-$ is to generalize this idea to more heaps. I never found a way to do this without bringing in binary notation in some form. Divide each heap into subheaps whose sizes are distinct powers of $2$ $-$ subheaps of binary size, for short $-$ and count the subheaps of each size. A position in two-heap Nim is unbalanced if some binary size occurs once and is balanced if each binary size occurs twice or not at all. At this point I’d suggest that the general notion of a balanced position might be one in which each binary size of subheap occurs an even number of times; the corresponding general notion of an unbalanced position would then of course be one in which some binary size occurs an odd number of times.

The hard part, of course, is showing in convincing fashion that it’s still true of these generalized notions of balanced and unbalanced positions that every move made from a balanced positions unbalances it, while from an unbalanced position there is always some move that balances it. The first of these isn’t actually all that hard. You can always imagine that the move is made by taking the largest subheap that isn’t too big, then the largest remaining one that isn’t too big, and so on, until either you’ve taken as many stones as you wanted, or the remaining subheaps are all too large; if anything does remain to be taken, take it from the largest remaining subheap. The binary size of the largest subheap affected by the move has then been unbalanced: exactly one subheap of that size has disappeared, and no new one can have been created.

Showing that you can always balance an unbalanced position in a single move is a little harder. The technique is to find the largest unbalanced binary size and pick a heap that has a subheap of that size. Now pick up that subheap and any other subheaps of that heap that have binary sizes that are unbalanced. Is the position balanced now? If so, you’ve found your move. If not, there must be some unbalanced binary sizes that weren’t represented in the heap in which you’re moving. Put back into that heap a subheap of each of those unbalanced binary sizes, and you’ve found your balancing move. The only possible worry is that you might not have enough stones to carry out the second half of the move, but since each binary size is one more than the sum of the smaller binary sizes, this isn’t actually a problem. (It helps to illustrate the process with real counters of some kind a few times.)

If your ‘victim’ is willing to think seriously about what you’re trying to explain, all that’s needed is a willingness to accept that any positive integer can be written as a sum of distinct powers of $2$, and that $2^n>\sum_{k=0}^{n-1}2^k$ for $n\in\Bbb Z^+$, though of course neither fact need be expressed so technically.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.