Now we want to actually to generalize the question. Is usually in mathematics is you cannot solve a simple question, not a simplest formulated question. You try to find a more general one and then you think about this more general one and then you come back with new knowledge. And then you solve the original one, this is the scheme. So we will try it for our puzzle. So first observation is another view of the game. So you can think that this cell which is empty cell is filled by the other, by the neighbor. But lets look in the other way. Empty cell is now active so empty cell moves in some way and when it moves, it exchanged the place with a neighbor. So every move is now an exchange of an empty cell and the cell which moved. So you may imagine that empty cell stays zero, so you have not from one to 1 to 15, but from 0 to 15, and every step you exchange two pieces. Okay what the matter? Why it's better? And it's better because we can now consider a more general question. Instead of forget about pieces, about this board, we have just n object in n positions and places. And we want to permute them. Permutation is you want to move one thing in the place of another and so you want to somehow do a new order to them. And what you are allowed to do is pair exchange and in mathematics called transpositions, so what you are not allowed to take all the objects away and then put it back in different modelling. What you are allowed to do is to exchange two of them and this is called transposition. For example, if you want that for four letters STOP. And if they want to get from STOP, you want to come to SPOT. And of course, one transposition is enough. You just exchange T and P, and that's all. But if you have a more complicated thing, you want to get POST, then more transpositions are needed. So we will see later but you should try it yourself and count how many of them is needed. And if you are afraid of permutations, this is a video which should convince you that it's a very simple thing, even a cat can deal with permutations quite efficiently. Okay, just kidding, but it's really nice video, you should try it independently of the permutations. And now our main thing is the classification of permutations. So they can be even or odd. This is two classes, and let me explain what does it mean. So first let's see some examples, So if you want to mix STOP to SPOT then you should make one permutation is enough. But of course you can make also three permutations just after this one useful, you can put twice to do that some permutation. Or just repeat this, the same permutation three times or so on. So you can make 3 or 5 or 7 or whatever you want. It's not so clear whether you can get any other number. But at least these are possible. And if you want to get POST, it's not possible to do in one permutation, because all the letters are in the wrong place. So you need to move all of them. So if you try, you can see that 3 is enough and then you can make 5 or 7 and so on. But again, two is not enough and four is not clear how to use four permutations together. Try it and you will see that there are some reason, by some reason, it does happen. But if you say not POST by POTS, then, 2 permutation are enough and you can also use 4, 6 and so on. So let's see how to make two. So STOP. What you do? First, you put, yeah, very easy. You exchange S and P and then you exchange T and O. Yeah? Yeah, so you can make two permutations and then you can make redundant ones. So a general observation is you can make n, then you can make n + 2 because twice permutation is nothing. Okay, and conjecture, which will be if you are is that permutation of two types some of them require like here. Oops, sorry. Require like here, they require an odd number of permutation, and this is an odd permutation. But this permutation, so its odd, odd, and this permutation is even. You need always even number of this positions. You need even number of this positions here, and odd number of transpositions here. So this is the conjecture, and before proving let me try to cheat. Let me show you counterexample, and you will probably see where I am cheating. So look, here we want to make from TOTEM we want to make MOTET. Why not? And here we do this with one permutation, we exchange this T and M. And here we do the same thing with two permutation. We exchange this T and M and now we exchange this T and M. So we achieve the same MOTET with one permutation, and also with two permutations. So what do we have? An even permutation. Even this is one transposition two transposition. So the question is whether we have one even permutation or odd permutation. How it's possible? Our classification system that's not possible. So what is the problem here? So let me tell you the answer. And the answer is that there are actually two letters T. So if we see that this is T1 and T2, then here we have T1 and T2 here, and here if we look here then this is T1, this is T2 and then a few is T1 and this is T2. So we get the same MOTET but we have actually these two MOTETs are different by one transposition. Exchanging this and this. So everything now is clear. It's not real counterexample. So now the theorem. Let us say it seriously. First each permutation can be obtained by a sequence of transposition. In mathematician rule it would say it's a product of transposition, just can be obtained by sequence of transposition. And the number of transpositions in the sequence is somehow predetermined by partial. So some permutations can be obtained only by even number, while other can be obtained only by odd number. So there are two cases and they do not mix. This is the theorem. Now let's prove the easy part. The easy part is that every permutation can be obtained by transposition. So you can always get whatever you want with transpositions. And this is very easy and probably you have seen in our example what we should do. We should just place the letters, whatever you want to place. We should place them one by one. So first, we see what should be in this place and find the letter and make a transposition. Then here we have a correct thing. Then we look on the next place, find whatever should be there and make a next transposition and so on. So let's see how it works. Imagine... We already have seen it but let me repeat it slowly. So Imagine we want to convert STOP to POST. So at the first place, we need this P so what do we do? We take STOP and exchange P and the letter of which is currently the first place, so we PTOS. And now P is in the collect position, but TOS is not good. So here, we need to have O. So what we do? We exchange O and T which is currently there. So this should be exchange we have POTS, and now the rest T is not, it should be S here and here is T. So we should replace them and get in one step, we get the final answer. And actually you can think if we have n letters, we have n, not that n but n- 1 step. n- 1 because the last letter is automatically the right place if the previous are in the right places, okay?
