So we're gonna do chemistry today.
Just kidding, I can't do any chemistry. But this one is for the chemists,
because we're gonna talk about something called the Centrifuge Problem.
Okay, so the centrifuge is this thing that chemists use to take test tubes and they
spin them to separate the contents of the test tube. Because it's something that's spinning at a very high speed
it needs to be balanced in order to work effectively. And so here's what the centrifuge problem is:
if you have a centrifuge with say n holes, let's say six, and you have k test tubes,
is it possible to balance the centrifuge? That's the question. Let's assume they're evenly spaced and on the edge,
let's assume the test tubes all have the same weight, that kind of thing; just to sort of idealise the problem.
It's hard enough as is. So that's the problem.
So if you look at this example,
so I've drawn this example with n equals 6. If k was equal to 1
we have no chance.
If you only have one test tube and you try and balance this thing, you're never gonna make it work,
right, because one side will be weighted because it's got the only test tube in there. So we can't balance it with one, right?
But we can balance it with two. We just put them opposite each other. Okay
so k equals 2 we can do. And similarly for 3 you could imagine putting one here, one here, and one there - and then the
centrifuge will be balanced because they're evenly spaced along the border. And so k equals 3 we can do it. And for k equals 4
you might not see right away that k equals 4 can be done,
but here's the thing: k equals 4, trying to balance that is the same problem as trying to balance k equals 2.
Right? Because if we have six spots total then missing two spots has the same weight balance as filling two spots.
Alright
so if k is equal to 4
we can do it, and maybe you either see that directly or you can think of it as being sort of the opposite of doing
two test tubes. Right, so rather than filling two, I'm leaving two empty.
So if one of them balances it, then so will the other, okay?
So yes, we can do k equals four. And for k equals five though
we again have no chance. For the same reason as k equals one, which is that if we leave one empty
then there's no chance of balancing this thing. And of course with six then we just fill every spot.
So right away if n is six we see that one and five are the bad configurations,
everything else is okay.
And if you're me and you like prime numbers the first thing you think to yourself is, well,
I see exactly when it can be done. It's when
k and n have some common factor.
Right? Because one and six they don't have a common prime factor, five and six don't have a common prime factor,
but every other number on this list does have a common factor with six. That was my guess when I first saw this problem. And
before I tell you how well my guess does
let me point out two things.
So one is that we've already discussed, which is doing this for k tubes is the same as doing it for n minus k tubes.
Right?
So if I can do it for,
say if n is six - if can do it for one I can do it for five, if I can't do it for one
I can't do it for five, and so on. So that's one thing to notice.
Maybe a more interesting thing to notice is that we can add up configurations,
right? So if I can balance some number of tubes, okay put them in the centrifuge, it's balanced.
Now if I have additional tubes and I can balance those,
then just add them in and I again stay balanced, right, because it's like adding zero to zero.
If you were balanced and then you add another balanced configuration on top of it
you stay balanced. If we want to think about the k equals four example, another way to think about it is two plus two.
I put one configuration here, that's balanced. And then I can choose any other configuration
that's balanced for the other two. And this will always work, this adding configurations,
so long as there is room for it. In this example the numbers are small and it's kind of okay,
there's a lot of room in this centrifuge. But it's not always gonna be true.
Okay? - (Brady: Okay, yup) - All right. So here's why I'm wrong.
Let's do an example with 12 spots.
Let's pretend these are all evenly spaced, like before, and so now we have n equals 12. And I claim that
we can actually balance this with seven tubes.
(Brady: That's a bold claim, cos that's not a common factor!) - It's a bold claim!
No common factors with 12,
in fact
it's a prime number and it's not any of the primes that divide 12. And it looks kind of weird, right, like I can't really
visualise
putting seven dots in here to balance this thing. But think about what I said a minute ago
about adding configurations. If I can do three in a balanced way, and I can do four in a balanced way,
as long as I can put them in here so they don't overlap
then I can do it. And that's exactly how we'll do this. Because 3 divides 12 I can just put them every four spots,
so there's 3 that are balanced. And same thing with 4, I can just put them every three spots and get something balanced.
So we'll put say one here; one, two, three; one, two, oh that's not gonna work,
it's already filled, right? So let's start again.
So can I do it by skipping every three? Well, if I start here I run into a filled spot,
we already tried starting here and I ran into a filled spot, if I start here
I'm gonna run into a filled spot over here,
so that configuration isn't gonna work. But it turns out there's actually a different four configuration that will work.
And the reason we know that is because 4 is 2 plus 2,
right? So let's not do 4, let's do 2 pairs of opposite tubes.
Here's one opposite pair and here's another opposite pair. And so even though this looks kind of strange,
I guess we've got 3 here and then 2 spaces and then 1, 2 and then a space.
Even though this configuration looks kind of strange, we know for sure it's balanced because it was the sum of three balanced configurations.
(Brady: Wow that's - that's balanced?)
Yeah! It's not obvious, even after you do it looking at it you're like, I don't know? How do I tell?
But because we've built it up from balanced configurations we know that it's balanced.
(Brady: So when you say balanced you're saying I could, you know, I could balance that on a pin?)
Yeah, that's right, that's right. I mean if you want to talk about centers of mass and that kind of thing
you should probably talk to a physicist.
For me I'll tell you the mathematical interpretation of this.
We've talked about complex numbers before and we've talked about the complex plane before,
so remember a complex number is a real number plus another real number times this i. And the way we
visualise it on the plane is just using the coordinates for the first and second real number, which I've written as a and b.
So here's my, like a and b.
So if I draw a circle on this plane that's centred at 0 and goes through the point 1, then I can draw this
centrifuge as a bunch of points on this circle. Let me do the 6 one,
it's a little easier. And it turns out that you can always write these complex numbers in terms of the first one.
So let's say this is z, then this is z squared,
this is z cubed, which is minus 1 actually, this is z to the fourth and this is z to the fifth.
And so the mathematical translation of this problem is, can I add together
powers of that one number z and get 0? Our very first
configuration, this was when we had four tubes in six spots, right? This is the same as saying,
so I have to rotate this picture a little bit
let's say this is my z - this is the same as saying z plus z squared
plus, and then I skipped a spot, and then z to the fourth,
plus z to the fifth
is equal to zero.
For that particular complex number. - (Brady: Ah, ok)
And so the way that you actually prove this is by showing that certain combinations like this of powers of some complex numbers
can add up to zero. But let's actually go back to the original thing. So we thought maybe at first
that the answer was having a factor in common, a prime factor in common. Now we know that that's not true
but it turns out that your next guess is true, which is if you think about this process, what did we do?
We took the number of tubes we had, we broke it down into prime factors,
and those we knew we could balance, right, just by spacing them evenly, as long as there was no overlap. And
it turns out that's exactly when this will work, is that you can balance the centrifuge if and only if both
the number of test tubes you have, which I've called k, and the number of empty spots,
which is n minus k, can be written as sums of prime factors of n. So let's look at this n equals 6.
So 1 is not possible to write as a sum of prime factors of n because the prime factors are 2 and 3.
Remember, we need both k and n minus k to be written that way, so 2 can be and 4 is 2 plus 2.
3 can be, n minus k is 3 which is also a prime factor of n. K equals 4
we've already checked, and n minus 4 is 2, we've already checked that one too. 5 can't be done,
even though 5 is 2 plus 3,
n minus 5 is 1, which can't be written as a sum of prime factors of n. And so this
condition of whether or not the number of test tubes and
the number of missing spots can be written as a sum of prime factors of the number of holes is
exactly when you can balance a centrifuge.
[Preview] Which is something we understand really well, right?
So this is always useful in sort of geometry or that kind of study, if you can
change something just a little bit and get back to something you understand really well. So there's a natural way to view this thing...