ZVEZDELINA STANKOVA: So here is the game. BRADY HARAN: Has it got a name? ZVEZDELINA: "Pebbling a Chessboard", perhaps?
Or… "Freeing the Clones". BRADY HARAN: The clones? ZVEZDELINA: The clones. BRADY HARAN: The clones. "Freeing the Clones". ZVEZDELINA: Okay, so we have pebbles, which we will call clones, because they will be able to move according to the following rule: Every clone clones itself one to the right, and one up, and disappears. Now this move can be carried anywhere on the board, as long as the position[s] to the right and up are free. And so, again, we can replace our guy by two clones, and remove him. For instance: In this situation, this guy cannot clone, because the cell to its right is not free. So in other words, we cannot put two or more clones in one cell. Okay, now the board, as you can see, is a chessboard, what we are showing here. But the actual game is played on an infinite board, which is infinite to the right and up. We have these unfortunate clones inside a prison. So, there is a prison which consists of three cells, as you can see on this picture. The [?] barbed fence is enclosing these three cells. And our clones want to escape the prison. Can you construct a sequence of moves — — and you're the boss, you decide what order, which clones to clone — — so that the three clones will escape the prison, and the prison will be… with no clones. There will be no prisoners. Okay, so let's play the game. For instance, we can do this. Perhaps that. Now we can free another clone from the prison. And then we can try the last clone, but unfortunately, there is a lot of crowding appearing. Well, the game itself is very easy. It's very tantalizing. Really, my intuitive feeling in the beginning was, "Sure, I can free the clones. What's stopping me?" But after lots and lots of trials, one might start thinking the other way around — — perhaps it is impossible. Well, before you move on with the video, you should probably stop it, and play for five, ten minutes, and see what the outcome is. Now, there are two outcomes: If you think it is possible, one particular way of freeing the clones, one particular game, is enough. It's sufficient. I don't want to see every possible way of freeing the clones. However… If you think it is impossible, Well, that's a question that mathematicians deal with on a daily basis. There are infinitely many games that you can try. Can you feed this into a computer? Well, computers don't really like infinite games. The calculation has to stop at some point. So computers perhaps are not an option. We need a human mind to resolve this puzzle. It has been solved by a human mind, and when Maxim Kontsevich proposed the problem, he had a particular solution in mind, which to this day is, I believe, the most elegant one. It is NOT possible, actually, to free the prison, but it is possible to prove that it is impossible. We will assign, to every cell of our board, a number. We'll just basically write the number there. So a move is made like that, everywhere. So what we need is to assign numbers in these three cells. So we have an old cell, and two new cells. So, in principle you can use three numbers for this, but because the game is symmetric along the diagonal, you might try only two numbers to make the solution easier, and more elegant. So something like this. The old number is "a", the two new numbers are "b". Alright, so what we want is the old number "a" to be equal to the sum of the two new numbers "b". So a must be equal to 2b, making the old sum equal to the new sum. So, what number can we put in the bottom left cell? In the first cell? Let's think of the very first number that you learned in school. BRADY HARAN: One. ZVEZDELINA: One. Okay, let's see. Is that gonna work? Let's try 1. But that forces us to put in the two adjacent cells up and to the right, one half. And each of those one halves forces a quarter. So, suppose this chip has a certain weight, which it does. The way you can think of it is: Cut it in half, and then put it on the two new squares. Now if I take this guy, whose weight is one half, I can replace it by two chips whose weights are one quarter. So again, the total weight stays the same. In fact, in the very beginning, what is our initial weight? So we have… One, plus a half, plus a half. This is what you have in the prison, which is 2. Alright, so let's make a move. Let's replace this bottom guy by two new clones. So now what do we have? We have one, plus a half, plus a fourth, plus a fourth. But hey! That also equals 2! So indeed, we've got an invariant. And [?] saying, suppose you can free the prison. So there is no one in the prison. And we have added, perhaps, along the way, lots of clones. Now where are the clones? The clones are outside of the prison, which we can call… Greenland! So they are out, in the free land, in Greenland. So their weights have to add up to 2! Because this is invariant. But the question is, do we have enough weight in Greenland, or enough gasoline in Greenland, to add up to 2? Mathematicians may find that question a bit too hard to answer at first, because this Greenland is irregular, it has this area that we have to subtract — — the prison area. So mathematicians like to simplify the problem. Why not, instead of Greenland, let us first try to find the sum of the whole table. Forget about the prison. But that's still a very hard question, because you have two dimensions to move. One to the right, and one up. Okay, so mathematicians think-think-think, and say, "Let's do a simpler problem!" A related, but simpler problem. How about we test our skills on finding just the sum of the first row? For if we are not able to do this, probably we won't be able to add up the whole table! We start adding up the numbers in the first row, and this is a very interesting, perhaps familiar (to some people) sum. One, plus a half, plus a fourth, plus one eighth, and so on and so forth. If you have taken a calculus course, you will immediately recognize that this is something called a geometric series, with first term 1, and ratio one half. Which simply means, to get the next term, you have to multiply the previous one by a half. And this keeps on going forever. When I have shown this problem to… …kids in middle school, the reaction has always been, "This adds up to something slightly less than 2." So you are a little bit short of 2; because they experimented, they added up a lot of those numbers, and said "It's slightly less than 2." BRADY HARAN: It's never gonna quite get there. ZVEZDELINA: Never quite gonna get there. I say, "Alright. So let's see what this number is!" So if this sum of the first row is sum "S", "S" is equal to one, plus a half, plus a fourth, plus one eighth, and so on and so forth. What we can do, is multiply everything by two. So on the left, I get two [times] our sum, and on the right, every term will be multiplied by two. So you will get two, plus one, plus a half, plus a fourth, plus one eighth, and so on. But now we recognize that we know a big chunk of the right-hand side. From 1 on, this is our sum "S". So what we have obtained is what mathematicians love working with: An equation. 2S on the left, 2 plus "S" on the right. Can we solve it? Certainly. We will subtract S from both sides, and we will end up on the left with S, and on the right with 2. Oops. Did we reach 2? Indeed we did. So if this row adds up to anything, there is no choice; it has got to be 2. [So] more generally, a geometric series is a sum of the form: a, plus ar, plus ar squared, ar cubed, and so on. Where we have a first term "a", and the ratio "r". In other words, every next term is gotten by the previous when you multiply by "r", just like in our first row. And so there is a nifty formula in mathematics. If this ratio is "small" — — how small? Between negative 1 and 1 — — this sum, this geometric series, actually adds up to something very simple: The first term, divided by 1 minus the ratio. And this formula works for any ratio, as long as it is between negative 1 and 1. And so we can double-check our previous result here. for the first row. In our situation, the first term was 1, and the ratio was one half. And what do we get, according to the formula? 1 over 1 minus a half; 1 over one half, which is our 2. Alright, so we are going to add up. The first row, as we saw, adds up to 2. Now how about the second row? The second row is almost like the first one, except every term is half as large; it's half of the previous one. So in other words, the sum should be half of our 2, which is 1. And now we see a repetition of this idea on the other rows: The third row should add up to one half; to one fourth; and so on and so forth. Because now we can add up the whole table, and we again end up with another geometric series, except that this time, the first term is 2; the ratio is still a half. Using similar arguments as before, we've gotten the total sum, is 4. Alright, so back to Greenland. We really wanted to check on Greenland. It is the total sum, 4, minus the prison sum which is 2; we end up with 2. So, it looks like we do have enough gasoline in Greenland. It looks like there is no contradiction, because we can fill in all of Greenland with clones, and get our new sum to 2. Which would mean that we can free the prison. Can we really fill ALL of Greenland with clones? Because, think about it: If you miss even one of those clones, your total sum in Greenland is going to be less than 2. But 2 is our invariant. We need to have 2. So we need to fill in every single cell in Greenland with a clone. Remember? We said we will free the clones. That's how we started. Alright. So at some moment, you say, "That's it! I freed the clones!" The game ends. But how many moves did you make up to that point? Infinitely, or finitely many? Basically, when you say the game ends, this is a finite game. So every time you make a move, the number of clones increases by one. If you make 10 billion moves, the number of clones will still be finite. So can you really fill all of Greenland with infinitely many clones after stopping the game at some point? No. Because infinity is not equal to a finite number. So that is a finite game, and therefore it's impossible to free the clones. So, when mathematicians solve a problem, they don't really stop. They try to generalize it. They try to create new games, new problems, and see if they're solvable or not.
