0
$\begingroup$

Rule "zero is better than one":

Consider a sequence which is made up only of elements from the set {0, 1} and constructed regarding to the following rules:

1) It starts with n ones.

2) We put one at the end of the sequence if and only if by putting zero we get a subsequence which length is n and it has been already written.

3) If there is no turn that produces a new subsequence which length is n we stop.

Prove that after doing this algorithm we will get De Brujin sequence with parameters n and k = 2.

Note: Subsequence is a continuous part of the sequence.

$\endgroup$
3
  • $\begingroup$ And what are your thoughts on this? $\endgroup$
    – Théophile
    Oct 27, 2016 at 23:12
  • $\begingroup$ @Théophile, I tried to note something common in cases for different n, but all my attempts were without any result. $\endgroup$ Oct 27, 2016 at 23:17
  • $\begingroup$ Do you know any graph theory? $\endgroup$ Oct 29, 2016 at 8:47

1 Answer 1

-1
$\begingroup$

So when I first started playing with De Bruijn sequences, before I even knew that name or that anyone else had played with them, that was the first way I found that produced them. My grandfather (who also had not heard of them but likes these kinds of puzzles) and I had tried to write up a proof that it worked. By the time we had finally gotten one I had gone onto making a more general solution to the problem, and I can't seem to find where the proof we made went, but I will try to piece it back together again.

By the way I am sure this proof is super redundant and inefficient, but whatever. It made more sense when trying to expand to other algorithms that produced any De Bruijn sequence, which is what we did later.

The first major thing we wanted to prove was that this method never produced a repeat, which is kind of redundant here since you just went out and required that you add in a manner that skips repeats, whereas our first method required counting the times you saw a certain subsequence of length n-1.

The second thing we wanted to prove was that it ended at some point, which it must since there are only finite possible subsequences that one can produce without repeats within the finite n and k given.

The third thing, which here is the only non-trivial thing to prove, was that it created every possible subsequence of length n in base k. We did this by first establishing that the last n-1 digits of the sequence must all be ones because the sequence cannot repeat, and the last n-1 digits must have occurred twice before to ensure that no digit could be placed at the end. Then because the last n-1 digits must have occurred twice before they must be the same as the first n-1 digits. this is because if they were not the first n-1 digits, then on two other occasions they must have had a digit preceding them and then again at the end, this would mean 3 different digits must have proceeded them, and since only 2 are present in this system, it is impossible for any n-1 digits other than the first ones to be present at the end of the sequence.

Once it is established that the last n-1 digits are all ones it is possible to prove the number of n length sequences, and based on the fact there are no repeats, that the sequence is a complete De Bruijn sequence. each n-1 length subsequence ending in a one, other than the first, must be preceded by a digit. since two n-1 sequences composed of all ones other than the first have been shown to exist (I did not prove this here but it is trivial at this point) one can know that two different digits precede n-1 length strings of ones. that gives us 2 n length strings, let us focus on the one that is not the first n length string, so the one beginning with a 0. if we look at it's first n-1 digits one can know that the same subsequence occur somewhere else, since we already know that for a n-1 subsequence to be followed by a one, it must have been followed by a zero earlier (again not proven here but trivial by initial conditions) that way you have two new subsequences to perform the process on. You repeat the process of looking at the first n-1 digits of each subsequence, finding it's duplicate, seeing that each must have a different number preceding them, counting those n length subsequences and duplicating. Once a sequence ends in a 0, all the others you find in that step must also end in 0's (because each step decreases the number of 1's at the end by one) since you started with n-1 ones and 2 n length subsequences, and each time you perform these steps you double the number of n length subsequences you have to double n times (because each time you have subsequences that you find the first part of, find the copy, there of, getting an additional sequence for each sequence if you consider what follows, and then double again by looking at the part preceeding it. It does not actually double twice each time because the first and second doublings overlap between steps, but in the final step they don't getting and extra double). This gives you 2^n n length sequences, which is how many their should be in a De Bruijn Sequence for base 2.

Sorry this is a little roundabout and complex at the end, I need to clean up my language but this is mostly from memory and not looked over for good and consistent wording.

$\endgroup$
1
  • $\begingroup$ As you say, this answer is quite a ramble, and could use some tightening up. As it is, I am having difficulty parsing it. This question is old, and isn't going anywhere. Perhaps you would like to take some time to clean up your answer a bit? $\endgroup$
    – Xander Henderson
    Jul 14, 2018 at 2:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .