Can you crack the combination lock? - Solution

Duration: 12 mins 8 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1198283/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	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.


Created:	2011-12-18 02:39
Collection:	Quite Easily Done
Publisher:	University of Cambridge
Copyright:	Dr J.R. Grime
Language:	eng (English)
Keywords:	maths; math; mathematics; problem; puzzle; combinatorics; lock; code; break; crack; sequence; De Bruijn; Lyndon words; graph; hamiltonian path; eulerian path;


Abstract:	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).

Abstract:

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).

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.78 Mbits/sec	162.31 MB	View	Download
iPod Video	480x270	488.09 kbits/sec	43.44 MB	View	Download
MP3	44100 Hz	125.04 kbits/sec	10.93 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)