# Combination Lock

talzamir
Posers and Puzzles 03 Nov '11 23:12
1. talzamir
Art, not a Toil
03 Nov '11 23:12

A door has an electronic lock with a two-digit code of zeros and ones. When gives a sequence of entries it looks at the latest two keys pressed, in sequences. If the last 2 are right right combination the lock opens; if nothing is pressed for a few seconds, the lock clears its memory. Obviously the combination is 00, 01, 10 or 11. I could type

00110

and that covers all the combinations. The number of clicks needed is the # of combinations + length of the right combination - 1.

Does that apply also for longer combinations? Also for codes that are not binary?
2. 05 Nov '11 16:38
Originally posted by talzamir
A door has an electronic lock with a two-digit code of zeros and ones. When gives a sequence of entries it looks at the latest two keys pressed, in sequences. If the last 2 are right right combination the lock opens; if nothing is pressed for a few seconds, the lock clears its memory. Obviously the combination is 00, 01, 10 or 11. I could type

00110

a ...[text shortened]... ation - 1.

Does that apply also for longer combinations? Also for codes that are not binary?
It does for three combinations. That needs 0001110100 (amongst others; 1000111010 would work as well, and is the same length). I haven't tried for four or more yet, but I suspect you are right.

And, being a programmer, I would have no idea about anything which isn't binary ðŸ˜›.

It is quite possible that you'd find the answer in Knuth, but I think it would have to be in one of the volumes which are as yet to be published. Unless he's got round to publishing vol. 4 when I wasn't looking; AFAICT it should be in that. But it's a fascinating problem, in any case.

Richard
3. 05 Nov '11 21:26
Originally posted by Shallow Blue
It does for three combinations. That needs 0001110100 (amongst others; 1000111010 would work as well, and is the same length). I haven't tried for four or more yet, but I suspect you are right.

And, being a programmer, I would have no idea about anything which isn't binary ðŸ˜›.

It is quite possible that you'd find the answer in Knuth, but I think i ...[text shortened]... king; AFAICT it should be in that. But it's a fascinating problem, in any case.

Richard
It seems to me if the calculation of minimal string length works for all binary combinations, then it works for all base-N combinations. The correct combination in any base can be expressed in binary, e.g., a base-3 combination like 2011 can be expressed as "11 00 01 01"(spaces for clarity). This can then be handled as a binary problem with combination length = 8. The minimal string length can be computed and converted back to base-3 which it seems must also be the minimal string length in that base.