Binary string that contains all substrings of length k exactly once.

Question

Here is the problem I'm working on (Satan's apple with bounded memory decision problem): Suppose I offer you slices of an apple, first $1/2$, then $1/4$, ... then $1/2^k$, etc. You want to eat as much of the apple as possible without eating the whole thing. For simplicity, lets have the utility $U(A_n) = n$ where $A_n$ is eating n slices, and $U(A_\infty) = -1$. Now suppose you can't remember the decision you made $k$ decisions back. What is the optimal strategy (only deterministic strategies are allowed)?

For $k = 0$, either you always pick a slice, or you don't pick one, so there are two strategies. The first gives $-1$ utility, the second gives $0$, so don't take.

For $k > 0$, I formalize the problem as such. Let $S:\mathbb N \to \mathbf 2$ be your sequence of moves, with $S(n) = 0$ if you don't pick the nth slice and $1$ if you do, and $S_i:\mathbf k \to \mathbf 2$ be the $k$-length substring starting at $i$. For simplicity (and I don't think it turns out to matter), let $S(i) = 0$ for $i < k$, and $S(k) = 1$. This represents $k$ being the first time you take a slice and removes the difficulty of dealing with a third option of not having been offered a slice. The goal now becomes maximizing $U(S) = \sum_i S(i)$ while still having the sum converge.

For $k=1$, we have $1\bar 0$, $U(S) = 1$ being the optimal solution

$k = 2$,

$S_1 = 01$

$S_2 = 11$

$S_3 = 10$

$S_4 = 00$

S = $011\bar 0$, $U(S) = 2$. Notice how all strings of length 2 show up.

---

$S_1 = 001$

$S_2 = 011$

$S_3 = 111$

$S_4 = 110$

$S_1 = 101$

$S_2 = 010$

$S_3 = 100$

$S_4 = 000$

$k = 3$, $0011101\bar 0$, $U(S) = 4$. Again, every string of length 3 shows up.

---

$k = 4$, $00011101100101\bar 0$, $U(S) = 8$, and all strings of length 4 show up.

If a string of length $k$ comes up more than once, other than $00\dots$, then we will get a cycle of strings containing a $1$ and $U(S)$ will not converge, so I know the above solutions are optimal.

Questions:

1. Do these sequences have a name?
2. Do they exist for all $n$? Will they always contain $2^{n-1}$ $1$s?
3. How do I specify them or give some closed form for them?
4. Is my conjecture that it doesn't matter if we start with $000\dots 1$ instead of $---\dots 1$ (where $-$ is no slice is offered, or a blank tape entry) true? This would mean that you can distinguish the first $k$ offerings from the rest by by remembering you've only been offered a slice $i < k$ times. It's strictly more information, but I couldn't do anything with it for $k = 2, 3$.

Answer 1

Cyclic Gray codes will work, not the only solution, though.

0,1

0,1,1,0 [reverse] and augment by first zero and one on the left 00,01,11,10

write as sequence (I wrote 2 periods since you need to slide windows of length 2 along to see all tuples

0011,0011

000 001 010 011 111 110 101 100

write as sequence

0001010111010,0...

Answer 2

1. The name is De Bruijn sequences.
2. They exist for all $n$. For your alphabet $\{0,1\}$, they contain $2^n$ symbols with $2^{n-1}$ 0's and the same 1's.
3. It's not easy to generate them. One way is with a shift register. See Knuth's Combinatorial Algorithms pre-fascicle 2A pp.22-23. (PDF)

I don't know the answer to 4.