Some Chip Transfer Games
Thomas S. Ferguson
Abstract:
Four related impartial combinatorial games are investigated. The
first game is called Empty & Transfer . Given k boxes
each containing at least one chip, a move consists of emptying a box
and transferring to it at least one chip, but not all chips, from one of
the other boxes. Players move alternately and play continues until
no more moves are possible. Under the normal ending rule, the last
player to move wins; under the misère rule, the last player to
move loses. The normal form of this game is solved for k<5. For
k=2, the Sprague-Grundy function is found. The second game is
called Empty-All-But-One . A move consists of emptying all
but one of the boxes and transferring chips from the remaining box
so that there is at least one chip in each box. The third game is
called Empty & Redistribute . A move empties only one
box but the chips in the remaining boxes may be redistributed among
all boxes in an arbitrary manner. These Two games are solved for
arbitrary k in both normal and misère forms. The last game
is called Entropy Reduction . Two boxes are chosen and made
more nearly equal in size by transferring chips from one box to the
other. This game is solved for k=3 in both the normal and the
misère versions.