Posers and Puzzles
03 Nov 11
03 Nov 11
I have no idea about this.
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?
- Joined
- 18 Jan 07
- Moves
- 12477
05 Nov 11
Originally posted by talzamirIt 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.
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?
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
- Joined
- 29 Dec 08
- Moves
- 6788
05 Nov 11
Originally posted by Shallow BlueIt 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.
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