Bracelets and de Bruijn Sequences

My colleague, Daniel Kline, was looking at chain linking manipulative and wondering what activities could make use of them. While he's working on an activity based on symmetries, I thought I would write one up based on de Bruijn sequences.

Setup

The manipulative that sparked this discussion is Learning Resources' Link n' Learn Links. As of this writing, they cost about $15 for 500 links. Here are a couple variants:

• Suwimit C-Clip Hooks (1000 links for $17)
• Bissap Plastic Chain Links (250 links for $8)

Four colors should suffice, but six could be nice for going deeper. Here is a starter puzzle to frame things:

Example

You have been commissioned to make a bracelet from (red) rubies and (blue) sapphires so that every possible clockwise 3-gem string of rubies and sapphires occurs. How many gems should you use? (It's in your best interest to use as few as possible!)

The bracelet could be made by considering all 3-gem strings and concatenating them. Using R for red and B for blue, these are

RRR, RRB, RBR, RBB, BRR, BRB, BBR, BBB.

The resulting bracelet is pictured below, with segments for emphasis on the right:

This arrangement is rather wasteful. For example, notice there are five reds in a row, which contributes three copies of RRR. If we cut out two of these red gems, we still have all eight 3-gem sequences, but we use 22 gems instead of 24:

Similarly, we find there are three non-overlapping instances of BBB. If we cut one gem from each of two of them, we still have all 8 distinct 3-gem strings and have reduced the number of gems used from 22 to 20:

We could continue trimming in this way, but maybe there is a way to more efficiently make this bracelet without over-making it and trimming it. For example, here is a way to do it with just 12 gems that we can't get by trimming our original bracelet:

How much better can we do?

Initial Questions

• What's the least number of gems needed to get:

  • Every clockwise 3-gem string of (red) rubies and (blue) sapphires on a bracelet?
  • Every clockwise 4-gem string of rubies and sapphires on a bracelet?
  • Every clockwise 5-gem string of rubies and sapphires on a bracelet?

• Is there a pattern to the number of gems required?

• Is there a nice way to find these efficient bracelets?

• How do things change if we have (red) rubies, (blue) sapphires, and (yellow) topazes?

• How do things change if we have (red) rubies, (blue) sapphires, (yellow) topazes, and (green) emeralds?

Explorations

You can do quite a bit better than 12 gems in the original problem. Here's a solution that uses only 8 gems:

It's a subtle point that students will hopefully work their way to, but to minimize the number of gems, it's best to make the gems "do a lot of work." In our original solution, we dedicated 3 gems for each of the distinct eight 3-gem strings, and removal of any gem ruins only one of these strings, at most (there are enough duplicates that that string might exist elsewhere). In our most recent solution, each gem is part of three distinct 3-gem strings and removal of any gem ruins at least one but up to three 3-gem strings if none accidentally get recreated after deletion.

What are some ways to try to come up with efficient arrangements?

• We can try building the bracelet one gem at a time. We could start with a string like RRR and then try to add a gem in such a way that exactly one new 3-gem string is added. If we did this, we'd see that it needs to be a sapphire, since otherwise we just have two RRR sequences:

  RRRR = (RRR)R = R(RRR)

  Since adding an R on either side is wasteful in this way, any efficient extension will have

  BRRRB

  If we add an R to both sides, this would create two copies of RBR, so at least one side should have B added. If both sides have B added, then since we would eventually cycle back to R, we would end up with two copies each of RBB and BBR. Thus, some good extensions would be

  BBRRRBR and RBRRRBB.

  Since we still don't have the 3-gem sequence in either, BBB, we could add a B:

  BBBRRRBR and RBRRRBBB.

  Closing these loops give our 8-gem solution and its mirror image.

• A more visual way to think about constructing these sequences one gem at a time is by making a directed graph:

  

  A sequence of gems is a path through this directed graph. For example, RBRRRBBB is the path

  RBR → BRR → RRR → RRB → RBB → BBB

  where the \(n\)th 3-gem sequence in the path is what you get when you start with the \(n\)th gem in RBRRRBBB and read 3 gems in a row, wrapping around. The graph is constructed so an arrow points exactly from one node to another precisely when the last two gems of the source node match the first two gems of the destination node.

  If we add another few terms, we get a wrap-around version and end where we started:

  RBR → BRR → RRR → RRB → RBB → BBB → BBR → BRB → RBR

  To use the graph to build a nice bracelet, find a path crossing through every node once (exactly once, if possible!) and ending where it started only moving from node to node in the directions the arrows point. Such a closed path hitting every node exactly once is called a Hamiltonian cycle. Here is the cycle (dark) for RBRRRBBB, tracing out the path described above:

  

• Some nice small cases to investigate for creating a bracelet with \(k\) types of gems containing all length-\(n\) strings:

  • \( (k,n) = (2,3) \)

  • \( (k,n) = (2,4) \)

  • \( (k,n) = (2,5) \)

  • \( (k,n) = (3,2) \)

  • \( (k,n) = (3,3) \)

  • \( (k,n) = (4,2) \)

  • \( (k,n) = (5,2) \)

• Since there are \( 2^n \) different binary strings of length \(n\), we have a natural lower bound on how short a ruby-sapphire bracelet can be. If we wish to see every \(n\)-gem string appear in a bracelet, we'll need at least \(2^n\) gems, since each gem would need to be the starting gem of a unique string of length \(n\).

  A somewhat surprising fact is that this lower bound can always be achieved. For \(k\) gem types and length \(n\) strings, you can always construct a bracelet of length \(k^n\) so that each distinct \(n\)-gem string occurs exactly once, reading clockwise. Generally, there are many ways to construct such a bracelet, called a de Bruijn cycle (or de Bruijn sequence).

• By stepping down a dimension, we can instead turn the problem of making a bracelet from one of visiting every vertex of a graph exactly once (i.e., finding a Hamiltonian cycle) to one of visiting every edge exactly once (i.e., finding an Eulerian cycle).

  To make a bracelet containing all \(n\)-gem strings using this method, we'll make a directed graph with \((n-1)\)-gem strings as its vertices. We will draw an arrow between two vertices if the last \(n-2\) gems of the source vertex match the first \(n-2\) gems of the target vertex. We'll interpret each edge as the \(n\)-gem string given by overlapping the two \((n-1)\)-gem vertex strings. Here is the digraph for our 3-gem string bracelet problem:

  

  We can think about crossing an edge as creating the corresponding \(n\)-gem string to our bracelet. A de Bruijn sequence corresponds to an Eulerian cycle (a path that starts and ends at the same vertex, crossing every edge exactly once). Since there will always be the same number of inward and outward edges at any vertex, an Eulerian cycle will always exist by a classic graph theory result. If students are familiar with graph theory, this is a nice proof that de Bruijn cycles always exist.

• One (not obvious!) way to construct such a sequence is by arranging the required gems in blocks in one row and alternating below. We then draw a line between the \(i\)th copy of a given gem in each row.

  

  If we number the positions in the rows, we can create permutation cycles by following the line from a top number to a bottom number, finding that bottom number in the top and tracing it down to a new bottom number, and so on until we return back where we started. If we do this for the above diagram, we find

  1 → 1,

  2 → 3 → 5 → 2,

  4 → 7 → 6 → 4,

  8 → 8

  If we lop off each redundant last number, we get an index sequence

  12354768

  in which replacing every index number with the corresponding gem in the top row yields

  RRRBRBBB

  Similarly reading

  

  gives the permutation

  1 → 1,

  2 → 4 → 2,

  3 → 7 → 3,

  5 → 5,

  6 → 8 → 6,

  9 → 9

  and index sequence

  124375689

  resulting in the de Bruijn sequence

  RRBRYBBYY

Wrap-Up Questions

• What were your personal bests for creating small, efficient bracelets?

• Did you find any methods for creating small bracelets or did you have to start each puzzle from scratch? (For example, did creating a bracelet where every 3-gem string appeared tell you anything about how to make one for 4-gem strings? If you master this for two types of gems, does this teach you anything about how it works with three gem types?)

Extensions

We've been careful to talk about every distinct string being present in the bracelet clockwise, but an interesting tweak to the problem is to demand each string of length \(n\) be present either clockwise or counterclockwise, allowing you to flip the bracelet to look for a given string. This doesn't allow you to make the bracelet smaller in some cases, but here is a solution for \( (k,n) = (3,2) \) with \( 6 \) gems when \( 3^2 = 9 \) would have been required without mirroring:

Here is a \(14\)-gem bracelet for \( (k,n) = (2,4) \) when \(2^4\) would be required without mirroring:

How much better than \( k^n \) gems can we do, in general, if we allow reversing? Is there a similarly nice formula for the number of gems? A nice way to construct them?

This post was sponsored by the Julia Robinson Mathematics Festival