Can you crack the combination lock? - Solution

The sequence 11221 contains all 2-digit combinations using the numbers 1 and 2.

A sequence such as that is called a De Bruijn sequence. I show you three methods to find such sequence. The first two involve making diagrams called graphs, and either taking a path that visits every node of a graph (a hamilton path), or a path that visits every edge of a graph (euler path). The third method is an algorithm for making 'Lyndon words' which if you string them together will make our De Bruijn sequence.

De Bruijn Sequences: http://en.wikipedia.org/wiki/De_Bruijn_sequence

Hamilton Path: http://en.wikipedia.org/wiki/Hamiltonian_path

Euler Path: http://en.wikipedia.org/wiki/Eulerian_path

Lyndon Words: http://en.wikipedia.org/wiki/Lyndon_word


There is an efficient method of generating a list of all Lyndon words of lengths that divide n, using the digits 1 to k, which involves a lot less crossing off. This is the method I used to make the final sequence in the video. I did not describe the method in the video, so let me describe it here:

Start the list with a sequence of n 1s, i.e. 11 . . . 1. We will generate successive words until we reach kk . . . k. For any word A = a1a2 . . . an, the successor of A is obtained as follows:

1. Let i be the largest value such that ai is less than k
2. Let B = a1a2 . . . ai-1(ai + 1)
3. Then the successor of A is the first n characters of BB . . . B.

We then decided to reject, replace, or keep the successor of A depending on the value of i:

1. If i does not divide n, the successor of A appears earlier on the list under rotation. Generate a successor to the word before removing it from the list.
2. If i divides n but not equal to n, the successor of A is periodic. Generate a successor to the word then replace BB . . . B with B. Replace 11 . . . 1 at the start of the list with 1.
3. If i = n we keep the successor of A.

This creates a list of Lyndon words, of lengths that divide n, written in lexicographic order.

Together, this list creates a De Bruijn sequence of length k^n, containing all the combinations of length n (if the sequence wraps around) using the digits 1 to k.


Ok then, here's an extra one for you to try. Use the algorithm to give me a sequence containing all 6-digit combinations using the numbers 1 and 2. So combinations like 111111, 112121, 211122 etc. The sequence is 64-digits long (if you let the sequence wrap back to the start).

Category:

Education

Tags:

• maths
• math
• mathematics
• problem
• puzzle
• combination
• lock
• code
• break
• crack
• sequence
• combinatorics
• de
• brujin
• lyndon
• words
• graph
• theory
• euler
• eulerian
• hamilton
• hamiltonian
• path
• cycle
• circuit
• computing
• robotics
• dna
• sequencing

[jamma246]

How much more efficient is the De Bruijn sequence than trying every combination?

Are there known limits as things tend towards infinity for the ratio between the length of a De Bruijn sequence of k symbols of length n and the number where you just try each combination once? E.g. if we fix k, is there a limit of this ratio as n tends towards infinity? Perhaps if k=n, and k tends towards infinity? etc.

[singingbanana]

@jamma246 There are k^n combinations of length n using k digits. So trying every combination involves n*(k^n) digits. A De Bruijn sequence has length k^n. So the ratio is 1/n.

[guppiemagic101]

am i the only one that actually wants to see the card trick?

[culwin]

"Only a crazy person would attempt to write out that sequence."

"I've done it here..."

LOL

[Wallencis1]

--- Which comes before YMCA...

[PouringRain21]

so you wrote this sequence twice?!? madman squared!

[IMakeOrWatchVideos]

@Eroll91 ok now i get it. so this is if order does not matter.

[swcomer]

At 5 mins, why would you take the last 2 digits of the end? Then, you lose the 311 combination.

[cappydawg]

Felt like I was in the Matrix at the end...

[livedandletdie]

English(US, UK, AUS...) peoples passwords are easier to crack thanks to this principle than it's to crack a scandinavian password as english people have 102 possible symbols in their passwords while swedes norwegians and danish people have 108. so let's have a 8 symbol lock.

English have 102^8=11716593810022656

Swedes have 108^8=18509302102818816

thank language for us having 3 extra letters than you guys.

[PoketoMtg]

I would love to see a HS/College math contest ask this type of question. I shall be prepared when it comes :D.

[Muscleduck]

@RectumPilum Haha I haven't got a clue as to how to even start with something like that :)

[RectumPilum]

@Muscleduck you're mad! Tell me when you're done and put up a video on Youtube =P