The next problem we are going to consider is a bit more tricky.

Suppose we have 30 persons in the room.

Some of them had shaken hands.

We need to show that there are two persons who shaked equal number of hands.

We have applied the pigeonhole principle before,

we are experienced so, let's count.

There are 30 people and they will be pigeons.

And the number of possible handshakes will be pigeonholes.

So we will show that, we would like to show that there are less pigeonholes than pigeons.

So, how many handshakes can a person have?

The minimal possible number is zero.

The person might have not shake hands at all and the largest possible is 29.

If a person shakes hands with everyone else it is 29 handshakes.

There are 29 persons except the person himself, 29 other persons.

So there are 30 options for handshakes.

There are 30 pigeon holes.

And it doesn't work so,

we have the same number of pigeons and pigeon holes.

So our, we cannot apply pigeon hole principle it doesn't work.Or maybe it does so,

maybe we just are not smart enough.

And indeed if you look at this a little bit more,

we observe that we can see one more detail this picture.

Observe that it is impossible to have zero handshakes and 29 handshakes in the same room.

It is impossible that someone in the same room,

there is one person who hasn't shaked at

all and there's another person who had shaken hands with everyone.

Because, these persons either had shaken hands between each other or not.

So if he had, first one doesn't have zero.

And if he didn't then the second one doesn't have 29.

So if you have a room,with people and so

there are 0 and 29 handshakes are impossible simultaneously.

And this leaves us with 29 pigeonholes.

So, and now there are to be two people who had the same number of handshakes.

So using this additional observation,

we make our pigeonhole principle work for this problem.

Let us summarize what we have learned in this lesson.

We have discussed proof by contradiction.

This is one of the most basic ways of reasoning.

It is used everywhere. It is usually

combined with other ideas but sometimes it can help on its own.

We have seen examples of that.

Next we discussed the pigeonhole principle.

One of the most basic proofs ideas.

It is used a lot in mathematics and maybe you have seen examples.

We will see other examples later.

On the other hand it is a very simple principle and basically amounts to counting.