The easy part is now done, and we have to switch to difficult part. Okay, so we show that even is not odd, of course not the number just the even permutation cannot be at the same time out permutation. That's our claim. And let's start with a special case, it's actually rather of general situation. So there is a theorem, there are some special cases. And then, we see that the special cases in fact equivalent to the theorem. So if we know the theorem for the special case, we can easily get the theorem in the general case. So in our proof, we will repeat this thing twice, but let's start with the first one. So this special case is the case of identity permutation. So identity permutation is just everything is correct, nothing should be done. So it can be obtained by zero permutation, and zero is an even number. So if we believe in our theorem, we will know that the identity permutation can be obtained by odd number of transpositions. And actually, the general case can be reduced to this special case. So if you believe in the special case, then the general case is also through y. Imagine, let's prove imagine we believe in the special case, let's prove the general case. So we have the same permutation from A to B, but we have two ways to get it. This way, we have an even number of steps. And in this chain, we have an odd number of steps. So you see that I have drawn the arrow in the other direction. So of course, we can just if we can come from A to B. Then in the same number of set, we can come from B to A. And now probably you see what we will do. So what we will do? So we go back and forth, we go from A to B this way and we go from B to A in this way. And then, we return to A of course. So we get the identity permutation, but what about the number of steps? We made first the even number of steps, and then the odd number of steps. So even plus odd is odd. So you see that we started from A, we made even plus odd number of transpositions. And then we get A back, which is not possible if we believe in our special case statement. So we have shown that it's enough to prove the theorem in the special case. Then in the general case it's also true. So what remains is to prove a theorem for the special case. Okay, how do we do this? And then we look under more special cases, special, special cases. And this special case is transposition of neighbors. For that, we should imagine that our objects are on the line, of course for the theorem it doesn't matter. You can imagine whatever you want, a ny position will work. So we can put them on the line, and then if they are on the line there is the notion of neighbors. When we exchange the letters which have no letters in between. So these are neighbors. And this special case is just, that identity permutation cannot be obtained after an odd number of neighbor transpositions. So this is a special key. Let's see why it's two. It's very simple, actually, because we can classify all the transposition according to the pair of letters which is involved in them. So for every pair, what happens? So there we have some pair of letters, then maybe they move somehow. But at some point, they are involved in the neighbors transposition, both letters of the pair are involved. So we just change them. And then, the order is changed. What was left is now right. And then, they move somehow, maybe. And then, they come back and they go in original position. So after each transposition of this pair, the order is changed. And the transposition of other pairs, other neighbor pairs do not matter for that. So each transposition of this pair change the order, and that in other pairs the order remains the same. So for each, we should return to an original order in each pair. For that we need an even number of steps. So the total number is the sum of even numbers, so it's even. Okay, so this special, special case is proven. And now we should reduce special case to special, special case. So how can we do this? And imagine we have a transposition of known neighbors like this. So we want to exchange a and b. And there are some k letters in between. So how can we do this? First, we should move b to the left. So we exchange b here, then we exchange b is now there, we move it again and so on. So b should cross over immediate letters, and for that we need k steps. And then, b and a should change their places as right here. And then, because we want b is now in the right place, but a is not. And a should go back, so it makes k steps back. And after that, we achieved what you wanted because here, this intermediate part, I don't know, x. This intermediate part is now here. Here, we have x. And then because a just jumps over x, and so the x is just moved one position. And then it's moved back. This part, of course, change. So after 2k + 1 steps, we get the transposition of known neighbor letters. So we have 2k + 1 neighbor transpositions to make one non-neighbor transposition. But what is important that if we're interested on, if we distinguish only even number and odd numbers, then this 2k is not important. Because its just an even number of steps. So from the view point of even odd numbers, we just made a one transposition plus a even number which doesn't matter for us. So non-neighbor transposition is somehow the same as neighbor one. Just some additional even number of steps, which doesn't influence our statement. And here is written, says, it's 1 modal of 2. And we will speak about this modular arithmetic in the part about number theory. But now, you should just distinguish between even or odd number, that's enough for now. So we are done with the neighbor case to neighbor, we reduce the general case of transpositions of identity permutation to the neighbor case. And in the neighbor case, we know the proof. And we reduce the general statement about the arbitrary permutation into a statement for identity permutation. So there's a chain of inductions of two reductions, and now we are done completely. Where we are, so what do we know and what you do not know? So we started with a 15-puzzle, and we wanted to prove that one cannot exchange 14 and 15. And for that, we developed some theory about permutations, transpositions, but this theory has nothing to do with our puzzle. We even have some general classification, there are even permutations, odd permutation, but what is the connection with the puzzle? Not clear, so we need some last step to get the result of the puzzle.
