Now, we learn how to narrow the search. Actually there are many combinations, but some clever tricks can condense, delete most of them and restrict our search to some small set. So, let's see how it's done. We're looking for 3×3 magic square. In fact, the truth is that they exist for all and starting from three, three, four, five and so on. It's not so easy to prove actually.But we are now interested only in 3×3 magic square, and what is called brute force search this mean that we should check all the possible positions of this nine numbers, and actually we know how many of them we have. If you don't know, you will know after the combinatorics course, part of this our course. But, there are nine possibilities for the first cell and for each possibility for the first cell there are eight possibility for the second one and so on. And if you multiply all those number you get 300,000. It's not much for a computer, but still still for us it's completely impossible. So, let's try to think how we can narrow the search. The first observation is we can know in advance what this... We know that the sum is in all the rows and columns are the same, but what is the sum? We can find it in a very easy way. So we know that in all the square together we have 45, and this 45 is made of three rows or of three columns. So, each column should have sum one third of 45 so it's 15. Why it's important? Let me show you before going farther. So, now, if for example, we know what is here, then the rest is the term to include. So, we can make a search only for all possibilities to fill this square. And this is much smaller actually, we have only nine, eight, seven, six. So I think it's 120 times smaller. Still it's a large number anyway, so we need more tricks and this is one of the tricks which I showed too early. And the trick is that we can predict what is in the center. So look, we have sum up four lines. This is the one line, this is the second line, third line and fourth line. First we know that if we sum all these numbers along these lines, we get four times the constant, this s, which is the sum of each line and each diagonal. So we have 4S. On the other hand, we can see that everything is counted exactly once, except for the center which is count for four lines, it's count four times. So the center, there is additional to 3×center. So 4S is the total sum which we know is 3S and 3×center. So the center is one third, so this four and three, so the difference is S. And the center is one third of the sum on every line. In our case is five. So, here is the equation and here is the solution in general, and in our case it's five. Good. So we know that we have five here. And this is again, our search space become smaller and smaller. And the next step is to think where we should place one. There is a minimal number one and it should be somewhere. And there are essentially two possibilities, either it's in the corner or it's in the middle of the side. So, this is our question, corner or middle? Now we should consider make a case analysis. So let's imagine one is in the corner, what happens then? Then we know that if this one is six, we have nine here. What do we know about other things? So there is three lines which should have key 15. This line, this line, and this line. So this is 14. So this should be 14 and this should be 14. But then let's look how we can get 14. 14 is 5+9 is this one. And there are other possibilities; this for example, you can get 6+8. You don't have number bigger than nine, so the only thing you can decrease this nine and then you get six here. And the next step is get 7+7, but this is not possible because we cannot use 7 twice. So actually there are only two ways to get 14; 5+9 and 6+8. And we have three positions when the 14 is needed. So we get a contradiction, one cannot be in the corner. This case is closed. Okay. Then, it should be in the middle. Let's put it in the middle for example, in the bottom line. Now, actually there is also symmetry, like we can turn it over this line. So we can assume for example, then on this line we should have 14, and this 14 we know that the only possibility is 8+6. But the question is whether eight here and six here or vice versa. But it's symmetric, so we consider one case. Now everything is determined. If we know we can compute all of the things. So if we have 13, we have 2 and in this lines 11, 4 and there is 12, 3 and 2+8+7. And what is very important which can be predicted, that we have correct sums everywhere, you can check this. And also, all the numbers are different. We can also check this easily by looking in the picture. So, we are lucky and indeed we get a major square 3×3. So we know that our existential statement with the magic square of size 3×3 exists is proven, we have an example it's enough.
