In the Drive Ya Nuts puzzle, we are given $7$ hexagonal nuts, whose edges have been numbered from $1$ to $6$. Each nut uses all $6$ numbers. The aim of the puzzle is to place all the nuts in a hexagonal grid, so that touch sides are numbered the same. In the marketed puzzle, there is a unique solution, provided that solutions arising from rotations of the entires grid are regarded as identical. (This is easy to confirm. There are only $7$ ways to place the nuts in the grid, and since rotations don't matter, we can assume the central hexagon has the $1$ on the north. There is then only one possible orientation for each of the outer hexagons, and we just have to check if they lead to a solution.)
I wonder how many possible puzzles of this type have the attractive property of having a unique solution. That is, how many sets of $7$ different numbered hexagons give a puzzle with a unique solution? We can represent a hexagon by listing it numbers in clockwise order. Since rotating a nut gives the same nut, we always start with the $1$. Also, since permuting all the labels does not essentially change the puzzle, we may assume that $123456$, which I will call the "unit", for want of a better term, is always one of the nuts.
I'm confident that I can find all such essentially different sets. We may assume that the central hexagon is the unit, oriented with $1$ on top. Now if we look at the $6$ edges radiating out from vertices of the unit, each is constrained to have one of $4$ possible labels, or we would have a hexagon with two sides labeled the same. For the same reason, no two consecutive "spokes" can have the same label. Brute force calculation shows there are $1144$ possible labelings. Once we have such a labeling, each of the outer hexagons has $3$ unlabeled sides, which may be labeled in $3!$ ways, so we have $$1144\cdot6^6=53,373,464$$ positions with at least one solution. Many of these will be relabelings of other such positions, so by generating the positions, keeping track of the ones seen, and rejecting isomorphs, I think testing them all will be quite feasible. (Obviously, I will use backtrack rather than generating all $5040$ positions.)
My problem is relating this answer to the number of possible puzzles. The possible number of nuts is $5!$=120, so the possible number of nut sets is $${119\choose6}=3,470,108,187$$ However, this ignores the, fact that some of these are just relabelings of others. We are only interested in permutations of the numbers that result in a set containing the unit. If we pick any of the nuts, we can replace any of its labels by $1$, the next label in clockwise order by $2$, and so on. This gives $42$ possible permutations for a given nut set.
My problem is figuring out what nut sets are invariant under which permutations. By what has gone before, the only permutations that might leave a nut set invariant are $6$-cycles or $5$-cycles. My instinct is that no $5$-cycle will work, but I don't know how to prove it. Part of what confuses me is that we have to take account of the canonical forms. Let us apply the permutation $$\sigma={1\,2\,3\,4\,5\,6\choose2\,3\,4\,5\,6\,1}$$ to the hexagon $\tau=132465$. We get successively $$\begin{align}\tau&=132465\\ \sigma\tau&=243516\\ \sigma^2\tau&=354321\\ \sigma^3\tau&=465132 \end{align}$$ Notice that $\sigma^3\tau$ is just a rotation of $\tau$, so $\sigma^3\tau=\tau.$
I've thought of Polya's theory of counting, of course, but I can't see how to apply it. I feel that there is probably a simple way of attacking this problem, but I just don't see it. Alternatively, am I making things difficult by requiring that the unit be part of the set? Would it somehow be easier to remove this requirement?
I can of course, compute the orbits of all $5$- and $6$-cycles
Any direction or assistance will be appreciated.
EDIT
I can prove that no $5$-cycle leaves any nut set invariant.
The length of an orbit must divide the order of a cycle, so that the orbits of a $5$-cycle $\sigma$ have length $1$ or $5$. If an orbit has length $1$, say $\tau=\sigma\tau$ then $\sigma$ rotates $\tau$, but this is impossible, since $\sigma$ leaves an element fixed. It is impossible to account for all $7$ elements of the nut set using only orbits of length $5$.
$\endgroup$ 14 Reset to default
