Decoding Locks

You are standing outside your house; you use a combination lock as your front door lock. You have forgotten your combination, and it’s started to rain. How do you get into your house in the most efficient way possible?

You stand there and ponder this for a few minutes until you realise you have a cup of tea getting cold on your worktop. Now it’s serious. If only you paid more attention in Maths, you might be able to think of a sequence that included all of the combinations of the numbers on your lock.

You know your lock only has two digits 0 and 1, it also requires a 4 digit passcode. We need to find a logical way to go through and form an efficient sequence, more efficient than button mashing. In your confusion, you find some chalk on the ground and start drawing diagrams. Which look much like graphs and finally something clicks, De Bruijn Sequences, you remember them from one of your midnight Wikipedia binges.

De Bruijn Sequences are ways of representing all the combinations of n-words on a certain alphabet. On our lock, we need 4-words on a 2 alphabet. The sequences were named after Dutch mathematician Nicolaas Govert de Bruijn after he wrote about them in 1946. The case of our predicament is one of his first proofs. We also know about the number of distinct sequences for each type of $k$-words and $n$-alphabets.

$$ \frac{(k!)^{k^{n-1}}}{k^n} $$

We also know of a link between Graphs, Hamiltonian Paths and these sequences. If each vertex is equivalent to a 3-word, i.e. $110$, and we name the arcs or arrows as an extra letter, i.e. $1$, then we create what is known as a De Bruijn graph. We also know that these graphs will lie in $k-1$ dimensions.

A De Bruijn Graph for the lock.

We can then take a Hamiltonian path of this graph, producing the required sequence to put into our lock! We also note that there are loops at the $000$ word with a $0$-letter and at $111$ with the $1$-letter.

The Hamiltonian Path of the graph

We can now read off the path from the letters, remembering the extra loops, starting at the $000$ – $000$ loop. 0000111101100101 is what we read off. We can enter this whole sequence, and the lock will unlock by the time we enter the last digit.

One last little thing, if you line up all of the nodes we have in the order $000, 001,010, 011, 100, 101, 110, 111$ and curve the arcs around nicely, what shape do you achieve? Does it resemble something else in Mathematics?

Leave a Reply

Your email address will not be published. Required fields are marked *