So Brady,
my good friend Éric Angelini, who lives in Brussels,
he came up with the following operation. This is an operation,
you can take a number and you can transform it. If you start off with 123,
if you look at the first two digits, it says 12.
You're allowed to half that. Divide it by 2 and you would get 63. That's a legal operation,
take a sub number and divide it by 2 if it's even, or you could double the number. You could also take the 2
and you could double it, and you'd get 143.
Or you could double the 3 and you'd get 126.
Or you could double the 23 and you would get 146.
Or you could double the 1 and you would get 223.
So those are examples of things you can do. Let's take something like 20218,
there's a nice big number.
You can focus your attention on any sub number in there.
So for instance if we look at that 2, that's an even number we can divide it by 2. And that would give us 10218
Now we have a choice, and in fact I call this choix de Brussels,
it's Brussels choice, because in honour of Éric. You could also take the
202 and divide it by 2, and you would get 10118.
And you can do any substring. If it's even you can either divide it by 2,
or double it, in place.
If it's odd, you can just double it. - (Brady: And you can choose that and it's completely arbitrary where you attack, right?)
Yes, you're free to choose, but you have a target because you're trying to get back down to 1.
(Brady: That's the game?) - That's the game, get to - or conversely,
because this is a symmetric operation, if you can go from x to y you can equally well go from y to x.
Every - these operations are reversible. - (Brady: And what, are we iterating here are we? We're going in steps?)
Yes. Oh but I want to show you one more example here because this is the surprise. This is the joke.
From 20218,
if I pick that 8
and double it, we get 202116.
That 8 has become 16 in place,
I'm keeping the 2021 but i'm doubling the 8. And we get
202116
or I could take that 18 and divide it by 2 and we would get
2029.
And we've shortened the length
by one
digit. It's not difficult to prove that if you start with a number n, what you get by this operation is at most 10n.
And at least n over 10. You can find examples which gets you arbitrarily close to n over ten.
So there's a wide range of numbers. Okay, so - - (Brady: That rule's with one step, obviously?) - That's with one step, yes. And then the question is
if you start off with a random number
how long will it take to get to 1? Is it even possible to always get to 1?
(Brady: Is it? You know, I don't - I want to know.) - Yes. Well, - (Brady: Show me an example of getting to 1.) - Okay, yes.
Well,
so let me go the other way around and let's go from 1,
and see what we can get, because it's symmetric. From 1 we can go to 2,
in fact we can only go to 2. From 2 we can go to 4, from 4 we can go to 8,
from 8 we can go to 16, from 16 we can go to 112. This is the crucial step.
We double that 6 and we get 112. From 112
we can divide by 2 and go to 56,
from 56 we can divide by 2 and go to
28. From 28 we can divide that 8 by 2 and go to 24,
then bingo! 12, 6, 3. 3 is hard to get to from 1,
but you can do it. And it took one, two, three, four, five, six,
seven, eight, nine, ten, eleven steps
to go from 1 to 3. And if you want to have some fun figure out how to go from 1 to
7 say, or 9 or 73. - (Brady: Oh, you completely changed the game on me)
(then, I thought this whole game was going to be about taking arbitrary numbers and getting down to 1.) - It is.
But I'm reversing it - - (Brady: Now you've just built a new game where you go up - ) - You go, oh you start it,
but these steps are reversible. Well, all right, we start at 3, how do we get to 1?
We double it we get 6, double it again 12, double it again we get 24, double the 4 - 28.
Double it again 56, 100 - ah now at 112
we can divide that 12 by 2 and get 6
so it goes to 16 and then 8, 4, 2, 1. - (Brady: If I give you any number can we always get to 1?)
Yes,
so that's a very good question and the answer is no. Look at all the numbers in the world.
All the positive integers in the world. There are two kinds - those that end in 0 or 5,
and they're all connected,
and those that don't end in 0 or 5 and they're all connected.
So I can get from 1 to 73, and I can get from 1 to 74,
but I can't get from 1 to 10, or 1 to 90 or 95 because they end in a 5. If the last digit
was a 0 or a 5 that doesn't change under these operations.
(Brady: So that will never get to 1 because I - it will always end with a 0 or a 5?) - Yes.
(Brady: Okay) - And let me prove that you can always get to 1
if
it doesn't end in a 0 or a 5. All right suppose that's not true. Look at the smallest number
that cannot get to 1. Let's call it K.
K never gets to 1, no matter how clever we - how hard we try. And K doesn't end in 0 or 5,
that's the claim. Suppose you could get from K to a smaller number,
then that would be a counter example because if you get from K to say L, and L is less than K,
L would be a smaller number that you could not get to 1 from. Because this - the operation is reversible.
So every number that you can get from K must be bigger than K. So that means look at the digits of K.
We can't have a 6
because if we did we'd have it, and we'd get a smaller number, from K. - (Brady: Because you could get to 3?)
Yeah, we'd halve that number, halve the 6 digit and we get the 3 and that would be smaller than K. So every
digit of k must be odd,
okay?
And what's more,
it can't be 3. There can't be a 3 digit in K because
we could do this to it and get it down to 1.
And that would be a smaller number.
This chain takes you from 3 to 1.
This chain takes you from 2 to 1. I didn't show you how to go from 7.
Okay, when we got to 28, I could go to 14 by halving the whole number and halving it again to 7.
So 7 via 7, 14, 28, 56;
7 goes to 1.
And what about 9? If I could do 9, I will have done all the digits, the single digits
except 5 and 0. And 5 and 0 you can't do, we can't handle them.
So, how do I get to 9?
18 would be good. So from 14 I can double the 4 and get 18.
I can halve the 18 and get 9. So 9 is connected to 1. So all the numbers between 1 and
9 are joined to 1 except 5 and 0. - (Brady: So K can't have a 1, a 2, a 3, a 4 - ) - It could have,
It could be, it could have a 1. It could be all 1s.
Or it could have a 5 in the middle of it. K could be maybe
1151. That's,
so far I haven't ruled that out because you can't get from 5 to 1.
So all the digits of K are 1s and 5s. Okay, so
if there was a 5 in the interior of it, well
it would have to be followed by a 1. From 51
we can go to 52, double the 1. We can go to 26 and 26 is less than 51.
So we've got a - reached a smaller number. - (Brady: So could the 5 be followed by another 5? - Yes it did,
but the last 5 must be followed by a 1.
So this argument works. Just look at the the right-most 5 and we get a smaller number.
What about a number that's all 1?
K,
so the argument so far has shown that K must be all 1s. Well, all right. Look at the last two 1s.
Double it, make it a 12. Halve it, make it a 6. So we've changed 11 to a 6, we've got a smaller number - contradiction.
So K does not exist. So every number
not ending in a 0 or a 5 can get to 1. And conversely because these operations are symmetric,
we can go from 1 to any number not ending in 0 and 5. Now,
what about the other numbers? The numbers that do end in 0 or 5? Well, the they're all connected,
maybe if I switch to red and show you that.
We can get from 90 to 10 because whatever this number is we can get from 117930,
we can get
to 10.
Proof?
This number
doesn't end in 0 or 5, therefore we can get to 1 from it. So we get to 10, and then we get to 5.
So the other class of numbers are all connected. We use the first argument
to get everything down to 10. - (Brady: But never the twain shall meet.) - Never the twin shall meet. There are two, two connected components.
Okay,
so the question is, if you start with a big number how many steps is it going to take
to get down to 1? Assuming it ends - it doesn't end in 0 or 5.
There are two parts to that. One is to look at what's the biggest number you can get from 1 in K steps?
And the answer is, basically you can use the greedy algorithm. In one step
all we can do is go to 2. In two steps all you can do is get to 4, and then 8, and then
16. From 16 the biggest - one two, three four -
the biggest thing you can get is 112 by doubling the 6. The rule is if you want to get the biggest number
you look for a digit which is bigger than 5
and as far to the right as possible and you double that. If it's a 6 you go from that 6
all the way to the end and you double that string.
And that's the biggest child, the biggest number you can get in, in that step. From 16
it's pretty clear
the best you can do is double the 6 in place and we get
112, one-twelve, which we read, which is a hundred and twelve. All we can do is double
the whole number so we get 224.
From 224 all we can do is double it.
And we get 448. And when we double the 8 we get 4416. And now we've got a 6,
so we get 44112,
this is doing the greedy algorithm.
It's possible that we could get a bigger number by not being greedy,
but being more devious, and taking a more circuitous route
and after a certain number of steps, getting a bigger number than we would get from this.
So now there's no digit bigger than 5, so we just double it. And we get eight, eight,
two, two, four.
Finally, here,
we have digits that are bigger than 5.
And we look for the right most one of them and that's the 8, which is furthest to the right.
And we double the number starting at that 8 all the way to the end.
So what we get is the 816448.
Now, again, we have numbers that are 6 or higher and we look for the rightmost one
which is the final 8. Means we just double that 8 in place and we get 8164416,
the 8 becomes a 16. We've lengthened the number by one digit and we've done this in the optimal way. If we had
doubled the number from the 6 onwards we'd get a smaller number
because that 6 would become a 12 and the number would begin 811.
By keeping the 6,
and just doubling the final 8, we keep the start 816. So this is bigger than doing anything else.
Let's keep going. Again
we look for the rightmost digit which is bigger than or equal to 6 and that's, that 6 at the end. Again
we look for the rightmost digit that's 6 or higher and
we double
from there
all the way to the end. Again, look for the the rightmost digit, which is 6 or more and that's this 8,
so we double from there to the end. So that's going to give us - I want to keep
81128 and now we double this and we get 16448. And in a minute
we'll see a pattern. Let's go one more step. We just double the 8 and we get
81128164416. There's a 6 at the end,
let's double that. 8112816441,
the 6 becomes a 12.
And now we can see the pattern. That number is the same as this number.
And in one, two,
three, four steps; what has happened is we took that number and we put a prefix in front of it, 8112.
(Brady: Oh, yeah)
So from this point on there's a simple rule for the biggest number you can get using n steps starting at 1.
And it grows,
by every four steps, it grows by putting
8112 in front of it.
Which is like multiplying it by adding four digits at the end. If the number is bigger than this
then we know we can't get to it by going in, by taking - one, two, three, four, five, six,
seven, eight, nine, ten, eleven, twelve - if a number is bigger than this we need more than twelve steps to get to it.
So this gives us a lower bound on how many steps we need to get to n. We know that we can get down,
from skipping 5,
we can get from
any digit,
1 through 9, we can get down to 1 in at most eleven steps.
You may remember that it took me eleven steps to get from 1 to 3 or from 3 to 1. So this is eleven steps,
in fact
any number between 1 and 99, not ending in 0 or 5, gets down to 1 in at most twelve steps.
So if we start off with some huge number, and we want to get to 1,
we look at the first two digits and we apply
at most 12 steps and change the - whatever it is - we change it to a 1. I should also say that we can get from
any number that ends in 0 or 5, we can get down to 5 in at most twelve steps, the same thing.
In short,
any two digit number
we can reduce to either 1 or 5 in at most twelve steps.
So say we have some huge number, we want to get to 1, we just whittle away.
We look at the top two digits and map them to either 1 or 5 and we repeat that.
And each time we do that it's taking, it's costing us at most twelve steps.
So roughly speaking 12 times
the number of digits in the number is an upper bound on how far we have, how many steps we need to take
to get down to 1.
Now when I was younger, I was taught
not to play with matches like these, but I think we can make an exception for today's episode sponsor, Brilliant.
Now have a look at this, can you see the fifth square in this arrangement?
Can you make four squares here by removing five matches?
These are just examples of the sorts of puzzles you're gonna find on Brilliant.
And there are loads of great courses too, like the ones you're seeing on screen now.
These are pretty elaborate courses with lots of steps to go through, they're fun,
interactive and elegantly designed by people who really know their stuff. To find out more go to
brilliant.org/numberphile where you can peruse all this stuff. And using that /numberphile will also line you up for 20%
off Brilliant's premium subscription which unlocks all the good stuff. And remember always be careful and thoughtful with matches,
real ones and mathematical ones.