5
$\begingroup$

Let's be given a safe that is secured by a code of length $n$ generated by using symbols from an alphabet of length $m$.

Now a continuous stream of symbols may be entered in order to open the safe. As soon as the correct code becomes a subsequence of stream thus far entered, the safe opens.

Given $n$ and $m$, what is the shortest code that opens the safe, that is guaranteed to open for any correct code?

For example, if one wants to test the codes AAA and AAB it is enough to simply try AAAB as both AAA and AAB are subsequences of AAAB.

$\endgroup$
  • 4
    $\begingroup$ Are you sure that you intend for any subsequence to open the safe, or only contiguous subsequences? $\endgroup$ – Eric Tressler Nov 12 '17 at 22:47
14
$\begingroup$

Assuming you mean that a correct code must be a substring, and not just a subsequence, then the answer is given by a de Bruijn sequence for words of length $n$ on $m$ letters, which has length $m^n$. (https://en.wikipedia.org/wiki/De_Bruijn_sequence)

Since de Bruijn sequences are cyclic, the answer might appear "across the boundary" from the end of the sequence to the start. Since our answer is a linear sequence, we need to repeat the first $(n-1)$ characters of whichever sequence we chose, making the actual length $m^n + n - 1$.

$\endgroup$
9
$\begingroup$

If you mean a substring then Eric's answer is fine. If you mean a subsequence then

a string of length mn should be sufficient.

To show it needs to be at least that long...

Consider that the code could consist of n repeats of the first character in {m}, or n repeats of the second character in {m}, etc. So each of the m characters needs to be repeated at least n times.

To show it doesn't need to be any longer...

Consider the length mn string consisting n repeats of the sorted alphabet. The first character in the code must appear in the first m characters of the string, the second character in the code must appear in the second n characters in the string etc. So each of the n characters in the code will appear (in the correct order) in the succeeding m characters in the code.

As an example:

With five characters {A,B,C,D,E} in a three letter code ABCDEABCDEABCDE will open the safe, or with three characters {A,B,C} in a five letter code ABCABCBCABCABC will be sufficient.

$\endgroup$

Not the answer you're looking for?Browse other questions tagged or ask your own question.