Brooks (brooksmoses) wrote,

A random math question.

So, suppose you've got one of those electronic push-button combination locks, with (say) four-digit passcodes, and you want to try to unlock it by going through all the passcodes sequentially. Assuming you enter the passcodes independently, you've got 10 possibilities for each digit, so you need to enter 104 passcodes, so 40,000 button-pushes are required.

However, in practice the locks are designed not to get too confused by random inputs. A simplistic way of implementing such a thing that seems consistent with observed behavior of some real-world locks is to unlock at any point when the last four button pushes correspond to the correct passcode. This means that, for instance, if you push "1 2 3 4", and then push "5", it will unlock if the passcode is 2345. Thus, with the ten button presses "1 2 3 4 5 6 7 8 9 0", you can try the seven distinct passcodes 1234, 2345, 3456, 4567, 5678, 6789, and 7890.

Thus, the question: Given such a lock, what is the minimum number of button-pushes required to try out all of the passcodes, and how do you generate an ordering of button-pushes to do that?

An obvious lower bound is 10,003 -- you need three at the beginning that don't test anything, and then after that you can test no more than one new passcode per push, so at least 10,000 for all of them. But it's not immediately obvious (to me, anyway) that a sequence exists that will run through all of the passcodes without duplicates. Thus, the question is to either generate such a sequence, or to generate a minimal sequence and prove that it's minimal.

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.