Problem: What is the shortest base-d sequence which contains all sequences of n d-digits?
I think I have a solution, but it's a bit of a sketch. The best possible is length d^n, assuming all adjacent sequences overlap (n-1), and I aim to show how to make one that length.
Instead of a sequence, consider a loop. We write this as a sequence, but consider the ends to be joined. This is because there's enough symmetry we can probably solve the one problem if we can solve the other, and because we can combine sequences without having to have n-1 tails hanging off the ends.
For instance, for 3-sequences of 2-digits, the loop 00010111 contains all 2^3 3-sequences, two of them wrapping round the end.( Spoilers :) )
I think I have a solution, but it's a bit of a sketch. The best possible is length d^n, assuming all adjacent sequences overlap (n-1), and I aim to show how to make one that length.
Instead of a sequence, consider a loop. We write this as a sequence, but consider the ends to be joined. This is because there's enough symmetry we can probably solve the one problem if we can solve the other, and because we can combine sequences without having to have n-1 tails hanging off the ends.
For instance, for 3-sequences of 2-digits, the loop 00010111 contains all 2^3 3-sequences, two of them wrapping round the end.( Spoilers :) )