Okay, so today we're gonna talk about this fantastic little puzzle It's called the 15 puzzle and you can see it's a tray with 15 little squares each numbered 1 through 15 and one blank So we can move the squares around Let's say we want to get these in order So I'm gonna move these around I've got 1 2 3 already and then the third row should have 9 10 11 12 and then 13 14 15 Oh you're good at that! So there we go. We can only make moves where we switch one tile with the empty spot So I can't switch this one and that one for example because there's no blank to move them around in What we want to talk about with this puzzle is some of the mathematics behind it So we went out yesterday and found some examples of these puzzles that you could buy in the stores around here and we found something very interesting on the back of the package. It shows you some of the patterns that you might try and arrange the tiles in So the one that we just did was 1 through 15 Here this one has 1 2 3 4 in vertical lines rather than horizontal You might want to do evens and odds, the various possibilities you could come up with Including a natural one You might try and do which instead of going from 1 to 15 goes from 15 down to 1 so in reverse order But this is very curious: try as you might, you will never be able to do this arrangement So, how they ended up on the back of this package is a real mystery, but that's the mystery that we want to Explain today. So that's like they're giving people this impossible task? It seems like it I don't know what they were thinking. Did you play this game when you were a boy? I had several versions of it including the standard ones like this. I also had some versions that Instead of having numbers had pictures. I had one that had a map of the world and the object was to you know Recreate the map of the world. But yes, I certainly wasted more time than I should have on these puzzles It was invented in around the 1870s . A famous American puzzle maker named Sam Lloyd claimed that he had invented it but apparently that's not case But what he did do in around the early 1870s was he issued a challenge to the public and he offered $1,000 to anybody who could accomplish this so his challenge was to take the 15 puzzle in the arrangement where the numbers are in order 1 through 15 and Rearrange it so that 14 and 15 are switched He offered $1,000 for this but the sneaky thing about this is that this is also an impossible arrangement But this caused an absolute national frenzy Everybody was involved in trying to do this. A serious mathematics research journal called the American Journal of Mathematics published a paper called 'Notes on the 15 Puzzle' and what the editor said was "The 15 puzzle for the last few weeks has been prominently before the American public and may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community" and then he goes on to say that This wouldn't have been enough to persuade them to publish a paper on this but they felt that it was a chance to educate the public on some important mathematical concepts. So they were jumping on the bandwagon? Actually, this paper is two short notes: one proving that some of the configurations are impossible and the other Saying exactly which ones were possible. Okay. So the first thing we have to do is we have to convert this puzzle into some mathematical language so that we can use the tools of mathematics to Figure out what's going on. So let's first of all just make all of these things I'm sort of put them all on the same footing so let's think of the blank square as the number 16 So now we've got the numbers 1 through 16 in some order So we're going to focus on those lists of numbers so each arrangement of the tiles we're going to think of as some arrangement of the numbers from 1 to 16. Every time we have a pattern in our puzzle I'm going to Write down the list of numbers 1 through 16 in the order that they appear in the tray So for example this arrangement would give me the list five one three Remember the blank is 16 then 9 2 6 4 13 10 7 8 14 15 12 11 so it's the same set of numbers 1 through 16 just written in a different order. In mathematics that sort of thing is called a permutation. In our case it's of the numbers from 1 all the way up to 16. At this point I would have assumed every permutation is possible If you juggle them around enough times, you can list the numbers in any order Right, that would be a reasonable assumption and if that was possible anything on the back of this package would have been fair game so what we're going to have to show is that among all the permutations there are some which have one property which is good for us and one which have a different property which is bad for us and we're going to use this Property that we will identify as a way to distinguish the possible from the impossible So let's think about what the sliding move that we can do is doing to the permutation So when we slide a piece we're swapping The blank Square from where it is to where the piece we slid into it came from. 16 So 16 and 4 have switched places if I make that move. If I made that move The blank and 3 have switched so 16 and 3 have switched. So the moves we're allowed correspond to switching one number with just one other. In our case in the moves from here We can always switch 16 with something else let's just say X and I'm gonna write it like that. When I write a pair this means switch 16 with X. If I do that I obviously get a new permutation. So we've now Translated our puzzle into the mathematical problem starting from one configuration Get to another configuration By doing switches like this. These are called transpositions. So now that we've translated it into mathematics we get to use everything that mathematicians have learned about permutations and transpositions and there are a couple of crucial facts that we need to use So the first fact: we can convert the permutation that we start with - everything in order - into any other permutation of the same numbers using only transpositions. So you're including the impossible ones at this point - at this point those impossible configurations are within our reach True, if we're free from the constraints of the puzzle and Only dealing with the permutations then we can convert any one into any other of these. Alright, simple example with the permutations just of 1 2 3 and let's suppose We want to end up with 3 1 2 so How can we convert 1 2 3 into 3 1 2? We can first get 3 into the place that we wanted to go by Switching 3 & 1 so we make the transposition (1,3) that will turn this into 3 2 1 we haven't done anything to 2 but we've switched 1 & 3 and now I Get to the 1 into place. So now I switch the 1 and the 2 and there we are from there to there by 2 permutations. If you have a longer set of numbers then you might need more but That's the idea that you can get from any one to any other just by switching two at a time so fact 2 addresses the fact that there's more than one way to get from one to another - we can always do it by transpositions but for example in the case of these two permutations I could have done something different. Okay now let me show you a longer one again going from 1 2 3 to 3 1 2 first switch the 1 and now let me move 3 over by switching it first with 1 and then With 2 and now I still have to get 1 and 2 into the right place. So that will take one more switch Switching 1 and 2 that will put this into the right place So now I've got a chain going from 1 2 3 to 3 1 2 That involves one two three four steps Whereas in our original example, we have only two steps Can you show me a three-step example? I cannot because of fact 2. And fact 2 says that even though there are many ways to get from one permutation to another They don't have to involve the same number of steps but if one path Involves an even number of steps then all paths have to have an even number of steps. So the number is not fixed, but the parity - whether it's even or odd - is fixed So it could have been odd? Like, with some numbers it will be odd as well? Right, between some permutations so for example if this was the way we wanted to end up if we wanted to go from 1 2 3 to 3 2 1 Then I would have only needed one step Or three steps or five steps. So the fact number two: the number of Steps required is not fixed But the parity of that number - whether it's even or odd - is fixed. I'm taking your word for that That's like a proven thing Right, we're taking these as facts that- And not just because we want them to be - these are proven facts. Right, right. These are you might even call them theorems about permutations. So like in the example, we did we had one path that had two steps and one that had four. The number was different but both were even. And I could try until the end of the universe to to do three and I wouldn't find it. You wouldn't find it. Yeah Or 5 or 7 or 9 even if I was like duplicating my steps and things. Right, you could have a Sequence where you just went round and round in a loop for a while and then cut out of the loop and made progress that would add a lot of unnecessary steps, but it wouldn't change the parity of the number of steps So what this means is that Starting from the numbers in order every other Permutation is reached either by an even number of steps or an odd number of steps another way of saying that is we can attach to each permutation a thing that we might call an invariant of the Permutation that is the parity of the number of steps needed to get to it from the starting configuration. Now that we know that all Permutations are either even or odd We will see that the impossible ones Have the wrong parity. When we go back to our puzzle and we want to know which Configurations are possible and which are impossible We're going to use this relation to even and odd permutations and we'll see that if the arrangement corresponds to a permutation with the wrong parity, then we'll never be able to get to it. One extra consideration we have to bring in is we have to look at where the blank space the number 16 in our permutations starts and ends. So like for example if we wanted to start with the pieces all in Horizontal row let's suppose we wanted to get to the vertical arrangement So here we see that in this vertical arrangement We're going to end up with the blank square again at the bottom there So if we start and end with the number 16 - or in puzzle language, the blank square - starting in the bottom-right corner and ending in the same place, what's going to happen between start and finish is that the blank square is going to move all around the tray as we make our switching. So here I'll start it We want to get to the ending configuration. So we have to move the blank square all around So that I can rearrange the numbers keep your eye on the blank square You can see it's moving all over the board and we will just keep moving the blank square around Until the pieces do what we want etc So let's count how many times we have to move the blank. That will be the number of transpositions we have to do. So you might think this is an impossible thing I mean there's going to be maybe dozens maybe hundreds of moves that we have to make but remember all that we care about is the parity of the number of moves and if we think about What's going to happen to this blank square if it's going to start here and end up at the same place? So let's suppose that when we're doing this we make a certain number of moves to the left a certain number of moves to the right a certain number of moves up and a certain number of moves down. If we're going to end up at the same place We have to make as many left as right because if every time we move left We'll have to compensate if we're going to end up at the back at the same place and the same With up and down. The number of ups will have to equal the number of downs so the total number of Moves is the total of the lefts and the rights and the ups and the downs But the lefts and the rights are the same So I can write that as twice the number of lefts and there are as many downs as ups So that's twice the number of ups so you can see that whatever The number is, it's twice something. It's even. It's even. So to end up with the blank or the 16 in the bottom right corner definitely even number of moves. Definitely an even number of moves. So that means if we start from this configuration and we end up with the blank square in the 16 We can only rearrange this to correspond to an even permutation All right, so to prove that this one is impossible all we have to do now is check whether the permutation corresponding to this arrangement is even or odd. If it turns out to be odd then we know we cannot reach it by these moves. Okay, how do we do that though? That looks like such a complicated thing to show. Alright so let's write out where we want to start from and where we want to get to. So we want to start from this configuration and we want to end in the permutation Corresponding to that arrangement so that starts with 15 So 16 is going to end up in the same place, but all the other numbers have been rearranged. Let's construct a sequence of transpositions that is going to take this permutation To that permutation and this is actually not too hard. So we have to switch 15 and 1 14 and 2 13 and 3, 4 and 12 5 and 11, 6 and 10, and 7 and 9 and if you make all those switches Then you'll get 15 first 14 13 12. You'll get it in this order Of course, you can't make that switch in the puzzle game quite so easily, can you? You can't do it in the puzzle game, but- Without cheating and taking the tiles. Right, but we know that the sequence that you would have to use in the puzzle game would have a different number of steps But the parity would be the same So we only have to worry about parity So if I can show that with this sequence the parity is wrong Then whatever sequence we could do there would also be wrong These are the switches that will get us from there to there and well how many of them are there? There's 1 2 3 4 5 6 7 so odd That's enough to tell you that it's impossible? That's it. So that means we cannot get from the starting configuration in order to the ending configuration in reverse order with the blank square in the same place. Let's think about Sam Lloyd's original nasty challenge, which was to take the original configuration and end up with a configuration where everything is the same except the last two are switched. So if we analyze this using our math superpowers that we've just acquired we have to compare our starting configuration Compare this to the configuration where everything is the same Except I've switched these last two tile numbers and 16 stays the same. How many transpositions do we need to get from the starting one to the ending one? Well all we need to do is switch 14 and 15 So it's the transposition (14,15). That's all we need. There's one of them - odd - so that's odd, but we know from this little argument that we made if we start with the blank at the lower right and we end with the blank in the same place 16 at the end then the number of steps that we have to have performed to get from start to finish has to be even So there's no way to start there end there and do an odd number of steps. So no one won the thousand bucks. No, so Sam Lloyd kept his thousand bucks. So these other ones that these package says are possible or impossible We've got to- we have to check all of them. We don't know which ones of those are possible or not. Right, let's see if we think it's possible to end up with the arrangement where the numbers go around the board in a spiral and now we end up with the blank over there. Let's see if this should be possible. So we're starting from the standard starting configuration So the blank starts in the bottom right. And we want to know, can we end up like this? What's the parity of the number of steps that it would take to get the blank from starting to its ending position? Well, it started in the bottom right. To get to where it is at the end of this configuration, we have to move one two to the left and one up So the number of steps has to have the same parity as three So the fancy math way of writing that is to say that the number of steps has to be 1 mod 2 in other words odd Yeah, odd. OK. That's a very fancy way of saying odd! Alright, alright. Let's write odd as well, write odd under it. Sorry unnecessarily Rather than 1 mod 2. Yeah, yeah. OK. So it's odd. Whether this is possible or not then depends on whether the configuration corresponding to this which is 1 2 3 4 12 13 14 5 11 remember blank is 16 15 6 10 9 8 7. Is that odd? So this one - it's not as easy to draw a map in the same way there But we can certainly figure out a path from the starting configuration To there, how are we going to do it? So we don't have to do anything about the first four. 12 13 14 in the starting configuration are over there They all have to be moved to come after 1 2 3 4 so we can do that Let's see 12 would have to be switched with 11 then 10 then 9 then 8 then 7 then 6 then 5 so that's 1 2 3 4 5 6 7 hops that would put the 12 in front of the 5 Then the 13 can come behind it another 7 hops and the 14 behind that another 7 We can get this much correct by Doing we had to do seven hops for the 12, seven for the 13 and seven for the 14 So that's going to take 3 times 7 Odd - there's odd hops. Odd number so far Okay now 5 is in the right place as well. So we're good up to there. We have to get 11 into the correct place Behind the five. So that's going to take five hops. Now we're good up to 11. Now we need the 16 that's gonna be one, two, three, four, five, another six hops, now we're good up to there. 15 into its correct position, that's gonna take one two Three four five hops nine ten. That was another one. Now we've got 15. 6 happens to be in its right position So now we've got to just switch the last few we've got to get 7 8 9 10 into the order 10 9 8 7 Here we can - actually we can short-circuit things We switch those two and those two - that will do the job. So that's another two that's odd Don't even need to know the actual number. All we need to know is, is it even or odd. Here we have another 10 steps That's even so an even number plus an odd number is odd. Good news because look up here. Good news. Right. Because that's what we wanted. Good news. That's gettable then. So let's do it You can edit this Mathematics wins, okay I'm gonna make your prediction:the number of people on the YouTube video that write comments saying "Oh I just take the tiles out or I cheat" and things like that is going to be odd Odd but not peculiar! Odd, and a lot of them Elements here, which these are not quite tetris because tetris is four squares, these have five. So these are five squares So these are all the possible ways you can put five squares together. If you were to stop right now This is area 20. So if you were to stop right now your score would be 20 That's your biggest, minus your smallest 4, your score would be 16
really good video too
UIUC - The 2nd spiritual home of Numberphile
Does Brady have some sort of Connection to Bradlow or the university?
HOld up, where was this filmed? Don't tell me Brady was on campus and I missed it
This held my attention much better than math225. I guess when you don't need to learn something it somehow becomes more interesting
His lecture are better sleeping pills
Here’s the Four Color Map Theorem video which was the first proof made with the help of a computer and it was from UIUC!
Also if you guys didn't know, Holly Krieger went to UIUC for her undergrad math degree! And was born in Champaign.
had abstract linear algebra with him this morning and then saw this was published after. he really is a nice and chill guy