# The Game of Nim alternative solutions

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 .

-
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
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

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.

-
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.
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.