Can you crack the combination lock? - Solution
Duration: 12 mins 8 secs
Share this media item:
Embed this media item:
Embed this media item:
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) |
| Distribution: |
World
(downloadable)
|
| Keywords: | maths; math; mathematics; problem; puzzle; combinatorics; lock; code; break; crack; sequence; De Bruijn; Lyndon words; graph; hamiltonian path; eulerian path; |
| Categories: |
iTunes - Mathematics |
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| 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) | |||||