The Centrifuge Problem - Numberphile

so we're gonna do chemistry today just kidding I can't do any chemistry but this one is for the chemist because we're gonna talk about something called the centrifuge problem okay so the centrifuge is this thing that chemists used 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 we 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 way it's that kind of thing just to sort of idealize the problem it's hard enough as it 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 balances 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 too empty so if one of them balances it then so will the other okay so yes we can do k equals 4 and for k equals 5 though we again have no chance for the same reason as k equals 1 which is that if we leave one empty then there's no chance of balancing this thing and of course with 6 then we just fill every spot so right away if six we see that one in 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 as well I see exactly when it can be done it's when K and n have some common factor right because one in 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 all right so if I can do it for safe and a six if I 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 for 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 the centrifuge but it's not always gonna be true okay okay 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 no common factors with 12 in fact it's a prime number and it's not any of the Prime's that divide 12 and it looks kind of weird right like I can't really visualize putting seven dots in here to balance this thing but think about what I said a minute 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 three divides 12 I can just put them every four spots so there's three that are balanced and same thing with four 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 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 built it up from balanced configurations we know that it's balanced so when you say balanced just I could I could pin yes 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 eye and the way we visualize it on the plane is just using the coordinates for the first and second real number which I've written is a and B so here's my like a and B so if I draw a circle on this plane that centered 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 6th one it's 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 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 + 4 is 2 plus 2 3 can be n minus K is 3 which is also the prime factor of n K equals 4 we've already checked an N minus 4 is 2 we've already checked that 1 2 5 can't be done even though 5 is 2 plus 3 - five is one 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 which is something we understand really well right so this is always useful in sort of geometry of 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

Channel: Numberphile

Views: 586,972

Rating: 4.9286914 out of 5

Keywords: numberphile, centrifuge problem, holly krieger

Id: 7DHE8RnsCQ8

Length: 9min 18sec (558 seconds)

Published: Mon Dec 03 2018

Reddit Comments

[u/Spirko]

Background: The task is to take N symmetrically distributed slots on a circular centrifuge, and fill k of them with test tubes and have the resulting pattern be balanced. The video discusses building the pattern of filled slots by filling smaller patterns that are symmetric. These small symmetric patterns always have a prime factor of filled slots. The conclusion reached is if and only if both k and N-k must be formable by adding prime factors of N, then the k test tubes can fill slots to form a symmetric pattern.

My thoughts: Once you have 3 or more prime factors, you can build a balanced pattern that includes negative contributions from a symmetric pattern. For example, for N=60 (2*2*3*5 with an extra factor of 2 just so the dots correspond to minute marks on a clock) slots:

Add in:  10, 30, 50        (upside-down triangle)
Add in:  0, 12, 24, 36, 48 (pentagon)
Subtract:  0, 30           (opposites)

Result:  10, 12, 24, 36, 48, 50  (k=6 slots filled)

The final k=6 pattern is balanced, but it isn't built from simply filling slots that are part of a symmetric pattern. Basically, any linear combination of symmetric slot patterns is allowed, as long as the final result only has values of 0 or 1 at the locations of the N slots.

So are there any N,k that can be balanced like this but couldn't be balanced using the simple fill-or-don't logic discussed in the video?

[u/hrlemshake]

For a second i thought it was Amy Adams presenting a Numberphile video

[u/Smartch]

Is it possible to visualize it with group theory? For example with subgroups of cyclic groups or finitely generated Abelian groups.

[u/Dd_8630]

When she did 7 in 12, that blew my mind. It's one thing to go through the maths, but to see it so viscerally... it's like being shown a missing number between 23 and 24!

[u/besalim]

How does one write 0 as a sum of the prime factors of n?

[u/Deodandy]

I fucking love numberphile

[u/wzkrxy]

How would this look like if we generalize this problem for Rⁿ with n>2? I'm guessing it should be possible to generalize this, as it works for n=2 as shown in the video and clearly works for n=1, with z1+z2+..+zk=0, too.

[u/sparr]

In the case where 7/12 is being shown as 3/12 + 2/12 + 2/12, what is the guarantee that there will be a place to put that last pair?

[u/wudaliang]

Buy centrifuge Please come to https://www.zonkia.net