Posts Tagged ‘bipartite configurations’

Ups and Downs (and Deeps and Shallows) revisited

June 21st, 2013

hexcross

I would like to be able to report that I have produced a successful prototype of the crossed stick puzzle I described in a previous post. But I cannot. This photo is a lie. There are two configurations for this puzzle, for which I intended to use two copies of each of the six possible pieces with up/down binary slots:

hexcross-both

I say “intended to” because the puzzle appears to not be possible to solve. Specifically, the 0110 piece is rather intransigent for the configuration on the left, and it doesn’t seem possible to fit two of them in without changing the piece set. Which is indeed what I did to put together the solution shown at top. For the configuration on the right, 0101 is the problem piece.

Problem #41: Are there sets of pieces that can be assembled into both of the above figures? It would be ideal if all 6 possible pieces are present in at least one copy. (I’d have explored this manually, but for the other reason this prototype was a failure: the material was too thick for the width of holes I used, and a number of pieces snapped in the process of trying to assemble the above. So I am not able to test out whether I can make two different configurations with any piece set without running out of intact pieces.)

In crossed stick puzzles, we like for solutions to be “assemblable,” meaning that there is no cycle of pieces where each has a downward facing slot connected to the next piece and an upward facing slot connected to the previous piece. (If there were, there would be no piece you could place last.) The assemblability condition implies the existence of a partial ordering among the pieces, where the pieces are ordered according to which ones are “on top” of other pieces. It follows that that there must be at least one piece with all slots pointing up and one piece with all slots pointing down.

It turns out that the Star of David puzzle using a single set of these pieces, which I proved was unsolvable due to a clever parity argument, is also unsolvable because it has only one 0000 piece. (Likewise, the dual Star of David puzzle using two sets of pieces, which I proposed in order to get around the parity problem, is also unsolvable, because that would require four 0000 pieces.)

An alternative to the up and down slot scheme is the deep and shallow slot scheme, where all slots point the same direction on each piece. This scheme bypasses assemblability issues entirely, but it has another problem: because upward and downward pointing pieces may only connect to each other, the configuration they form must be bipartite. It turns out that a lot of interesting configurations aren’t! Here are the configurations possible on a triangular grid with 12 pieces with three equally spaced slots:

(Did I miss any?

(Did I miss any?)

Only two of these configurations are bipartite. They can be made with a double set of 6 pieces with a deep/shallow slot scheme. Here are a couple of prototype lasercut puzzles in these configurations:

minihexcross

But what about the rest? Is there some way we can change our piece set to be able to make them? If we allow the middle slot to take all four possible combinations of up/down and deep/shallow, while the outer slots are deep/shallow and, as before, point the same direction, the resulting set should be more flexible in the configurations that can solve. (Conveniently, there are twelve such pieces.) Any subconfiguration with a cycle formed by an odd number of pieces that is connected only by outer slots is still impossible to solve. Therefore the configuration with the triangle shown in brown is still impossible. But the others should still be solvable.

(As I was finishing off this post, another set of pieces to use with these configurations occurred to me. We can make a set of pieces where each piece has exactly one deep, one middle, and one shallow shot, and the slots can occur in either direction and any order. As before, there are twelve such pieces. Can they be assembled into all of the above configurations?)