Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is essentially a question about counting nonintersecting short paths in a cubic lattice, but with a twist. (One constraint that I did not make clear below is that when to turn is already chosen: after you have made the $n$th choice of perpendicular direction, you go a predetermined integer distance $a_n$ in that direction before making the next orthogonal turn. For a given $n$ and sequence $a_n$ of positive integers, I want to know how many paths there are.) Specifically I am wondering what combinatorial means there are to ensure counting paths that don't cross themselves. To focus efforts, I will describe a puzzle.

Take an integral brick ($3\times3\times3$ inspired this question) to be cut up in unit cubes. Choose a Hamilton path which visits every unit cube once, and then cut into unit cubes, drill a hole through all but two of them in a certain fashion, thread them with a rubber band, and then reassemble so that the rubber band nicely traverses the chosen hamilton path. (If you actually build one out of wood, I recommend two-coloring the cubes so that the path goes through alternating colors of cubes.) Congratulations! You now have a snake puzzle!

In the construction of this, you will usually have cubes with bends (the hole enters through one face and exits an adjacent face) and maybe cubes without (enter a face and either leave through the opposite face or don't leave). If $b$ is the number of cubes with bends, you can twist the configuration next to a bend to get up to four possible orientations of one part of the snake to the other. So there are up to $4^{b-1}$ possibilities in theory for reshaping the snake, of which one of these is an integral brick.

But not quite. The cubes are solid and only one of them can occupy a given lattice point; we count only feasible configurations where each cube is on a lattice point. Further, the band can take a lot of twisting but not much stretching: it must make a nice Hamilton path through the configuration of adjacent cubes and not change the order in which the cubes are visited. Finally those cubes without bends (there are $a_n - 1$ of them after the $n$th bend and before the next bend) serve a geometric but not combinatoric function directly: You can spin the cubes around the band and not affect the configuration. If the original path passed straight through a cube however, every feasible configuration will have a $1$ by $3$ (or longer) subsegment involving that cube. Likewise cubes that were bends in the path remain as bends in every feasible configuration. Let me not forget that the cubes are axis aligned and adjacent in each configuration.

Is there a way to count how many feasible configurations there are in such a puzzle? Once $b$ reaches $3$, there are possibilities for self intersection, so one does not get all $16$ possibilities sometimes. For the $3\times3\times3$ brick, which paths produce the largest (smallest) number of configurations, up to rotational and reflectional symmetry? Note that the band is flexible enough that I assume cubes pass through (or around) one another in moving from one feasible configuration to the next. As above, I am interested in the combinatorial technique that eliminates or accounts for the infeasible configurations that are tantamount to self-intersecting lattice paths.

Pointers to the literature are welcome, even to minor variations on this puzzle.

share|improve this question
    
"Choose a hamilton path which visits every unit cube once...." I am familiar with Hamiltonian paths as a concept in graph theory, but you haven't described a graph. –  Gerry Myerson Jun 12 at 7:08
    
@GerryMyerson: His graph appears to connect each cube to its up-to 6 face-to-face neighbors. –  Joseph O'Rourke Jun 12 at 11:34
1  
OEIS A096969 counts the "number of ways to number the cells of an $n \times n$ square grid with $1,2,3,\ldots,n^2$ so that successive integers are in adjacent cells." That seems to count the Hamiltonian paths except on $\mathbb{Z}^2$ rather than $\mathbb{Z}^3$. –  Joseph O'Rourke Jun 12 at 11:57
1  
Self-avoiding walks in a cubic lattice have been studied but I haven't found an explicit count. Here is one place where such a count might be recorded were it available. –  Joseph O'Rourke Jun 12 at 11:58
    
@Gerry, sorry for the lack of clarity. Joseph has the idea: let G be a grid graph or subgraph of N^3 lattice graph containing a rectangular region of vertices, a times b time c, and choose a hamilton path through G, which path will be reshaped in certain ways later. The object corresponding to this path is the cube and rubber band construction I call a snake, which will fold up into an a by b by c integral brick. –  The Masked Avenger Jun 12 at 15:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.