# Category Archives: Puzzles

These posts are the puzzle series.

# 6. Puzzle Series [#3: De Bruijn sequence]

I will discuss puzzle #3 here. Let me repeat the puzzle. You want to write a string $S$ of digits with minimum length, say $L= {\rm length}(S)$, to include all the $n$-digit numbers in base $b$. For example, if $n=3$ and $b=10$, then, we want $S$ to include 000, 001, …, 999 in it, as its substrings.

Proposition 6.1. A string $S$ with length $L=b^n+n-1$ digits, can include all the $n$-digit numbers in base $b$, as its substrings. This formula means that each digit you are appending, after first $n-1$ digits, will include a new substring, i.e. a distinct $n$-digit number. The proof will be a bit sketchy, but I think it is quite straightforward to make it rigorous.