nim_balancing.txt

<title>A balancing algorithm</title>

<p>Locate the highest power of two, \(2^k\), that was unbalanced by removing stones from  one of the piles. Select any other pile that uses that power and remove that amount from the pile.  Balace the powers less than \(2^k\) by either subtracting smaller powers from the same pile or adding them. At most, \(1+2+\cdots+2^{k-1} = 2^k -1\) of the removed stones need be put back into the game, so the resulting move is legal.</p>

Example

Balanced:
	45 = 1     + 4 + 8 +   32
	29 = 1 +	 4 + 8 +16
		and other piles
		
If 7 stones are removed from the 45:
	38 =   2   + 4          +32
	29 = 1 +	 4 + 8 +16
		and other piles
		
	the 1's 2's and 8's are unbalanced in this move.
	
	8 is the highest power removed, so we remove 8 from 29, but 1 was also removed, while 2 as added.
Therefore, remove 8+1-2 = 7 from the 29.


Balance again:
	38 =   2   + 4          +32
	22 =   2   + 4  +16
		and other piles
Note that the 4's and 32's were not changed in this example, and there must be at least one
more pile that has 32 stones.