Die-rolling Hamiltonian cycles - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T02:40:03Z http://mathoverflow.net/feeds/question/87437 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87437/die-rolling-hamiltonian-cycles Die-rolling Hamiltonian cycles Joseph O'Rourke 2012-02-03T14:07:55Z 2012-02-27T03:13:49Z <p>Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$, each of whose unit squares is labeled with a number in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$. Say that such a labeled $R$ is <em>die-rolling Hamiltonian</em>, or simply <em>rollable</em>, if there is a Hamiltonian cycle obtained by rolling a unit die cube over its edges so that, for each square $s \in R$, the cube lands on $s$ precisely once, and when it does so, the top face of the cube matches the number in $s$. For example, the $4 \times 4$ "board" shown below is rollable. <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/DiceRolling.jpg" alt="Dice Rolling" /> <br /></p> <blockquote> <p><b>Q</b>. Is it true that, if $R$ is die-rolling Hamiltonian, then the Hamiltonian cycle is unique, i.e., there are never two distinct die-rolling Hamiltonian cycles on $R$?</p> </blockquote> <p>This "unique-rollability" question arose out of a problem I posed in 2005, and was largely solved two years later, in a paper entitled, "On rolling cube puzzles" (complete citation below; the $4 \times 4$ example above is from Fig. 17 of that paper). Although the original question involved computational complexity, the possible uniqueness of Hamiltonian cycles is independent of those computational issues, so I thought it might be useful to expose it to a different community, who might bring different tools to bear. It is known to hold for $R$ with side lengths at most 8. If not every cell of $R$ is labeled, and unlabeled cells are forbidden to the die, then there are examples with more than one Hamiltonian cycle.</p> <p><b>Edit1</b>. Rolling a regular tetrahedron on the equilateral triangular (hexagonal) lattice is not as interesting. See the Trigg article cited below.</p> <p><b>Edit2</b>. Serendipitously, <em>gordon-royle</em> posted a perhaps(?) relevantly related question: "<a href="http://mathoverflow.net/questions/87496/" rel="nofollow">Uniquely Hamiltonian graphs with minimum degree 4</a>."</p> <hr /> <ul> <li> The computational version is <a href="http://cs.smith.edu/~orourke/TOPP/P68.html#Problem.68" rel="nofollow"> Open Problem 68</a> at <a href="http://cs.smith.edu/~orourke/TOPP/" rel="nofollow">The Open Problems Project</a>. </li> <li> "On rolling cube puzzles." Buchin, Buchin, Demaine, Demaine, El-Khechen, Fekete, Knauer, Schulz, Taslakian. <em>Proceedings of the 19th Canadian Conference on Computational Geometry</em>, Pages 141–144, 2007. <a href="http://people.csail.mit.edu/schulz/papers/RollingFull.pdf" rel="nofollow">PDF link to full paper.</a> </li> <li> Charles W. Trigg. "Tetrahedron rolled onto a plane." <em>J. Recreational Mathematics</em>, 3(2):82–87, 1970. </li> </ul> http://mathoverflow.net/questions/87437/die-rolling-hamiltonian-cycles/89493#89493 Answer by domotorp for Die-rolling Hamiltonian cycles domotorp 2012-02-25T16:08:54Z 2012-02-27T03:13:49Z <p>UPDATE: I played around and came up with a construction (chance of containing a mistake is high!), below it I leave my original answer for explanation.</p> <p>$\begin{array}{ccccccccccccccccccccccccc} 3&amp;-&amp;2&amp; &amp;2&amp;-&amp;1&amp;-&amp;5&amp;-&amp;6&amp; &amp;5&amp;-&amp;1&amp;-&amp;2&amp;-&amp;6&amp;-&amp;5&amp;-&amp;1&amp;-&amp;2\cr |&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|\cr 1&amp; &amp;1&amp; &amp;3&amp; &amp;4&amp;-&amp;5&amp;-&amp;3&amp; &amp;4&amp; &amp;1&amp;-&amp;4&amp;-&amp;6&amp;-&amp;3&amp;-&amp;1&amp;-&amp;4\cr |&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; \cr 4&amp; &amp;5&amp; &amp;5&amp; &amp;1&amp;-&amp;5&amp;-&amp;6&amp;-&amp;2&amp; &amp;5&amp;-&amp;4&amp;-&amp;2&amp;-&amp;3&amp;-&amp;5&amp;-&amp;4\cr |&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|\cr 6&amp; &amp;6&amp;-&amp;4&amp; &amp;6&amp;-&amp;3&amp;-&amp;1&amp;-&amp;4&amp;-&amp;6&amp;-&amp;3&amp;-&amp;1&amp;-&amp;4&amp;-&amp;6&amp; &amp;6\cr |&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|\cr 3&amp; &amp;2&amp;-&amp;4&amp;-&amp;5&amp; &amp;4&amp;-&amp;2&amp; &amp;5&amp;-&amp;6&amp;-&amp;2&amp; &amp;2&amp;-&amp;4&amp; &amp;5&amp; &amp;3\cr |&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 1&amp; &amp;1&amp; &amp;1&amp;-&amp;5&amp;-&amp;6&amp; &amp;6&amp; &amp;3&amp;-&amp;6&amp; &amp;3&amp;-&amp;1&amp; &amp;1&amp; &amp;1&amp; &amp;1\cr |&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 4&amp; &amp;5&amp; &amp;3&amp; &amp;2&amp;-&amp;3&amp; &amp;5&amp;-&amp;3&amp;-&amp;2&amp; &amp;3&amp;-&amp;5&amp; &amp;3&amp; &amp;2&amp; &amp;4\cr |&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 6&amp; &amp;6&amp; &amp;6&amp; &amp;6&amp; &amp;6&amp;-&amp;5&amp;-&amp;1&amp;-&amp;2&amp;-&amp;6&amp; &amp;6&amp; &amp;6&amp; &amp;6&amp; &amp;6\cr |&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 3&amp;-&amp;2&amp;-&amp;4&amp;-&amp;5&amp;-&amp;3&amp;-&amp;2&amp;-&amp;4&amp;-&amp;5&amp;-&amp;3&amp;-&amp;2&amp;-&amp;4&amp;-&amp;5&amp;-&amp;3\cr |&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|\cr 1&amp;-&amp;2&amp;-&amp;6&amp;-&amp;5&amp;-&amp;1&amp;-&amp;2&amp;-&amp;6&amp;-&amp;5&amp;-&amp;1&amp;-&amp;2&amp;-&amp;6&amp;-&amp;5&amp;-&amp;1\cr |&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 4&amp; &amp;4&amp; &amp;4&amp; &amp;4&amp; &amp;4&amp;-&amp;5&amp;-&amp;3&amp;-&amp;2&amp;-&amp;4&amp; &amp;4&amp; &amp;4&amp; &amp;4&amp; &amp;4\cr |&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 6&amp; &amp;5&amp; &amp;1&amp; &amp;2&amp;-&amp;1&amp; &amp;5&amp;-&amp;1&amp;-&amp;2&amp; &amp;1&amp;-&amp;5&amp; &amp;1&amp; &amp;2&amp; &amp;6\cr |&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 3&amp; &amp;3&amp; &amp;3&amp;-&amp;5&amp;-&amp;4&amp; &amp;4&amp; &amp;1&amp;-&amp;4&amp; &amp;1&amp;-&amp;3&amp; &amp;3&amp; &amp;3&amp; &amp;3\cr |&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp;|\cr 1&amp; &amp;2&amp;-&amp;6&amp;-&amp;5&amp; &amp;6&amp;-&amp;2&amp; &amp;5&amp;-&amp;4&amp;-&amp;2&amp; &amp;2&amp;-&amp;6&amp; &amp;5&amp; &amp;1\cr |&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|\cr 4&amp; &amp;4&amp;-&amp;6&amp; &amp;4&amp;-&amp;1&amp;-&amp;3&amp;-&amp;6&amp;-&amp;4&amp;-&amp;1&amp;-&amp;3&amp;-&amp;6&amp;-&amp;4&amp; &amp;4\cr |&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|\cr 6&amp; &amp;5&amp; &amp;4&amp; &amp;3&amp;-&amp;5&amp;-&amp;4&amp;-&amp;2&amp; &amp;5&amp;-&amp;6&amp;-&amp;2&amp;-&amp;1&amp;-&amp;5&amp;-&amp;6\cr |&amp; &amp;|&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; \cr 3&amp; &amp;3&amp; &amp;1&amp; &amp;6&amp;-&amp;5&amp;-&amp;1&amp; &amp;6&amp; &amp;3&amp;-&amp;6&amp;-&amp;4&amp;-&amp;1&amp;-&amp;3&amp;-&amp;6\cr |&amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp;|&amp; &amp;|&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;|\cr 1&amp;-&amp;2&amp; &amp;2&amp;-&amp;3&amp;-&amp;5&amp;-&amp;4&amp; &amp;5&amp;-&amp;3&amp;-&amp;2&amp;-&amp;4&amp;-&amp;5&amp;-&amp;3&amp;-&amp;2 \end{array}$</p> <p>HOW THIS THING WORKS:</p> <p>I think there are configurations that are not uniquely Hamiltonian. The example I have in mind should be around 14 times 14, except that I do not have a definite example, but I hope I can convince you that only a technical difficulty is missing.</p> <p>Our goal is to prove a somewhat stronger statement, to exhibit an R that has two different die-rolling H-cycles in which the cube is in the same position over every field no matter which H-cycle you take. This allows us to define a nice graph on R. First we will give one H-cycle, then add the edges not contained in this H-cycle along which the cube could move, only allowing moves that take the cube into the same position over the field as it would have in the H-cycle. Denote the obtained graph by G. It is easy to see that G is a subgraph of the grid-graph, moreover, G cannot have cycles whose length is less than 10 and G has (at least) two H-cycles.</p> <p>One such graph is given below on the 13 times 10 grid (130 vertices). Legend: X marks the squares contained in both H-cycles, while 1 and resp. 2 the squares contained in only one of them.</p> <p>$\begin{array}{ccccccccccccc} %<br> X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X\cr X&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;X\cr X&amp; &amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp; &amp;X\cr X&amp; &amp;X&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;X&amp; &amp;X\cr 1&amp;1&amp;1&amp;1&amp;X&amp;X&amp;X&amp;X&amp;X&amp;2&amp;2&amp;2&amp;2\cr X&amp; &amp;X&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;X&amp; &amp;X\cr X&amp; &amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp; &amp;X\cr X&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;X\cr X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X&amp;X\ \end{array}$</p> <p>Unfortunately this graph is not yet good enough, we cannot give a good numbering of R to make the edges valid. However, we can play around (i.e. make more wiggly using more area) with the top and bottom parts (shared by both H-cycles) and I am sure that way we can ensure the validity of all edges. This is the only missing part which seems to be only technical.</p>