^{4}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.

## Error

Your reply will be screened

Your IP address will be recorded

You must follow the Privacy Policy and Google Terms of use.