{"id":188,"date":"2013-01-01T21:38:06","date_gmt":"2013-01-02T05:38:06","guid":{"rendered":"http:\/\/puzzlezapper.com\/blog\/?p=188"},"modified":"2013-01-02T15:12:18","modified_gmt":"2013-01-02T23:12:18","slug":"more-fun-with-binary-words-de-bruijn-sequences","status":"publish","type":"post","link":"https:\/\/puzzlezapper.com\/blog\/2013\/01\/more-fun-with-binary-words-de-bruijn-sequences\/","title":{"rendered":"More Fun with Binary Words: De Bruijn Sequences"},"content":{"rendered":"

In the previous post<\/a>, 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<\/em> 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<\/em> words, and turning words backwards gives equivalent reversible<\/em> words. <\/p>\n

You’ll notice some new columns in this version of the table. Cyclic<\/em> words remain equivalent over any number of cyclic shifts<\/i> 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.<\/p>\n\n\n\n\n\n\n\n\n\n
Length<\/td>\nFixed<\/td>\nInvertible<\/td>\nReversible<\/a><\/td>\nInv. & Rev.<\/td>\nCyclic<\/a><\/td>\nCyclic Inv.<\/a><\/td>\nCyclic Rev.<\/a><\/td>\nCyclic Inv. & Rev.<\/a><\/td>\n<\/tr>\n
1<\/td>\n2<\/td>\n1<\/td>\n2<\/td>\n1<\/td>\n2<\/td>\n1<\/td>\n2<\/td>\n1<\/td>\n<\/tr>\n
2<\/td>\n4<\/td>\n2<\/td>\n3<\/td>\n2<\/td>\n3<\/td>\n2<\/td>\n3<\/td>\n2<\/td>\n<\/tr>\n
3<\/td>\n8<\/td>\n4<\/td>\n6<\/td>\n3<\/td>\n4<\/td>\n2<\/td>\n4<\/td>\n2<\/td>\n<\/tr>\n
4<\/td>\n16<\/td>\n8<\/td>\n10<\/td>\n6<\/td>\n6<\/td>\n4<\/td>\n6<\/td>\n4<\/td>\n<\/tr>\n
5<\/td>\n32<\/td>\n16<\/td>\n20<\/td>\n10<\/td>\n8<\/td>\n4<\/td>\n8<\/td>\n4<\/td>\n<\/tr>\n
6<\/td>\n64<\/td>\n32<\/td>\n36<\/td>\n20<\/td>\n14<\/td>\n8<\/td>\n13<\/td>\n8<\/td>\n<\/tr>\n
7<\/td>\n128<\/td>\n64<\/td>\n72<\/td>\n36<\/td>\n20<\/td>\n10<\/td>\n18<\/td>\n9<\/td>\n<\/tr>\n<\/table>\n

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:<\/p>\n

\"\"<\/p>\n

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<\/code>. There can’t be another 0 on either end of that, because that would make a second instance of 000<\/code> in the sequence. So there must be a substring of 10001<\/code> in the sequence. But that gives instances of both 001<\/code> and 100<\/code> which are equivalent to each other both as cyclic and reversible words. The same reasoning applies to longer words. <\/p>\n

However, you can make improper<\/em>, non-cyclic De Bruijn sequences. For example, 00010111<\/code> 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<\/strong> is to find an improper De Bruijn sequence for the reversible words of length 5.<\/p>\n

The invertible and reversible length 4 words do have an improper De Bruijn sequence: 000011010<\/code>. 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:<\/p>\n

\"\"<\/p>\n

Problem #30<\/strong>: Find a De Bruijn sequence of the invertible words of length 5.<\/p>\n

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\u0101t\u0101r\u0101jabh\u0101nasalag\u0101<\/em> 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.<\/p>\n

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.<\/p>\n

(Sources: Wikipedia on Sankrit Prosody<\/a> and De Bruijn Sequences<\/a>, and Professor Stewart’s Cabinet of Mathematical Curiosities<\/em> by Ian Stewart.)<\/p>\n","protected":false},"excerpt":{"rendered":"

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 … Continue reading More Fun with Binary Words: De Bruijn Sequences<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[99,102,101,71],"class_list":["post-188","post","type-post","status-publish","format-standard","hentry","category-recreational-mathematics","tag-binary-words","tag-cyclic-sequences","tag-de-bruijn-sequences","tag-symmetry"],"_links":{"self":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/188","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/comments?post=188"}],"version-history":[{"count":17,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/188\/revisions"}],"predecessor-version":[{"id":208,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/188\/revisions\/208"}],"wp:attachment":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/media?parent=188"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/categories?post=188"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/tags?post=188"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}