Hi. I'm Vladimir Podolskii,

and today we're going to discuss termination of processes.

We have used invariants before to show impossibility.

And for us invariants were properties that do not change.

In a more wide sense,

we can call by invariant the property that changes but in the right way.

For example, if it is a number,

it might be only increasing or only decreasing.

So it mostly depends on the problem you're currently considering.

And another standard use of invariants is showing termination of some processes,

and that's what we are going to discuss in this lesson. Consider the following problem.

There is a town and there are two football teams in this town,

whatever football means in your country.

Each of the citizens is supporting one of the teams.

And if among someone's friends,

there are more supporters of the other team,

than of his own, then this person switches to supporting another team.

Each day one such person switches, exactly one.

Is it possible that this process goes forever?

Is it possible that people switches from supporting one team to another forever?

And okay, we have enough medical course.

So, we will assume here that friendship is always mutual.

So, if someone is friend to another person,

then this another person is friend to him as well,

and the population of the city doesn't change,

and a friendship also doesn't change.

So it seems natural that this process will stop.

Maybe more popular team will just gather all of the fans,

or something like that, it seems natural.

But how can we prove it formally?

So, how can we prove it informatically that the process will stop?

And the idea is to look at the right value, to look at the right number.

OK, we will look at the following number.

Consider all friendships, all pairs of

people that are friends and that are supporting opposite teams.

Let's see what happens to this number after one day.

What changes after one day?

There is a person who can switch to supporting the opposite team.

And when this happens, it happens.

So in these picture we represent people by circles and we represent friendship by lines.

And this person in this picture switches to support another team.

If there are more of his friends supporting the opposite team,

then the number of his friends supporting the same team.

OK, in the beginning,

the edges on the right of this picture,

the lines on the right of his picture are counted in the number we are considering.

OK, now we'll see what happens when this person switches to support the other team.

OK, now the edges on the left are counted in

the number we are considering instead of edges on the right.

And note, since there are more circles on the right than on the left,

then the number of edges we are counting for this person decreases.

And this is all what changes during the day.

So it turns out that the number we are considering,

the number of friendships such that friends support opposite teams,

always decreases, and decreases during each day.

But it cannot decrease forever,

it should be non-negative number.

So the process should stop.