[SOUND] Let us consider now a more advanced illustration of the previous program. Again we are given a table of four by four. Again, there are plus and minus signs on the table, but now all four corners have minus signs, and all other cells have plus signs. Again, now we switched this position to all signs by switching signs in rows and columns several times repeatedly. Okay, let's consider this problem. We can try to do it, and if we try to do it, we will see that this problem looks way more tricky. It still doesn't work somehow, if we try we will not succeed. On the other hand, the previous argument doesn't work. In the previous argument we use the number of minuses initially odd, and then if we want it to be even, and it is in variance, so we can do it. But here the number of minuses is also even in the beginning, so we say it doesn't work. So it doesn't forbid disrupting or plus positions, so what can you do instead? If you know already about residues modulo 4, we will learn them later in the later courses. You can try to use them, but they also doesn't help. Still, if you try to use this variant it doesn't help. Data satisfied in the end and data satisfied in the beginning. So still yet, there is a very simple solution to this problem. And if you don't know it, I suggest you to think bit more before we can server. This way you will get more from this lesson, and besides that you enjoy the solution more if you thought about problem in the beginning, especially it applies to simple solutions. So now I will proceed to the solution. Okay so, we have this table and then here the solution is very simple. Lets look at the smaller problem, lets look at the small part of the current problem. And that's a very basic and natural here, and somehow it works very good in this situation. More precisely let's do the following, let's consider a sub table of this table at two by two corner to top left corner. And let's observe the following, if you switch a column or row in the large table, if we also switch a column or a row in the small table, or do nothing. So if you switch one of the two top rows in this table, then we switch a row in the small table as well, in the small sub table we consider. If we switch one of the first two columns, again, we switch columns in our small sub problem we are considering now, we are ignoring everything else. If we switch last two rows or last two columns, we just do nothing with our small sub problem. So if we can move in a large table, we either make the same in a small table, or we do nothing in a small table. So what does it mean? It means that if we want to solve the large problem, if we want to make all signs to be pluses in large problem, at the same time we will make all signs to be pluses in the small sub problem we're considering. And to apply exactly the same position we will switch rows and columns in this small sub table. Okay, but now this two by two problem is unsolvable by the old argument. It has odd number of minuses. And if we switch row and or a columns here, the number of minuses stay odd. So we cannot solve the small problem. And from it, we get that we cannot solve the large problem as well. If we could solve the large problem, we could have solved the small problem as well. And this is impossible by our old argument. Okay, now let's get a glimpse beyond what we are considering. So we note that we have found a very powerful obstacle. We note that if we are given such a table with pluses and minuses, and for it to be possible to switch to all signs to pluses. There should be even number of minuses in all two by two squares in this table. And this is a very powerful obstacle. For many tables, this is not satisfied and then we can immediately say this table is not possible to switch all sides of the table to get pluses. Okay, and it turns out that these are the only obstacles. So we have found a lot of obstacles and they are very powerful, and this is a complete set of obstacles. That is if our table satisfies all these restrictions, if for all two by two squares if a number of minuses is even, then it is always possible to switch all signs to plus. You can think about this problem yourself. We will not discuss it, but you can think it about yourself. It's not complicated on the same level of complexity. I will give a hint on next slides, so if you would like to think about it yourself, please stop now. So I'm switching to the hint. Let's consider a table, and let's assume that our invariant is satisfied. So all 2 x 2 squares has even number of minuses. And let's do the following, the first step, switch the first row and the first column to all pluses. This is always possible, it's not hard to do, so you can perform this. So you can perform switches of rows and columns in such a way that you obtain this position. And you do not know what is in the blank cells. And the second step, use this invariant to show that if you achieve this position, then all the rest cells also contain pluses. So now we're done with this problem and let's summarize what we have learned on this week. We have studied invariants and we observed it very important, and they can help a lot in different problems in a wide range of problems. And they can help to prove impossibility of something, they can also prove to count something. And also another important application is to show the process terminates or even recontrol them in variance. We can show bounds on the running time of some algorithms, and this is important especially for computer science. This is a very important application of invariance. Invariance can take many forms. It can be numbers. It can be properties of the number to be even or odd. It can be some equation. It can be some of the commodity. There are a lot of form of invariance. The important thing is, if there's something that doesn't change or changes in the right way. So double counting can be viewed as a special case of an invariant. And this is not all. There are other forms of invariants we haven't discussed. For example, the residues. And we will discuss some of them in the future in the next courses. [SOUND]
