Let me try to give a short. No, no, not short hint for the last problem. How to show that every even permutation is possible in the key. We already know that every possible permutation is even. But now we want to prove that the reverse statement is, we can achieve everything in permutation and this is a mathematical account and that it should be translated into programming side. So, you should write the programming using this stand out situation you have mathematical proof and you need to implement it. Anyway, first, we start with some mathematics which is not related to this game, buzzing which is just the general things from group theory. So, let's tell you what is the three-cycle. So, two-cycle is transposition. So two-cycle, we have A and B and we want A to go to the place of B and B to go to the place of A. This is transposition and then you can get what is three-cycle. It's just we have A, B and C and A should go here. B should go here and C should go here. So, it's a three-cycle. So, is it even or odd that's the first question? And then it's easy to check, if it's even. We know how to check this, because we just need to present it as a sequence of transpositions. So first, you want to put A here. B here and C here. So first, you make a transposition with A and B. So after that, here you have A and here you have B. So, A is in the right place. A should be here, but B and C are in the wrong place. B should be here and C here. So, the second disposition is needed to exchange B and C. So, it's an even permutation. So, this is our first step and second step is that every even permutation can be obtained by three-cycles. So we know that if we make several three-cycles, then we have even permutation. Because each of them is a sequence of even number of dispositions. So in total, we have also even thing. But now, we want to show the reverse statement that every even permutation can be obtained in this way. It's rather easy, we should recall how we did this for two-cycles. For two-cycles, we just placed the right thing here, then the right thing here and the right thing here and each can be done with a permutation. And now if we want to place something in the right place, then we cannot do a transposition. We need to do a three-cycle. So, we need some temporary location. And so, we make this three cycle and this is what we need. The problem with that at the end, we don't have temporary locations. So if we here, everything, except the last thing is correct. Then we are no more able to do this, but then we have only two things. And so, they can be either in the order we want or in the reverse order. But if they are in the reverse order, then one more transposition is needed. And this is impossible, because both our global permutation which we want to get and our current permutation are even. So, they cannot differ by one transposition. So automatically, we get to last thing in the correct order before we had the last thing in the correct place. But now, we have two last things in the correct order. So, every even permutation can be obtained by three cycles. So, this is about general things and more computations. Now, we return to our game and there are two observations about this game. So, the first observation is that at least some three-cycles are very easy. So we have a board and there is a special three-cycle, which is very easy to obtain. So, imagine we have this red things. We have here, I think it's 11. Yeah, 11, 12 and this is 15. So this three-cycle is easy to obtain, so we can get in this place. We can get 11 here. 12 here and 15 here. No and of course, you see how you do this. You just need to make one step rotation in this direction and then 15 is going here. No, first, you move 12, then you move 11, then you move 15, then you move this one. Everything is okay. So, one three-cycle is possible. So that's a special three-cycle or if you repeat this twice, you'll get three-cycle in the other direction. It's okay in both cases. So the question is how to obtain every arbitrary cycle, if we know how to get this one special one and then we need this next step is that every three pieces can be placed into this red zone. So, I made some symbolic things. So if you take any three places, if the rest of course, they're not so many possibilities. But if they have any free places in the rest, you can and you want to put them there in the red zone. It's always possible. For each of them, you know where you want to put it in the red zone and there's possible without any restriction of other pieces. So, other pieces can go wherever they want. You just look at this time. Actually, if you played ten minutes in this game, you know that it's easy. The problems start when you are close to the end. If you put only three pieces, that's just trivial. But of course, we need some proof and this proof unfortunately requires some case analysis. So imagine we want to put this piece here, then how can we do it? First, we can put it to the left side. If we put the empty piece somewhere and then we make a rotation along the cycle, so we remove this piece until it goes. Now, it's already on the left side. But if it were somewhere, we can just put it there, then we can make a rotation along this line and put it here and then after that we make rotation in this cycle and put it there. So in this way, we can put it here. So now, this thing is in the correct place and then we need to put other two not touching this one. So you should not make any changes here, but you should make cycles like if you have [INAUDIBLE] which one. If you have for example, this one and you want to put there and you can move it first out of this, then move it here and then bring here. And so, it's not difficult. So every three pieces can be placed in the red zone, but maybe now you are confused why we do all these. Because first, we do something in the red zone and there's enough of completely different story, how to put three pieces in the red zone. But now, there is the most important part of the argument is something from grew fewer. Let me show it like this, symbolically. So, imagine we want to make some cycle. First, we make some S sequence of three-cycles and put that, six sequence not six-cycles, sorry, sequences moves in the game and these three pieces are placed in the red zone. So, these three pieces go somewhere. I don't know. Like this, like this, like this. Then what we do? We make the cycle in the red zone. So in the red zone, we make a cycle. It's not bad, so okay. So, we make a cycle here. So it goes here and goes here, and this goes here. So this is the red cycle, which as we know is easy. And now what we do, this is the most important step. What we do, we do the reverse. So we do the same movements, SNS, but in other directions. So, that usually is noted by s minus 1. So, we put things here. And now these three things go back, so this one goes here. This one goes here. This one goes here. This one goes here. So, what have we achieved in this way? If you see that these things are moved in the red zone, then cycles made there and then they are rolled back. So we achieve the cycle we want and all other pieces here, they are moved somehow. They are not untouched. They are moved in unknown place. And by then, he already don't move them. So here on the second stage, they remain in the same place. So in the third stage, they will go back exactly where they were initially. So, we get the three-cycle here and all of the other pieces are on the same place. So, we obtained everything. So, we conclude that every three-cycle is possible according to game rule. And now we know that every permutation is a combination of three-cycles and every even permutation is a combination of cycles, and every third cycle is possible. So, these two things show that every even permutation is possible. So, this is the proof. The only thing there remains to do is to implement this in terms of the program and it's a bit complicated. Because here, it's easier when [INAUDIBLE] we make hand waving and say, look, it's easy. Blah, blah, blah. But as programmers, we need to consider all the cases carefully and not miss any case. So you should be very careful on the second part and then the other things are less complicated, and final remark. There is another problem which shouldn't be mixed with this when you are asked to provide the shortest, shortest path. So you need to provide minimal sequence of moves, which gives the desired permutation. This is much more difficult problem. It's required a lot of memory and some tricks to optimize them, so it's not that easy and it's another story completely. What we did is only the existence proof, so we prove that some part exist. And therefore, there is always the shortest possible. We have no tools to find the shortest pass up to now. So sorry for if this was kind of, since it's most complicated thing. I did not, I tried to explain it fast. I didn't make slides, but it's more challenging probably to follow this. But I hope it's more or less clear.
