Hello everyone, last time I gave you a problem about a combination lock
that uses digits 0 to 9
and it accepts a 4-digit
combination. And I asked you if you want to do
crack the lock,
what was the shortest sequence of numbers
that you would have to enter
that contains every possible 4-digit
combination. Now,
we're gonna find the solution
to this problem. These sort of sequences
are called de Bruijn sequences.
This is named after a dutch mathematician Nicolaas de Bruijn
and I'm trying to do the dutch
pronunciation. I'm sure I'm getting that wrong. If I am
I will be corrected. Of that I have no doubt.
These are used
In fact in lots of places. They're used in computing,
robotics,
DNA sequencing even. They
chop up the DNA and then they...
they fit the sequence together using this
sort of principle. There's even a card trick
that uses this principle. Which maybe I'll
show you sometime.
Now, we're gonna try and do this. I'm gonna show you 3
ways to solve this sort of problem.
And I'll be honest with you, this is not going to be
the easiest video I've ever made.
There's gonna be some new ideas in it,
some new words,
I'm gonna explain them as I go along.
So if you're with me, come on, let's do it.
Let's start with an easy example.
Last time I showed you that the sequence
11221
contains every possible 2-digit combinations of the numbers
1 and 2.
So, how would I make a sequence like this? So,
one way you could do it is to write out
all the combinations that you're interested in.
So if I write out
all the 2-digit combinations
of 1 and 2.
So for example
11, 12, 22 and 21.
Now I'm gonna join these combinations together
with an arrow,
if I can add a digit to the end of the combination
and it overlaps with another one.
For example, if I added a 2
onto the end of the combination 11,
it would be 112,
which overlaps with
12. I'm gonna join them together with an arrow.
There we go.
On the other hand, if I started at 11
and I added a 1 to the end,
I would get 111,
which actually overlaps with itself,
the "overlap" goes round back to 11.
So, continuing in this way, you get a diagram called a graph.
Now all you have to do is find a path,
that visits every node of the graph
exactly once.
So, starting at 11: I get 11,
12,
22, and 21.
Visiting every node exactly once is called a Hamilton path.
Now, another way to do this is to
not write out all the 2-digit combinations
but to actually write out all the combinations of length one less.
Then that which is, in this case, combinations of length 1.
Which in fact is just the numbers 1 and 2.
Now we do the same sort of idea, we join them together
with an arrow
if we can add a digit to the end and
the two combinations
overlap. So if I start at 1,
and I add a 2 to the end,
I would get 12,
which overlaps with the combination
2. So I'm going join that
together
with an arrow.
If I started at 1,
and I added a 1 to the end, I would get 11,
which actually loops back
to itself.
So I will do that as well.
And if you continue again in this way,
you'll gonna get another diagram
like this.
This time I want to find the path that visits every
edge exactly once.
So starting at 1: you get 1
1
2
1.
And you visited
every edge exactly once.
And this sort of path is called an Euler path.
So if you want all the combinations of length n,
you can either write out all the combinations of length n
and find the Hamilton path,
or you write out all the combinations of length (n-1)
and find the Euler path.
So let's try and do a harder one.
This time I'm going to use the Euler path method,
to find a sequence
that contains all 3-digit combinations of the numbers
1, 2 and 3.
And if you do that you'll get a graph that looks like this.
And look at that, it's now a beautiful thing.
It contains all the combinations of length
"1 less than 3", so it's all the combinations of length 2.
And we want to find a path that uses
every edge exactly once.
Here's one such sequence.
It starts at 11,
and then it continues, so it goes 11,
1,
2,
1,
3,
1, and so on.
In fact, these path are cycles,
they loop back where they started.
So you don't even need the last 2 digits.
You can think of these sequences as wrapping around.
So the number of de Bruijn sequences
is equal to the number of Euler cycles.
In this case, we have
373,248 solutions.
Now, that sounds like a lot, but
that's out of about 8.5 billion ways you could write a sequence
using the same digits.
Now that graph method is pretty close
to what some of you were describing
in the Youtube comments
as, some of you were talking about writing out the combinations,
so that they overlapped with each other and
crossing them of if they were too long.
And I had about
40 entries for this particular problem, and
I think about half of them were right, I can
tell you some of the winners.
It's only some of the more pronuncable ones.
Everyvideo123 got it right.
GammahooX got it right.
Kitkatchunky93 - nice name - got it right.
Wopaah got it right.
So, HappymemoryXD
which I think is a emoticon, so it's Happymemory...
got it right.
And Fishpizza1212 got it right
- duff name, you should get a proper name, like I have.
And Mr Kuran's 3rd hour discrete math class
got it right, but
does Mr Kuran know that you're watching Youtube videos
when you should be doing your homework?
In general, if you were interested in finding
all the combinations of length n,
using k digits
well there are k to the power n such combinations.
And every digit of a de Bruijn sequence is the start
of a new combination.
So if it's a sequence that wraps around
it has a length
k to the power n.
Now if we were interested in finding how many Euler paths
there were for that graph.
That's equal to the number of solutions to this problem.
And that is equal to this horrible thing
It's k factorial
to the power
k to the power (n-1)
divided by
k to the power n. Yeah, it is a horrible thing.
But that formula
is the one I use
to find the total number of ways
to find solutions for
3-digit combinations using the numbers 1, 2, 3.
which was 378,248.
Now if you want to do a harder problem,
like for example
how many 4-digit combinations
using digits 1,2,3 and 4,
then that graph is gonna get pretty ugly. So,
mathematicians have come up with a efficient algorithm to do it instead.
I'm going to show you how that works.
So this algorithm I'm going to explain to you now,
is probably gonna be pretty new to you
but we're gonna use it to solve this problem of finding a sequence
that contains all our
4-digit combinations
using the numbers 1, 2, 3 and 4.
So, the first thing that we do,
is we list
all the combinations of length 4.
But not only that,
we also list all the combinations of length that divide 4.
So it's the combinations of length 2,
and combinations of length 1.
But we don't include combinations of length 3.
Because that doesn't divide 4.
In general, what you do is you make a list
of all the combinations of length n,
and all the combinations of length that divide n.
Now, we're gonna order
these combinations in something called lexicographic order.
That's a fancy word for something you already know.
That's the same order that you would use if you were
ordering words in a dictionary. So it's dictionary order.
So although these aren't words,
they're in dictionary order.
So A comes before AA,
which comes before AAAA
which comes before AAAB, and
AAAC, and so on. So,
That comes before ABAA and ABAB...
comes before B and comes before BA...
and so on. It's dictionary order.
So we're gonna list our combinations using this,
and then we're gonna start to cross them off.
First of all,
we cross off all the combinations that are periodic.
So 11 would get crossed off,
and 1111
would get crossed off. These are periodic.
And combination 1212
gets crossed off. That's periodic.
The idea is, if you rotate the combination,
and you get something that you
already had, then you cross it off.
You also cross off combinations that,
if you rotate them, they already appear
earlier on in the list.
So you would cross off 1211,
because if you rotate it, you would get 1112,
and that's already appeared earlier on in the list.
You cross off 2111
for the same reason.
Now, you string all those combinations together.
And that's it. That's your solution. That
is the sequence that contains
all the 4-digit combinations of the numbers
1, 2, 3 and 4. You can do it!
And you can do it yourself. Maybe you want to try it out.
Now, if we go back to our original problem,
of solving a sequence that contains
all the 4-digit combinations
using digits 0 to 9,
now this sequence has length
10,000.
Now, only a crazy person will attempt to write out
that sequence.
I've done it here. This is my notepad.
The notepad of a madman.
And you can see I did actually write out the entire sequence.
I tell you, I'm not going read it out to you.
What we'll do, we'll end the video and I'll let it scroll past.
It's gonna take about a minute
to scroll past.
So while it does, you can enjoy the royalty-free music.
For now
if you have been,
thanks for watching.