MHB Is Two-Colour Bead Necklace Arrangement Possible?

[evinda]

Hello! (Wave)

We have a necklace with $64$ beads from $8$ different colours. Is it possible that they are put in such a way that if we go along the necklace in one direction (in any of the two) then we see all the possible successions of two colours exactly once?

 

[Opalg]

Hello! (Wave)

We have a necklace with $64$ beads from $8$ different colours. Is it possible that they are put in such a way that if we go along the necklace in one direction (in any of the two) then we see all the possible successions of two colours exactly once?

This is called a De Bruijn sequence. (I'm assuming that the necklace is joined up at the ends so as to form a cyclic sequence of beads.)

The sequence that you want is the De Bruijn sequence $B(8,2)$. If you want to see an example, here it is (with the colours labelled $0$ to $7$).

[sp]http://www.hakank.org/comb/debruijn.cgi?k=8&n=2&submit=Ok[/sp]

 

[evinda]

This is called a De Bruijn sequence. (I'm assuming that the necklace is joined up at the ends so as to form a cyclic sequence of beads.)

The sequence that you want is the De Bruijn sequence $B(8,2)$. If you want to see an example, here it is (with the colours labelled $0$ to $7$).

[sp]http://www.hakank.org/comb/debruijn.cgi?k=8&n=2&submit=Ok[/sp]

And how could we prove that such a sequence exists? (Thinking)

 

[caffeinemachine]

And how could we prove that such a sequence exists? (Thinking)

The construction of $B(2, 4)$ is illustrated in the wiki article. That should explain how to construct such sequences. You can see the proof of the general statement in West's Introduction to Graph Theory. Look for "De-Bruijn Cycles" in the index.