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.
Continue reading

2. Puzzle Series [#1, #2, #3]

Each ‘puzzle series’ post will be a few puzzles, which I have learned about watching videos, reading some random books, or I did come up with gathering ideas from here and there. By word ‘puzzle’, I informally mean a problem that can be stated easily and has at least one known solution which doesn’t involve fancy math. Usually I put couple of hours a week thinking about some of these puzzles and I really enjoy the process, and want to share this joy with you.
Continue reading