I recently encountered the following problem: How long is the shortest possible string in a given alphabet of size N, that contains all n-symbol strings? And how to construct such a sequence.
For instance, say, an electronic lock will open when a certain unknown 4-digit code is entered at any time. (N = 10, n = 4) What's the minimum number of keypresses that will open the lock with 100% certainty?
Name:
Anonymous2010-07-25 19:04
I'm not entirely sure I understand what your asking but I thinks you mean is that on a lock with 10 digits, presumably 0 - 10 (not that it matters), and it needs 4 digits entered. What is the least number of tries at entering a code, could you be guaranteed success?
Answer: 10'000, All you could enter are the numbers 0000 through 9999, so ten thousand different combinations, If you entered all 10'000 combinations you would be guaranteed success on one of them.
However, you said " keypresses" so I don't know if you mean complete codes or individual key presses.
If you meant individual key presses the answer is 40'000 as there is 4 digits in each code do 10'000*4 = 40'000
>>1
It depends on the lock. For instance, if the code is "1143" will pressing "21143" open it, or will it take "2114" and fail?
Name:
Anonymous2010-07-26 16:58
I think the OP's question means that, for example, the sequence 235976 would be interpreted as 2359 followed by 3597 and then 5976. That example shows that a string of 6 digits can give 3 unique 4-digit strings. So the question is what is the shortest string of digits that would be interpreted as the entire list of 10000 4-digit codes.