In the next problem we will see that invariance can help us not only to show termination, but to show also how long does it take for a process to terminate? Consider the following problem. King Arthur has a shelf of his works consisting of ten volumes, numbered from one to ten. And over the years, the volumes in the shelf got disordered and Arthur hires Merlin to sort the collection. Okay. But volumes are variable, so he doesn't want more than two volumes to leave the shelf at once. And on the other hand volumes are very heavy, these are large books. So it is possible to switch two volumes on the shelf in one day. Only two volumes, not more than that. And Merlin doesn't know what is the current configuration of volumes in the shelf, so how many days Merlin can guarantee to sort all of these volumes? Okay, It turns out that it is always possible to do it in nine days. If you can try to sort arbitrarily in order of an arbitrary permutation of volumes, then it's always possible to do it in nine days and you can just enact the following. On the first day, we can find the first volume and place it to its right place. So we find the first volume and we switch it to the first position. On the second day, we can do the same to the second volume. We find the second volume and we place it to the second position. Okay, let's do it. On the third day we can find the third volume and place it to the third position, and so on and so forth. After nine days we will place the first nine volumes on their places. If by any chance some volume at some day already stays its own place, then we just saved a day and that's even better. But in the worst case, in nine days we will place the first nine volumes on their positions, what is on the last position? Okay, there is only one volume left it should be there so the tenth volume is also on its own position. So, nine days is enough. Okay, now what is the minimal of number of days? Is nine minimal, is it optimal, and another question, what is the hard permutation of books? What is the permutational books that is hard to permute back in the right order? Okay, it might seem that in the beginning that the hard permutation is then that all books are positioned in the opposite order. Let's look at this permutation here. It is so all books, the order is just reversed. Okay, it turns out that this is not actually hard permutation because let's do the [INAUDIBLE]. In the first day, we can pick the first and the last book and switch them and then this way, we place both volume one and volume ten in the right positions. On the second day, you'll do the same with the second and the ninth volume, and we'll see that we placed both of them in the right positions. You can do the volume three and volume eight in the next day and so on. And just five days is enough in this configuration. So it is not really a hard permutation of volumes. Okay, so what is the right number of days finally? So we'll assume that it's possible to do it in nine days or if we have tried to consider hard permutation we obtain five days. We could do it in five days, so what is the right number? And more importantly, how we're going to show this is the right number? Okay, then you need to find some invariant. Invariant in a more wide sense. Invariant is a number that change but it changes according to some rules. And the rules are the following. The number, this invariant doesn't want it to change too fast during this process. It shouldn't change by the large invariant in one day. And on the other hand, it should change substantially while we are ordering the books. So from the beginning to the end, it should change substantially. And then one day, it should not change too fast. And if it substantially show we need a lot of days to order the books. Recall the following problem. It is very similar to the problem we had in the first course. So let's recall the following problem. There is a sequence of ten cells, and the leftmost contains number 1 and the rightmost contains number 30. And the question was, the question problem considered was is it possible to fill other cells with numbers in such a way that the consecutive numbers differ by at most three? And we showed that this is impossible, because numbers do not grow fast enough to reach 30 from 1 in just 10 cells, and this is the same idea so we're just using the same idea we used in this puzzle before. Okay, now we can name our invariant. There are several choices of it, but we will just pick one and discuss it. The invariant would be the number the invariant we're interested in is the number of books that stay to the right of their intended position, they stand to the right of the place where they should stay. Okay, and let's check the properties. This number is small in the end, it should be zero if all books are staying in the right position, then no book are staying to the right of the correct position. Okay, next. This number decreases slowly. It can decrease only one by one in one day, why? In one day, we change positions of two books, so this number might decrease by at most two. But note that we changed position of one book. We moved one book to the left and one book to the right. And if we consider a book that we moved to the right, it cannot lose this property we are considering a missing invariant. If it was to the right of intended position. If we move it further to the right, it will still be to the right of intended position. So invariant in this number of books we are considering in one day, we can use only one book, the one we moved to the left. So this number decreases by at most one each day. Okay, so what is left? We need to show that this number is large in the beginning. And now, we need to choose the permutation of books, the ordinal of books, such that this number is large in the beginning. So how we can do it, and can we do it at all? And yes, it is possible to do it, this number can be made large in the beginning, just consider the following permutation. The tenth volume is on the first position and all other volumes are just shifted one position to the right, and that's exactly what we need. Volumes from one to nine are to the right of their initial position. So in the beginning of this number is nine, we can reduce it by at most one in each day, and we should reach zero in the end. So we need at least nine days to do that. [MUSIC]
