The parity of permutations and the Futurama theorem

[Music] one of the first videos we did for for this channel was about the Futurama theorem which is a pretty amazing thing it's about mind switching mathematics and a real fear of their peers in one of the Futurama episodes and what I was going strong when we were recording this episode and were laureate I don't know what it was 25 minutes so just happy told me you have to stop now I have to stop now and well I stopped in but the video actually became quite popular and so I thought well why not why not do a part two where we talk about all the stuff that I didn't get around to talking about last time ok so that's what I'll do today so when you think about the Futurama theorem you'll actually notice well it's a lot of fun but mathematically speaking it's actually pretty well not very interesting so outside Futurama no applications I think on the other hand that stuff that I didn't talk about that gets you into territory that's extremely important within mathematics in fact into some sort of incarnation of yin yin yang within mathematics it's called the parity of a permutation of a parity of a mess and it's something like Auden even or left-handed and right-handed for for permutations for masses for shuffles whenever you rearrange something it's there somewhere in the background and but within mathematics it's very very important and Rubik's cubes for example day they know about it and a couple of other people anyway so let me talk about this stuff so pretty quick recap of what has been happening so far so I'll stick with the Futurama setup because most people will be familiar with this so there's the professor and there's Amy and the professor's just invented this mind switching chair so you sit on the chair both characters sit on the chair you push the button and minds get switched and the way I've set it up is like this so here we've got always two diagrams one stands for the body and one stands for a mind that's the body the one with the triangle is the mind okay so they sit on the chair they push the button and Minds get switched okay now this chair comes with a little bit of a flaw it's a great invention but once to two bodies have set on a chair and switched minds if you try this again with the same two bodies it's not going to work yeah so these two guys at the moment they're stuck but you know they can sit on the chair again push the button but minds won't get switched so their idea is to just bring in a couple of their friends and then use their bodies as temporary storage and kind of swap minds around and hopefully eventually get everybody sort it out so that drew that so they get in like nine characters in total well seven so seven plus the two that were there before that's nine and it's the usual crowd plus a couple of additions for that for that episode and then they go for it all right and well they don't get anywhere really what I just get into a big huge mess and that's that's the mess there yeah that's the mess and in fact the only way out is to bring in outside help outside help comes in the form of the Harlem Globetrotters of the future is these basketball players there who also happen to be extremely good at maths and they come up with this theorem that you see there in the background and the theorem allows to sort out any mess whatsoever and you don't even have to know how it came about and you can do it so it's something very very neat and not only do they come up with the theorem they also help sorting out the mess and that's basically where where I'll pick up the story and we'll just have a look at the clip again where things get sorted out it's not clear that they actually gets order but they do and it's all correct what I want to do is I want to count the number of switches it takes to sort out this mess okay so in the clip there's always going to be two switches happening at the same time so the way I'm going to count is 2 4 6 8 and so on until we're finished okay so here we go two four switches six switches eight which is ten switches twelve switches and one more 13 switches okay so thirteen switches the theorem sorts out this mess in 13 switches okay well I mean the theorem discuss everything you know any sort of mess but what it doesn't do it doesn't try to be you know particularly efficient and actually if you have a really really close look at how this mess comes about then you'll notice that you can actually do with less switches if you just really smart about it you can actually do the whole thing with with nine switches okay nine switches can you do even better you know I mean that's something that you kind of ask in mathematics quite a bit what's the best way of doing it what's the least number of ways of accomplishing something you know it's it's a kind of a theme that runs through mathematics and just in general everybody's interested in doing things the best way possible okay so let's ask can we do any better well actually it turns out with this particular sort of chair and the set up we have here we can't do better than nine if you want to do better than nine what you actually have to do is you have to ask the professor to go away and and fix his chair so that's what he's actually going to do in a second so he's going away and he's fixing his chair he comes back with an improved chair okay and an improved chair actually it doesn't have any restrictions anymore right so he can put like a me and the professor on and push the button five hundred thousand times and his minds are going to get switched five hundred thousand times yeah all right and now we're going to just try and and do better than the nine okay let's see how far we can get and when we make a mistake we put Fry and charge okay so if we foot put fry and charge and he just gives commands use which was that guy and use which was that guy and let's just see how he goes right so he goes through and eventually he actually manages to sort out the mess it takes him well sixty five times that's not an improvement right then maybe he goes again and again and again and again and let's just note down everything he does all right okay so here we go that's what he does all right so he does like thirty five times to sorted out and twenty-one 1579 what is all stuff now actually haven't shown this to Jesus as I'm gonna ask him what do all these numbers have in common they're odd it's exactly right they're all odd so they're all odd they're all odd numbers and in fact that gets us to the sting in the young thing okay so it turns out that this mess here when you swap when you've only sorted out with just using swaps well you can do it in many many different ways but whatever you tried you're always going to take an odd number of swaps it's not possible to sort this thing out with an even number of sorts absolutely not not possible and so that makes this thing here what what mathematicians say an odd permutation or odd mess all right and well that's kind of true in general so whenever you look at some sort of rearranging of things or some sort of you know bringing things back into a certain order that's going to be in the background so for example I've got these animals sitting here if you want to arrange them so that the smallest one is here the next smallest one is here and so on you'll actually turn out that no matter what you try there's many many different ways of doing this it will always take an even number of swaps so that's an even mess or an even permutation and it becomes really important for puzzles like this for example when when you've got this sort of information it actually turns out that all the messes the shuffles of a Rubik's Cube when you really will ever have a look at it they're all they're all even permutations so for example isn't even permutation you kind of give it a couple more twists even permutation even fermentation even mess even shuffle whatever you want to call it right so this is something very very fundamental right so there's the even permutation stairs the odd permutations and again even permutation or odd mess or even mess means even mess means if you want to sort this out with swaps it's always going to take an even number of swaps odd mess always takes an odd number of swaps okay so what I want to actually show you and my colleagues in the math department have advised me against it because they think it can't be explained to a lay audience or people who are not specializing mathematics is why this is the case and also what's the least number of swaps that we need to actually sort out this particular mess or any mess okay so here we go now let's just put somebody in charge and so fry let's put somebody in charge of actually smart who's smart in Futurama but Professor definitely Leela's also pretty smart so let's put Leland's in charge let's have a look at this actually I'm going to pick on gzip again okay so if you've got this mess and you want to sort it out right I mean what's the what's what what does everybody really do and so if you want to you know if you want to put this thing here in order what do you do you probably focus on bender but and then how do you get bender sorted out so with the Emperor that's right and then yeah you pair them up in your swap run so that's what pretty much anybody would do I think and then well we would try to maybe sort out fry what do we do yeah so fry with soy burger just pair them up and you go and I actually keep count of how many swaps it takes okay ram-leela boys well there's the Leela mind what so and you just keep on going like this all right and sort it and I call this maybe the the you know the straightforward approach or something this is straightforward approach takes seven swaps take seven swaps better than nine right better than nine so the improved machine really had made a difference but now the question is can be a dual even better than this can we do even better well I mean one thing which is good is it's awesome number just like what I said what's not number okay now to get to the bottom of this I've got something really cute set up here so I'm really proud of this and it actually it's the same sort of setup that we use for for the Futurama theorem it actually works very well for this one yeah okay so here's our nine characters to be able to actually describe what's happening like really describe I need a bigger mess than what we have here okay so I'm actually going to bring in a few more characters here you know so it's for example you know it Nemo is down there Bock and I'm going to jumble them up okay so that's a mess now and now I'm going to first find the underlying structure of a mess there's always something there's always some order in a mess and I wanted to show you what that is okay lot of people watch the Futurama theorem clip they know it is everybody else here we go and so we'll focus on one of those guys yeah at the moment there's bender and there's needles mind so let's just have a look at this base Leela's body right so we will just make an arrow here then here's kiff's mind keeps bodies over there so we're making arrow there's fries mind fries Bodine see an arrow and we just keep on going like this okay and obviously you know I mean there's only a couple of places where these arrows can go so eventually we have to come back to the beginning all right and you know we actually do so after six you know it's basically six times we have to draw an arrow here we cut back to the beginning no we didn't pick up those guys so we just start again with this one here and we go here here here here here again another cycle so the mathematics is called a cycle and then where we're not finished yet so we do this one here that gives us a mini cycle and then there's actually one guy who you know there's nothing happening here but it's we're still always connecting mind to body so if you connect mind to body you have to go like this all right okay now we can sort out this thing I like the strip's graphically look and make it look a little bit nicer so here we go so what I've done now is I've just really made these cycles looking cyclical right so so that the minds are always next to the body so my next is body mind next to the body and so on right and so what we've got here is called a six cycle because it's got six guys in it that's a two cycle that's five cycle and joosep what do you think what is this that's a one cycle that's right so it's a you know it's a one cycle okay and now the key the key to really understanding what's going on here is to have a look at what happens when we swap two minds okay and there's actually two possibilities here either the two minds are in like two different cycles or they're in the same cell okay so let's just see what happens if we if we swap those two minds they're ready for the magic he's ready okay so we swap these two minds and what happens is we get a bigger cycle that's right so the two cycles merge so I call this sort of thing in outer swap okay now to swap so dis so now to swap so the two cycles merge and in terms of numbers what it means is that the number of cycles goes down by one okay so before we had four and since these two merge together when I have three one two three okay okay let's just do another example here here so let's make the swap make the swap and what do we get one big cycle that's a number of cycles has gone down by one and actually when we kind of go backwards here just going backwards you see that's already one of those other other swaps where we have two guys on inside a cycle when we swap those the cycle actually splits up into two parts okay so let's just do this cycle to split up into two another example here and let's just go for a swap in here we do that you know the cycles were splits up and so the effect here is that the number of cycles goes up by one but but the main thing here to remember is that no matter what we do the number of cycles either goes up by one or it goes down by one it's very simple ya know if they're in the same cycle like what we just did here you know it's splits up it always splits up into so nothing stays the same so as soon as you make a swap you know the cycles either split up or they get merged and the number of cycles either goes up by one or goes down by one depending on whether you make an outer switch or an inner switch okay so that's you know that's the key to everything let's just have a look okay so we start out with four cycles okay and where do we want to go we want to sort everybody out line so we want this and what is this well it's 14 characters and it's basically 14 one cycles okay so fourteen one cycles okay now we want to do this with swaps right well one swap we have to get from 4 to 14 somehow well obviously what we really want to do is we want to kind of go five six seven right we want to know don't want to go the other direction we definitely don't want to go backwards so we were going to go 5 6 7 8 9 10 and so on so it's a difference of 10 right so we should be able to get there in 10 steps now we're going to split cycles are we going to emerge cycles for this we're going to split cycles right because we're kind of really want to kind of break them down basically into these individual components all right so every single thing we do here is going to be just go inside swap swap stops or swap I just want to show you how that works with 10 switches here we go so for example we take those two mines they're swap and it breaks up this two cycle and actually it turns out that for to break break up one of those cycles into individual components you just need one less swaps 10 guys in here so for this one we just needed one that was a 2 so I thought we needed one for this one we're going to take 4 & 4 that one's going to take 5 so 5 swaps plus 4 swaps plus 1 is 10 ok so let's just do it right so let's let's break up this one here so I'll just do it right and I actually always take mines in kind of adjacent it doesn't really matter what you do it's always going to break up the whole thing but this is kind of neat when you kind of take these these mines and adjacent guys in here you always kind of isolate one out like that right and there's the counter of cycles right so tomorrow we had 13 cycles and we just do one more step like this that it gets us up to 14 all right okay and now when you kind of have a look at this it's pretty obvious that we can definitely not do better than 10 right and 10 does it so 10 is the minimum number of swaps you'll need to break up that mess okay so blatantly obvious yeah obvious one okay so now we can go back to our mess that we're really interested in the Futurama mess okay so what have we got here we've got how many cycles to and where do we want to get to how many guys are here nine right so it's two and nine so what's the minimum seven right nine minus two is seven seven that one that we got with the straightforward approach was best possible and actually it turns out that if you do the straightforward approach you're always going to be best possible you know and if you I mean if you actually understood what I've been talking about just go back to when we did the straightforward approach and let's have a look at it and you see you actually yes I'm always doing inner swaps here when I'm gonna do a little a forward approach and that's why it's got to be optimal yeah I mean that the upgrading of the machine is just a gimmick really usually there's a machine you just swapping right all right bye so that's that's that's pretty good right and it says something but the really deep thing is to see that you know this guy is an optimization and it's based on the same sort of inside you know the breaking up the cycles and kind of going up by one and going down by one now I'm just going to show you four for this particular mess but if you understand why this is an odd permutation you can do this for any permutation or any mess you'll see that it's always going to take either always an odd number of swaps or always an even number of swaps okay I'll show you how why why this is an acht permutation but it will always take an odd number of steps to get get disordered or something so let's put fry and charge again hey let's put fry and charge again so he's he doesn't know what what's going on right so he's just going to make like random switches again right so some times the number of cycles going to go up by one and sometimes going to go down by one okay cycles at the moment we've got two okay now we make our first switch like fry mixes random first switch how many cycles are we left with what are the possibilities we can either go down by one that's right so one of three right okay now he makes a second switch again we don't know whether he's going up or going down so what are possibilities well one cycle we can't go down one side that's a true but we can go up so we can go to two he came from here we can go to two or to four so we can either go to two or four that's that's the only possibilities in when three how many cycles what are the possibilities you can go back to one yep or you can go down to three yeah and a five and that's it and if you just have a look at it it's pretty obvious what's going to happen always in terms of autumn even in the first step it's got always gonna be odd alright that's even that's odd and then it continues like this right so on the fourth one it's gonna be even right then odd even odd even odd even odd even odd even so it's going to be like that no matter what fry does not you know I mean if he did actually nobody was doing he would be finished after seven but he probably doesn't finish after seven so what under numbers can you finish all right we want to see that it's always going to be odd okay and it's actually already pretty obvious a lot of you will have seen it already now but I just say okay what are we aiming for well we're aiming for nine cycles okay nine is odd right nine is odd so the only places where we have any chance of actually solving the whole thing is on the odd cycles bits right so the only places where we can actually sort out the thing are on 7 9 11 13 15 and so on that's the whole explanation right it's the whole explanation so it's an odd mess pretty good right now I actually didn't really show you where where this comes up so we're going to do another video where we actually have a really really neat application of this and to the max Museum in Futurama so I'll just show you the clip to the whet your appetite so here we go so what do people do for fun here do you enjoy your partying all night with the plenty of ale and lusty women I sure do not us we spend our leisure time in the mathematics museum so that's the mathematics museum and you probably recognize this little puzzled edits built in there so um this odd-even permutation business plays a big big big big role in kind of understanding this thing so um there going to be another video about this stuff so just in case you made it to this point I just actually tricked you in and in sitting through a whole mathematical proof so you may have not noticed it but I mean in in a maths book what we've just done looks like this alright so you know pretty cool isn't

Channel: Mathologer

Views: 99,932

Keywords: Mathologer, Mathematics, Math, Maths, puzzles, futurama, futurama theorem, parity, parity of permutation, ying and yang, mathematical proof, Rubik's Cube, 15 puzzle, 14-15 puzzle, Planet da Vinci, fry, Leela, parity in math, mind swapping

Id: w0mxdo5ur_A

Length: 22min 27sec (1347 seconds)

Published: Fri Aug 14 2015