January 23rd, 2009


So, yeah, about those first few days

I'm seeing a fair bit of startlement among some people in my friendslist regarding the things that Obama's done in his first few days in office. It's almost as if they had this expectation that, because the metaphorical scaffolding was still up and a lot of the superstructure was being assembled, he wasn't yet ready to actually issue orders and stuff.

There's really only one response to that thought, I think:
Now witness the firepower of this fully armed and operational Obama administration!
  • Current Mood
    silly silly

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.