Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member talzamir
    Art, not a Toil
    03 Nov '11 23:12
    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?
  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.