# Posts Tagged ‘binary words’

## Three More Crossed Stick Puzzles

March 28th, 2013

Since I last posted about crossed stick puzzles, I’ve come up with three new ones. Here’s one of them:

This one nicely fills one of the spots in the binary word table. There are eight pieces with three slots apiece; if we use binary shallow/deep slots, there are exactly eight possible pieces, because the pieces won’t be flippable vertically or horizontally within the puzzle.

The principle behind this piece configuration can be used to make other configurations. You can take any line segment, together with a center point, reflect the segment across an axis passing through the center, and create images of the original and reflected segments over successive rotations around the center to make configurations with rotational (indeed, dihedral) symmetry. However, because the pieces wouldn’t generally be horizontally flippable, (are there exceptions?) this only produces puzzles with combinatorially complete piece sets when the number of pieces is a power of two, and only 8 and 16 make reasonable numbers of puzzle pieces. In fact, I’d argue that the ideal range of numbers of pieces for a puzzle of this type is between 8 and 12, with a penumbra extending to about 6 and 16 in which puzzles will still be interesting to some solvers, but not as many. This necessarily constrains the quantity of viable puzzle configurations to a number that is finite, and may indeed be quite small.

But if the math keeps the number of possible puzzles down, inventing new ways to skirt the constraints we’ve set for ourselves can create new possibilities. Witness the following configuration:

Here the slots are ternary: intersection points can have slots that are ⅔ of the width of the piece (pointing up or down) or they can have two slots ⅓ of the width of the piece, pointing both up and down. Where three pieces intersect, one of each of these three slot types must be present. Three piece intersections are harder to work with than regular intersections. I’m pretty sure there is no finite configuration on the triangular grid containing all pieces of the same size with all intersections being three piece intersections.

So we have to fudge. This configuration looks like it has two kinds of three slot pieces, because three of the three slot pieces intersect at a two piece intersection. The trick is that the slot on the two slot pieces at the two slot intersection has a special, single ⅓ width slot, so that it can match the regular slots on the three slot pieces. Nicely, there are exactly three possible two slot pieces with one slot of this type and one regular slot.

In this scheme there are ten three slot ternary pieces, when both horizontal and vertical flipping is allowed. Since there are only nine three slot pieces in the configuration, one piece must be excluded. In fact, our hand is forced: the excluded piece must be the one that has all three slots of the double ⅓ width type. This is because the total number of double ⅓ width slots must equal the number of three piece intersections, which is nine. Before excluding that piece, there is one double ⅓ width slot in the two slot pieces, and 11 such slots in the three slot pieces. Well, if we can’t have a combinatiorially complete set of pieces, the next best thing is a combinatorially complete set minus the most exceptional member, which we could argue that this piece is, on account of it being the only piece with both horizontal and vertical reflection symmetry.

Finally, two configurations for the same piece set:

The configuration on the left was one that I implied in this post. If we use shallow/deep binary slots, we have pieces that can be flipped horizontally but not vertically. There are six of these and twelve pieces in the configuration, so we can use a double set of these as our piece set. As an extra bit of good fortune, there is a second configuration that uses these pieces.

I’m currently getting prototypes of the last two of these lasercut, so I hope to be able to show off the results soon. (I came up with the first one after I put in the order, so it will be a while before I get around to making a prototype of it.)

## More Fun with Binary Words: De Bruijn Sequences

January 1st, 2013

In the previous post, we explored symmetry variations on binary words in the context of crossed stick puzzles. Now I want to look at some ways to play with sequences of these binary words. For reference, I’ll recap the table of numbers of different binary words of various types and lengths from that post. As before, swapping 1’s and 0’s with each other gives equivalent invertible words, and turning words backwards gives equivalent reversible words.

You’ll notice some new columns in this version of the table. Cyclic words remain equivalent over any number of cyclic shifts or moves that take every digit but the last down by one place and put the last into the first place. You can think of the digits as black and white beads on a necklace, where the necklace stays the same however you rotate it. The cyclic property can be combined with invertibility and reversibility; reversing a cyclic word is equivalent to “flipping over” the necklace.

 Length Fixed Invertible Reversible Inv. & Rev. Cyclic Cyclic Inv. Cyclic Rev. Cyclic Inv. & Rev. 1 2 1 2 1 2 1 2 1 2 4 2 3 2 3 2 3 2 3 8 4 6 3 4 2 4 2 4 16 8 10 6 6 4 6 4 5 32 16 20 10 8 4 8 4 6 64 32 36 20 14 8 13 8 7 128 64 72 36 20 10 18 9

One classic puzzle involving binary words is to find a necklace where every possible word of a given length is present exactly once exactly once as a substring of the necklace. These necklaces are known as De Bruijn sequences. For example, here’s a De Bruijn sequence of length 4 binary words:

Since we have a bunch of variations on binary words, we can look for De Bruijn sequences of each of them. Neither the cyclic nor the reversible words will make proper De Bruijn sequences. Consider the length 3 word `000`. There can’t be another 0 on either end of that, because that would make a second instance of `000` in the sequence. So there must be a substring of `10001` in the sequence. But that gives instances of both `001` and `100` which are equivalent to each other both as cyclic and reversible words. The same reasoning applies to longer words.

