OK, maybe I am the last person to see this, but I have been keeping *way*too much state in keeping track of positions in this game. I've essentially been keeping track of a poset, and yesterday as I was walking to the T for my homeward commute, it occurred to me that most of that structure is completely irrelevant to the situation. Each disk has an upper surface and a lower surface; each surface is either available or engaged. A move consists of engaging two surfaces, a lower surface, and an upper surface somewhere below it. *All* you have to keep track of is the sequence of which direction the available surfaces point. Don't imagine moving the disks around, gluing them, and so forth: this is distraction. I imagine the disks as lain out side by side, smaller disks on the left, bigger ones on the right, tipped so their axes are horizontal. I represent an available left-pointing surface as a minus sign, and right-pointing ones as a plus sign. So the initial position in, say, the four-disk game would be "-+-+-+-+". But since the leftmost "-" can never be used, and likewise the rightmost "+", the position can be written as "+-+-+-". A move consists of deleting any plus-sign and any minus-sign to its right. Analysis is much easier in this formulation. I was able to verify the Nim sequence 0120123 for one through seven disks in about fifteen minutes by hand. There are other simplifications: of a cluster of adjacent identical, all choices are identical; a position of the form X++- can be simplified to X+-, and likewise +--X can be simplified to +-X. This rule can be generalized: any cluster of identical signs can be reduced to the number of opposite signs in the appropriate direction, so for example +++-+- can be reduced to ++-+-. Furthermore, any position can be inverted by reversing all the signs and writing it backwards. As a result, many options turn out to be identical, and don't require separate consideration. I fully expect that there are further simplifications, and some math-funster will find some way to calculate the Nim value of given positions more directly. My dictionary so far: +-: 1 +-+-: 2 ++--: 0 ++-+-: 0 +-+-+-: 0 ++-+--: 1 ++--+-: 1 +-++--: 3 ++-+-+-: 1 +-++-+-: 3 +-+-+-+-: 1 ++-+-+-+-: 2 +-++-+-+-: 2 +-+-++-+-: 1 +-+-+-+-+-: 2 +-+--++-+-: 0 +-+-+-+-+-+-: 3 On Thu, Apr 15, 2010 at 7:21 PM, Gareth McCaughan < gareth.mccaughan@pobox.com> wrote:
Apologies for the ludicrous line-breaks there. Apparently my mail program inserts line breaks according to where the lines happen to wrap in the window you're editing the message in. How bizarre.
Here's the exact same text with (I hope) more sensible line breaks.
On Thursday 15 April 2010 22:09:00 Allan Wechsler wrote:
With pen and paper I've managed to produce the Nim values for the game with between 1 and 6 disks. The values I get are almost certainly a mere tease: 0, 1, 2, 0, 1, 2. I don't expect that pattern to continue.
It apparently doesn't. A maximally-stupid program in a slow language gives me the following, for n from 0 upwards:
n | 0 1 2 3 4 5 6 7 8 9 A B C D --+---------------------------- | 0 0 1 2 0 1 2 3 1 0 3 2 4 1
The largest nim-value encountered in calculating that far is 6, which occurs e.g. for the position 0 1 2 36 4 5 7 8 9 A B (and not with any smaller number of discs).
Anyone want to check and/or extend this?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun