[MUSIC] Consider the following problem. There is a sequence of 10 cells. The leftmost contains number 1, the rightmost contains number 30. And the question is, can you place numbers in all other cells in such a way that consecutive numbers differ by at most 3? So, we will show that this is impossible. And to do this, we assume that it is possible, and we will show yet a contradiction. So, let's assume that we can do it and let's see what happens. And let's see what is the largest possible number we can place in the second cell. And it should differ from 1 by, at most, 3. So the largest possible is 4. Okay, now let's see what is the largest possible number we can place in the first cell. It should differ from 4 by at most 3, so the largest possible, again, is 7. Okay, in the next cell, we can place at most the largest possible number is the number that differs from 7 by at most 3, so it's 10. And so on and so forth, so let's see what happens. So in the ninth cell, we will place in this way, we will show that the largest possible number we can place there is 25. And note that this is too far from 30. So even if we put the largest possible numbers in the cells of this sequence, still in the ninth cell, we have the number which is too far from 30. So this is a contradiction. So we assumed that you can do it and we got a contradiction, so we have shown that this is impossible. And the reason for this was that numbers in the cells grow too slowly. And observe that these problem is an important example for us. This reason is a very common trick for estimating the running time of some algorithm. We find some number in the algorithm and show that it grows too slowly and it should be large in the end. And that's how we can show that some algorithm should work for a long time. Okay, now consider a following problem. We have a chessboard, and we would like to place numbers and all cells of a chessboard, numbers from 1 to 64. And we would like to do in such a way that neighbor in cells that is sharing the side differ by at most 4. Okay, can we do it or not? We will show that this is impossible. And for this, we will assume that it is possible and we will again arrive at a contradiction. So let's assume that we have done this, so let's assume that we have a table filled of numbers from 1 to 64. And we will like to arrive to a contradiction. So the first problem in here is to understand what we should look at. And a good idea is to look at the largest and the smallest in this table, numbers 1 and 64. So, we are somewhere in this table, suppose we are here. Okay, how many steps does it take us to get from 1 to 64? Okay, it is not hard to see that, in this case, we need 7 steps. We need 3 steps right, and we can make 3 steps right and 4 steps up to get from 1 to 64. Okay, note also that 7 steps are necessary, because we need to go to the right at least 3 times to get to the sixth column. And we need to go up, also. We need to get up at least 4 times to get to the sixth row from the cell containing 1. So we need at least 6 steps to get from 1 to 64. And it already looks suspicious, so in the cells indicated now by green color, in the neighboring cells, they differ by at most 4. And in the beginning, we have 1, in the end we have 64. We can do calculations, but it is also visible to the naked eye that it is impossible to do that. The numbers grow too slowly. Okay, so but maybe we have placed numbers 1 and 64 in the wrong way. Maybe they should be placed in some other way, such that it takes more steps to get from 1 to 64. And it is not hard to see that the best way to place 1 and 64 is to place them in the opposite corner. Then, it takes us 14 steps to get from 1 to 64. 7 steps right and 7 steps up. Now we have 14 steps to get from 1 to 64. And in 1 step, the number can grow by at most 4. So in 14 steps, it can grow by at most 4 by 14, which is 56, which is not enough. And if, in the beginning, we have 1, you can grow by at most 56. And in the end, you have 64, this is impossible to achieve. So let's place numbers in this tables and see by eye that in the end we have 53, which is too far from 64. So we have shown that this is impossible. And again, we have applied the same idea as in the previous problem. [MUSIC]