However, you can make improper, non-cyclic De Bruijn sequences. For example, `00010111` is an improper De Bruijn sequence of the reversible length 3 words. For the reversible length 4 words, even an improper De Bruijn sequence is impossible. (Try to make one, if you are wondering why.) Problem #29 is to find an improper De Bruijn sequence for the reversible words of length 5.

The invertible and reversible length 4 words do have an improper De Bruijn sequence: `000011010`. And with plain invertible words, proper cyclic De Bruijn sequences are again possible. Here’s a De Bruijn sequence of the invertible words of length 4:

Problem #30: Find a De Bruijn sequence of the invertible words of length 5.

Unlike polyform puzzles, De Bruijn sequences are considered a topic for respectable mathematics, which means that they are well studied, and therefore it can be assumed that anything written here is well known by those who know such things. Still, they are fun to think about, and have real world applications. For example, in the study of Sanskrit poetry, a mnemonic based on the nonsense word yamātārājabhānasalagā has been employed. In this word, the syllables correspond to the names of three syllable feet, (like anapests and dactyls in western poetry) and the three syllable segment starting with a given syllable has the same stress pattern as the foot denoted by that name. (The syllables with macrons are stressed and the others are unstressed.) If you truncate the last two syllables, the stress patterns “wrap around” to create a proper De Bruijn sequence.

And I still haven’t gotten to Gray Codes. Well, I’ll get to that in a later post. Unless I get distracted and never get back to it, which is a real possibility.

(Sources: Wikipedia on Sankrit Prosody and De Bruijn Sequences, and Professor Stewart’s Cabinet of Mathematical Curiosities by Ian Stewart.)

## Symmetry Variations on Binary Words

December 18th, 2012

In exploring the space of crossed stick puzzles, I’ve gone on a tangent into the world of binary words and their symmetries. A binary word is just a string where the “letters” can be one of two symbols; for convenience we’ll use 0 and 1. (The distinction between a “word” and a number in binary is that a word can have any number of leading 0’s, and these are significant.)

The usefulness of binary words in crossed stick puzzle design comes from our ability to encode them in the types of slots used in a piece of a puzzle. For example, my decagram puzzle uses pieces with outer slots that could point down or up, and inner slots that always point up, but could be deep or shallow. We can assign 0 to down and 1 to up for the outer slots, and 0 to deep and 1 to shallow for the outer slots. Then, reading across the slots, we get a binary word corresponding to a given piece. For example, down-shallow-deep-up is `0101`.

One benefit of using binary words is that we can enumerate the possible pieces in a puzzle by counting the binary words of a given length, (in this case four). But there is a snag: The piece we called `0101` can be flipped horizontally, after which it would read as `1010`. It seems that rather than plain binary words, what we want are the equivalence classes of binary words formed by some symmetry action, in this case, reversing the word. Examining these gives us four symmetrical words that map to themselves upon flipping, and six pairs of words that flip to each other, for a total of ten classes of length four.

Instead of horizontal flipping, we could, if our slots are only using an up vs. down slot scheme, flip them vertically. In terms of the effect on the pieces, this will invert all of the 0’s to 1 and vice versa. This gives us eight pairs of words that flip to each other. We could also allow both horizontal and vertical flipping. In this case there are six classes of words of length four.

At this point, you might want a table with the number of binary words of each type. That way, when you come up with a crossed stick puzzle idea you can look at the table on the row with the number of slots in the pieces, and see if there’s an entry that gives you the number of pieces you’d like. Or you could go the other direction, and look at an entry in the table and try to come up with a good puzzle for that entry. (This is how I designed my Decagram puzzle.)

 Length Fixed Invertible Reversible Inv. & Rev. 1 2 1 2 1 2 4 2 3 2 3 8 4 6 3 4 16 8 10 6 5 32 16 20 10 6 64 32 36 20 7 128 64 72 36

Let’s give it a try using the piece configuration from my last post:

Applying the table to this, there are 12 pieces with 4 intersections (and thus, slots) in that configuration. There are no entries of 12 in that row, so we’re going to have to get creative. There’s a 6 in the Inv. & Rev. column; we can make our (well, my) puzzle have two copies of each piece corresponding to one of those. The intersection points are conveniently symmetrical, which gives us reversibility, and if we use up/down slots, we get invertibility. So now we have a puzzle design.

Of course, there’s one step left, which is making sure that the puzzle can be solved. (Ideally, by a human being of reasonable intelligence devoting no more than a reasonable amount of time.) It is quite possible to develop a design for a puzzle of this type that can’t be solved.

For example, this star of David puzzle, using one set of the invertible & reversible 4 slot pieces, is unsolvable. To see why, look at the relevant binary words, and consider the first and last digits, corresponding to the slots at the six points of the star.

```0000 0001 0010 0011 0101 0110```

There are three 1’s in the external slots. Inverting a word may change that number by two, or keep it the same. Reversing a word will not change the number of 1’s. Therefore, the number of 1’s must always be odd. But since each intersection in a solved puzzle must have one up and one down slot, there must be exactly six 1’s in external slots in a solved puzzle. Thus, the puzzle is unsolvable. (However, if we had two copies of each piece, we could possibly make two stars of David by swapping pieces between the sets. This gives us a second challenge for the set above. It’s starting to look like a keeper!)

Stepping away from crossed stick puzzles, it turns out that all of the fun things that you can do with binary words can be done with these symmetry variants. And when I think of fun things you can do with binary words, I think of de Bruijn sequences and Gray Codes! But this post has gotten long enough already; that will have to wait for another post.