So, you know those cars with that keyless entry pad? The one under the
driver's side handle? Well, if you look closely you will see that there are
really only 5 buttons, labeled "1/2", "3/4", "5/6", "7/8", "9/0". In an effort
to avoid a little confusion, I'm going to call those buttons 1, 3, 5, 7, and 9,
respectively.
A little experimentation will reveal that, if the code is 11357, and you
type 5113579, the door will still open! This means that with 7 characters we
managed to try out 3 sequences - 51135, 11357, and 13579. After the inital 4
numbers (which sort of primed the pump) every digit tries one new sequence.
Since there are 55 length 5 sequences of characters
from an alphabet of size 5, we know that we'll need to try 3125 sequences total.
With our intuition from above, we would hope that we could find a sequence of
size 4 + 3125 (priming the pump, followed by one new sequence every keypress).
It turns out that a mathematician named de Bruijn has already done all of the
hard work for us on this one, and all of the relevant math can found under the
names de Bruijn sequence and de Bruijn graph. But I'm not
going to talk about math any further here. Right now, I am going to give you a
sequence of minimal length that, when you enter it into a car's numeric keypad,
is guaranteed to unlock the doors of said car. It is exactly 3129
keypresses long, which should take you around 20 minutes to go through.
9 9 9 9 1 1 1 1 1 3 1 1 1 1 5 1 1 1 1 7 1 1 1 1 9 1 1 1 3 3 1 1 1
3 5 1 1 1 3 7 1 1 1 3 9 1 1 1 5 3 1 1 1 5 5 1 1 1 5 7 1 1 1 5 9 1
1 1 7 3 1 1 1 7 5 1 1 1 7 7 1 1 1 7 9 1 1 1 9 3 1 1 1 9 5 1 1 1 9
7 1 1 1 9 9 1 1 3 1 3 1 1 3 1 5 1 1 3 1 7 1 1 3 1 9 1 1 3 3 3 1 1
3 3 5 1 1 3 3 7 1 1 3 3 9 1 1 3 5 3 1 1 3 5 5 1 1 3 5 7 1 1 3 5 9
1 1 3 7 3 1 1 3 7 5 1 1 3 7 7 1 1 3 7 9 1 1 3 9 3 1 1 3 9 5 1 1 3
9 7 1 1 3 9 9 1 1 5 1 3 1 1 5 1 5 1 1 5 1 7 1 1 5 1 9 1 1 5 3 3 1
1 5 3 5 1 1 5 3 7 1 1 5 3 9 1 1 5 5 3 1 1 5 5 5 1 1 5 5 7 1 1 5 5
9 1 1 5 7 3 1 1 5 7 5 1 1 5 7 7 1 1 5 7 9 1 1 5 9 3 1 1 5 9 5 1 1
5 9 7 1 1 5 9 9 1 1 7 1 3 1 1 7 1 5 1 1 7 1 7 1 1 7 1 9 1 1 7 3 3
1 1 7 3 5 1 1 7 3 7 1 1 7 3 9 1 1 7 5 3 1 1 7 5 5 1 1 7 5 7 1 1 7
5 9 1 1 7 7 3 1 1 7 7 5 1 1 7 7 7 1 1 7 7 9 1 1 7 9 3 1 1 7 9 5 1
1 7 9 7 1 1 7 9 9 1 1 9 1 3 1 1 9 1 5 1 1 9 1 7 1 1 9 1 9 1 1 9 3
3 1 1 9 3 5 1 1 9 3 7 1 1 9 3 9 1 1 9 5 3 1 1 9 5 5 1 1 9 5 7 1 1
9 5 9 1 1 9 7 3 1 1 9 7 5 1 1 9 7 7 1 1 9 7 9 1 1 9 9 3 1 1 9 9 5
1 1 9 9 7 1 1 9 9 9 1 3 1 3 3 1 3 1 3 5 1 3 1 3 7 1 3 1 3 9 1 3 1
5 3 1 3 1 5 5 1 3 1 5 7 1 3 1 5 9 1 3 1 7 3 1 3 1 7 5 1 3 1 7 7 1
3 1 7 9 1 3 1 9 3 1 3 1 9 5 1 3 1 9 7 1 3 1 9 9 1 3 3 1 5 1 3 3 1
7 1 3 3 1 9 1 3 3 3 3 1 3 3 3 5 1 3 3 3 7 1 3 3 3 9 1 3 3 5 3 1 3
3 5 5 1 3 3 5 7 1 3 3 5 9 1 3 3 7 3 1 3 3 7 5 1 3 3 7 7 1 3 3 7 9
1 3 3 9 3 1 3 3 9 5 1 3 3 9 7 1 3 3 9 9 1 3 5 1 5 1 3 5 1 7 1 3 5
1 9 1 3 5 3 3 1 3 5 3 5 1 3 5 3 7 1 3 5 3 9 1 3 5 5 3 1 3 5 5 5 1
3 5 5 7 1 3 5 5 9 1 3 5 7 3 1 3 5 7 5 1 3 5 7 7 1 3 5 7 9 1 3 5 9
3 1 3 5 9 5 1 3 5 9 7 1 3 5 9 9 1 3 7 1 5 1 3 7 1 7 1 3 7 1 9 1 3
7 3 3 1 3 7 3 5 1 3 7 3 7 1 3 7 3 9 1 3 7 5 3 1 3 7 5 5 1 3 7 5 7
1 3 7 5 9 1 3 7 7 3 1 3 7 7 5 1 3 7 7 7 1 3 7 7 9 1 3 7 9 3 1 3 7
9 5 1 3 7 9 7 1 3 7 9 9 1 3 9 1 5 1 3 9 1 7 1 3 9 1 9 1 3 9 3 3 1
3 9 3 5 1 3 9 3 7 1 3 9 3 9 1 3 9 5 3 1 3 9 5 5 1 3 9 5 7 1 3 9 5
9 1 3 9 7 3 1 3 9 7 5 1 3 9 7 7 1 3 9 7 9 1 3 9 9 3 1 3 9 9 5 1 3
9 9 7 1 3 9 9 9 1 5 1 5 3 1 5 1 5 5 1 5 1 5 7 1 5 1 5 9 1 5 1 7 3
1 5 1 7 5 1 5 1 7 7 1 5 1 7 9 1 5 1 9 3 1 5 1 9 5 1 5 1 9 7 1 5 1
9 9 1 5 3 1 7 1 5 3 1 9 1 5 3 3 3 1 5 3 3 5 1 5 3 3 7 1 5 3 3 9 1
5 3 5 3 1 5 3 5 5 1 5 3 5 7 1 5 3 5 9 1 5 3 7 3 1 5 3 7 5 1 5 3 7
7 1 5 3 7 9 1 5 3 9 3 1 5 3 9 5 1 5 3 9 7 1 5 3 9 9 1 5 5 1 7 1 5
5 1 9 1 5 5 3 3 1 5 5 3 5 1 5 5 3 7 1 5 5 3 9 1 5 5 5 3 1 5 5 5 5
1 5 5 5 7 1 5 5 5 9 1 5 5 7 3 1 5 5 7 5 1 5 5 7 7 1 5 5 7 9 1 5 5
9 3 1 5 5 9 5 1 5 5 9 7 1 5 5 9 9 1 5 7 1 7 1 5 7 1 9 1 5 7 3 3 1
5 7 3 5 1 5 7 3 7 1 5 7 3 9 1 5 7 5 3 1 5 7 5 5 1 5 7 5 7 1 5 7 5
9 1 5 7 7 3 1 5 7 7 5 1 5 7 7 7 1 5 7 7 9 1 5 7 9 3 1 5 7 9 5 1 5
7 9 7 1 5 7 9 9 1 5 9 1 7 1 5 9 1 9 1 5 9 3 3 1 5 9 3 5 1 5 9 3 7
1 5 9 3 9 1 5 9 5 3 1 5 9 5 5 1 5 9 5 7 1 5 9 5 9 1 5 9 7 3 1 5 9
7 5 1 5 9 7 7 1 5 9 7 9 1 5 9 9 3 1 5 9 9 5 1 5 9 9 7 1 5 9 9 9 1
7 1 7 3 1 7 1 7 5 1 7 1 7 7 1 7 1 7 9 1 7 1 9 3 1 7 1 9 5 1 7 1 9
7 1 7 1 9 9 1 7 3 1 9 1 7 3 3 3 1 7 3 3 5 1 7 3 3 7 1 7 3 3 9 1 7
3 5 3 1 7 3 5 5 1 7 3 5 7 1 7 3 5 9 1 7 3 7 3 1 7 3 7 5 1 7 3 7 7
1 7 3 7 9 1 7 3 9 3 1 7 3 9 5 1 7 3 9 7 1 7 3 9 9 1 7 5 1 9 1 7 5
3 3 1 7 5 3 5 1 7 5 3 7 1 7 5 3 9 1 7 5 5 3 1 7 5 5 5 1 7 5 5 7 1
7 5 5 9 1 7 5 7 3 1 7 5 7 5 1 7 5 7 7 1 7 5 7 9 1 7 5 9 3 1 7 5 9
5 1 7 5 9 7 1 7 5 9 9 1 7 7 1 9 1 7 7 3 3 1 7 7 3 5 1 7 7 3 7 1 7
7 3 9 1 7 7 5 3 1 7 7 5 5 1 7 7 5 7 1 7 7 5 9 1 7 7 7 3 1 7 7 7 5
1 7 7 7 7 1 7 7 7 9 1 7 7 9 3 1 7 7 9 5 1 7 7 9 7 1 7 7 9 9 1 7 9
1 9 1 7 9 3 3 1 7 9 3 5 1 7 9 3 7 1 7 9 3 9 1 7 9 5 3 1 7 9 5 5 1
7 9 5 7 1 7 9 5 9 1 7 9 7 3 1 7 9 7 5 1 7 9 7 7 1 7 9 7 9 1 7 9 9
3 1 7 9 9 5 1 7 9 9 7 1 7 9 9 9 1 9 1 9 3 1 9 1 9 5 1 9 1 9 7 1 9
1 9 9 1 9 3 3 3 1 9 3 3 5 1 9 3 3 7 1 9 3 3 9 1 9 3 5 3 1 9 3 5 5
1 9 3 5 7 1 9 3 5 9 1 9 3 7 3 1 9 3 7 5 1 9 3 7 7 1 9 3 7 9 1 9 3
9 3 1 9 3 9 5 1 9 3 9 7 1 9 3 9 9 1 9 5 3 3 1 9 5 3 5 1 9 5 3 7 1
9 5 3 9 1 9 5 5 3 1 9 5 5 5 1 9 5 5 7 1 9 5 5 9 1 9 5 7 3 1 9 5 7
5 1 9 5 7 7 1 9 5 7 9 1 9 5 9 3 1 9 5 9 5 1 9 5 9 7 1 9 5 9 9 1 9
7 3 3 1 9 7 3 5 1 9 7 3 7 1 9 7 3 9 1 9 7 5 3 1 9 7 5 5 1 9 7 5 7
1 9 7 5 9 1 9 7 7 3 1 9 7 7 5 1 9 7 7 7 1 9 7 7 9 1 9 7 9 3 1 9 7
9 5 1 9 7 9 7 1 9 7 9 9 1 9 9 3 3 1 9 9 3 5 1 9 9 3 7 1 9 9 3 9 1
9 9 5 3 1 9 9 5 5 1 9 9 5 7 1 9 9 5 9 1 9 9 7 3 1 9 9 7 5 1 9 9 7
7 1 9 9 7 9 1 9 9 9 3 1 9 9 9 5 1 9 9 9 7 1 9 9 9 9 3 3 3 3 3 5 3
3 3 3 7 3 3 3 3 9 3 3 3 5 5 3 3 3 5 7 3 3 3 5 9 3 3 3 7 5 3 3 3 7
7 3 3 3 7 9 3 3 3 9 5 3 3 3 9 7 3 3 3 9 9 3 3 5 3 5 3 3 5 3 7 3 3
5 3 9 3 3 5 5 5 3 3 5 5 7 3 3 5 5 9 3 3 5 7 5 3 3 5 7 7 3 3 5 7 9
3 3 5 9 5 3 3 5 9 7 3 3 5 9 9 3 3 7 3 5 3 3 7 3 7 3 3 7 3 9 3 3 7
5 5 3 3 7 5 7 3 3 7 5 9 3 3 7 7 5 3 3 7 7 7 3 3 7 7 9 3 3 7 9 5 3
3 7 9 7 3 3 7 9 9 3 3 9 3 5 3 3 9 3 7 3 3 9 3 9 3 3 9 5 5 3 3 9 5
7 3 3 9 5 9 3 3 9 7 5 3 3 9 7 7 3 3 9 7 9 3 3 9 9 5 3 3 9 9 7 3 3
9 9 9 3 5 3 5 5 3 5 3 5 7 3 5 3 5 9 3 5 3 7 5 3 5 3 7 7 3 5 3 7 9
3 5 3 9 5 3 5 3 9 7 3 5 3 9 9 3 5 5 3 7 3 5 5 3 9 3 5 5 5 5 3 5 5
5 7 3 5 5 5 9 3 5 5 7 5 3 5 5 7 7 3 5 5 7 9 3 5 5 9 5 3 5 5 9 7 3
5 5 9 9 3 5 7 3 7 3 5 7 3 9 3 5 7 5 5 3 5 7 5 7 3 5 7 5 9 3 5 7 7
5 3 5 7 7 7 3 5 7 7 9 3 5 7 9 5 3 5 7 9 7 3 5 7 9 9 3 5 9 3 7 3 5
9 3 9 3 5 9 5 5 3 5 9 5 7 3 5 9 5 9 3 5 9 7 5 3 5 9 7 7 3 5 9 7 9
3 5 9 9 5 3 5 9 9 7 3 5 9 9 9 3 7 3 7 5 3 7 3 7 7 3 7 3 7 9 3 7 3
9 5 3 7 3 9 7 3 7 3 9 9 3 7 5 3 9 3 7 5 5 5 3 7 5 5 7 3 7 5 5 9 3
7 5 7 5 3 7 5 7 7 3 7 5 7 9 3 7 5 9 5 3 7 5 9 7 3 7 5 9 9 3 7 7 3
9 3 7 7 5 5 3 7 7 5 7 3 7 7 5 9 3 7 7 7 5 3 7 7 7 7 3 7 7 7 9 3 7
7 9 5 3 7 7 9 7 3 7 7 9 9 3 7 9 3 9 3 7 9 5 5 3 7 9 5 7 3 7 9 5 9
3 7 9 7 5 3 7 9 7 7 3 7 9 7 9 3 7 9 9 5 3 7 9 9 7 3 7 9 9 9 3 9 3
9 5 3 9 3 9 7 3 9 3 9 9 3 9 5 5 5 3 9 5 5 7 3 9 5 5 9 3 9 5 7 5 3
9 5 7 7 3 9 5 7 9 3 9 5 9 5 3 9 5 9 7 3 9 5 9 9 3 9 7 5 5 3 9 7 5
7 3 9 7 5 9 3 9 7 7 5 3 9 7 7 7 3 9 7 7 9 3 9 7 9 5 3 9 7 9 7 3 9
7 9 9 3 9 9 5 5 3 9 9 5 7 3 9 9 5 9 3 9 9 7 5 3 9 9 7 7 3 9 9 7 9
3 9 9 9 5 3 9 9 9 7 3 9 9 9 9 5 5 5 5 5 7 5 5 5 5 9 5 5 5 7 7 5 5
5 7 9 5 5 5 9 7 5 5 5 9 9 5 5 7 5 7 5 5 7 5 9 5 5 7 7 7 5 5 7 7 9
5 5 7 9 7 5 5 7 9 9 5 5 9 5 7 5 5 9 5 9 5 5 9 7 7 5 5 9 7 9 5 5 9
9 7 5 5 9 9 9 5 7 5 7 7 5 7 5 7 9 5 7 5 9 7 5 7 5 9 9 5 7 7 5 9 5
7 7 7 7 5 7 7 7 9 5 7 7 9 7 5 7 7 9 9 5 7 9 5 9 5 7 9 7 7 5 7 9 7
9 5 7 9 9 7 5 7 9 9 9 5 9 5 9 7 5 9 5 9 9 5 9 7 7 7 5 9 7 7 9 5 9
7 9 7 5 9 7 9 9 5 9 9 7 7 5 9 9 7 9 5 9 9 9 7 5 9 9 9 9 7 7 7 7 7
9 7 7 7 9 9 7 7 9 7 9 7 7 9 9 9 7 9 7 9 9 7 9 9 9 9 9
Happy hacking!