Re: [math-fun] Fwd: Sticky Towers of Hanoi
Alex Fink wrote (forwarded): << Sticky Towers of Hanoi is played with the disks of an n-disk ToH set (the pegs can be disregarded). In the initial position all of the disks are separate. In a general position there will be stacks of fused disks, with top radius and bottom radius differing. A move is to pick up a stack S and set it on another stack whose top radius exceeds the bottom radius of S; this causes the two disks that come in contact to fuse.
I'm at least as perplexed as Fred here. Where it says "In a general position there will be stacks of fused disks" does that mean each stack is entirely fused, or just that it consists of a stack of fused stacks? I don't see how the description of play can lead to anything but each stack being entirely fused, yet as Fred points out, that makes "solving" the puzzle all too obvious. (There is nothing about what constitutes a solution, so maybe that's where the confusion lies?) Perhaps Alex can clarify this? --Dan ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx
It's a game. You want to make it so the other guy has no move. You can fuse any pair of stacks so long as the sizes are descending up. Once a stack is joined, it stays joined. Disks of (1,2,3): winning move is join (1,3). No further move is possible. If instead you fuse (1,2), then the second player can create (1,2,3) and win. I second bringing Alex Fink in; I also enjoyed getting to know him. -tom On Sun, Apr 11, 2010 at 4:20 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Alex Fink wrote (forwarded):
<< Sticky Towers of Hanoi is played with the disks of an n-disk ToH set (the pegs can be disregarded). In the initial position all of the disks are separate. In a general position there will be stacks of fused disks, with top radius and bottom radius differing. A move is to pick up a stack S and set it on another stack whose top radius exceeds the bottom radius of S; this causes the two disks that come in contact to fuse.
I'm at least as perplexed as Fred here. Where it says "In a general position there will be stacks of fused disks" does that mean each stack is entirely fused, or just that it consists of a stack of fused stacks?
I don't see how the description of play can lead to anything but each stack being entirely fused, yet as Fred points out, that makes "solving" the puzzle all too obvious. (There is nothing about what constitutes a solution, so maybe that's where the confusion lies?) Perhaps Alex can clarify this?
--Dan
________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
[I'm expecting this to fail as a post to the mailing list. Fred, Dan, could one of you forward it if necessary?] On 11 April 2010 16:20, Dan Asimov <dasimov@earthlink.net> wrote:
Alex Fink wrote (forwarded):
<< Sticky Towers of Hanoi is played with the disks of an n-disk ToH set (the pegs can be disregarded). In the initial position all of the disks are separate. In a general position there will be stacks of fused disks, with top radius and bottom radius differing. A move is to pick up a stack S and set it on another stack whose top radius exceeds the bottom radius of S; this causes the two disks that come in contact to fuse.
I'm at least as perplexed as Fred here. Where it says "In a general position there will be stacks of fused disks" does that mean each stack is entirely fused, or just that it consists of a stack of fused stacks?
Each stack is entirely fused. I should've said that every stack automatically becomes fused: there are only separate fused stacks in the game, there's no circumstance in which a disk or stack gets put on top of another without fusing.
I don't see how the description of play can lead to anything but each stack being entirely fused, yet as Fred points out, that makes "solving" the puzzle all too obvious. (There is nothing about what constitutes a solution, so maybe that's where the confusion lies?) Perhaps Alex can clarify this?
Right. Like most of the games we were studying at the 2005 Banff workshop (BIRS is in Banff), this is a two-player game, not a single-player puzzle. The players take turns making fusing moves. Eventually someone will be left without a move, since no stack fits on another anymore. That player loses (this is the "normal play convention"; alternatively you could use the misère convention, by which that player wins). Thus, for example, if your move unifies all the disks into one (fused) stack, you win -- but most games don't end this way, since nonadjacent disks get stuck together. Alex
---------- Forwarded message ---------- From: Alex Fink <finka@math.berkeley.edu> Date: Apr 12, 2010 12:48 AM Subject: Re: [math-fun] Fwd: Sticky Towers of Hanoi To: math-fun <math-fun@mailman.xmission.com> Cc: Dan Asimov <dasimov@earthlink.net>, Fred lunnon <fred.lunnon@gmail.com> [I'm expecting this to fail as a post to the mailing list. Fred, Dan, could one of you forward it if necessary?] On 11 April 2010 16:20, Dan Asimov <dasimov@earthlink.net> wrote:
Alex Fink wrote (forwarded):
<< Sticky Towers of Hanoi is played with the disks of an n-disk ToH set (the pegs can be disregarded). In the initial position all of the disks are separate. In a general position there will be stacks of fused disks, with top radius and bottom radius differing. A move is to pick up a stack S and set it on another stack whose top radius exceeds the bottom radius of S; this causes the two disks that come in contact to fuse.
I'm at least as perplexed as Fred here. Where it says "In a general position there will be stacks of fused disks" does that mean each stack is entirely fused, or just that it consists of a stack of fused stacks?
Each stack is entirely fused. I should've said that every stack automatically becomes fused: there are only separate fused stacks in the game, there's no circumstance in which a disk or stack gets put on top of another without fusing.
I don't see how the description of play can lead to anything but each stack being entirely fused, yet as Fred points out, that makes "solving" the puzzle all too obvious. (There is nothing about what constitutes a solution, so maybe that's where the confusion lies?) Perhaps Alex can clarify this?
Right. Like most of the games we were studying at the 2005 Banff workshop (BIRS is in Banff), this is a two-player game, not a single-player puzzle. The players take turns making fusing moves. Eventually someone will be left without a move, since no stack fits on another anymore. That player loses (this is the "normal play convention"; alternatively you could use the misère convention, by which that player wins). Thus, for example, if your move unifies all the disks into one (fused) stack, you win -- but most games don't end this way, since nonadjacent disks get stuck together. Alex
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. On Sun, Apr 11, 2010 at 8:03 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
---------- Forwarded message ---------- From: Alex Fink <finka@math.berkeley.edu> Date: Apr 12, 2010 12:48 AM Subject: Re: [math-fun] Fwd: Sticky Towers of Hanoi To: math-fun <math-fun@mailman.xmission.com> Cc: Dan Asimov <dasimov@earthlink.net>, Fred lunnon <fred.lunnon@gmail.com
[I'm expecting this to fail as a post to the mailing list. Fred, Dan, could one of you forward it if necessary?]
On 11 April 2010 16:20, Dan Asimov <dasimov@earthlink.net> wrote:
Alex Fink wrote (forwarded):
<< Sticky Towers of Hanoi is played with the disks of an n-disk ToH set (the pegs can be disregarded). In the initial position all of the disks are separate. In a general position there will be stacks of fused disks, with top radius and bottom radius differing. A move is to pick up a stack S and set it on another stack whose top radius exceeds the bottom radius of S; this causes the two disks that come in contact to fuse.
I'm at least as perplexed as Fred here. Where it says "In a general position there will be stacks of fused disks" does that mean each stack is entirely fused, or just that it consists of a stack of fused stacks?
Each stack is entirely fused. I should've said that every stack automatically becomes fused: there are only separate fused stacks in the game, there's no circumstance in which a disk or stack gets put on top of another without fusing.
I don't see how the description of play can lead to anything but each stack being entirely fused, yet as Fred points out, that makes "solving" the puzzle all too obvious. (There is nothing about what constitutes a solution, so maybe that's where the confusion lies?) Perhaps Alex can clarify this?
Right. Like most of the games we were studying at the 2005 Banff workshop (BIRS is in Banff), this is a two-player game, not a single-player puzzle. The players take turns making fusing moves. Eventually someone will be left without a move, since no stack fits on another anymore. That player loses (this is the "normal play convention"; alternatively you could use the misère convention, by which that player wins). Thus, for example, if your move unifies all the disks into one (fused) stack, you win -- but most games don't end this way, since nonadjacent disks get stuck together.
Alex
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
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
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
participants (6)
-
Alex Fink -
Allan Wechsler -
Dan Asimov -
Fred lunnon -
Gareth McCaughan -
Tom Rokicki