Consider the following problem.

We have 10 boxes, and they are filled with a lot of white balls.

And we would like to distinguish these boxes.

And the only way to do it, and so

the only means to do is you have an answer our 30 black balls.

And they're identical, so how can we distinguish boxes now?

We can place different number of black balls into different boxes.

This way the boxes will be disguised.

So we have 10 boxes,

we have 30 black balls to distinguish them, can we do it or not?

We will really prove that this is impossible.

And for this, we will assume the contrary.

We will assume that we can do it.

And we will see that there is a contradiction.

So let's assume that we have placed black balls in the boxes in such a way

that there are different number of balls in different boxes, and

let's see what happens.

Okay, let us enumerate all boxes in the increasing order

of the number of black balls in there.

Okay, let's see what we can tell about the number of balls in each box,

consider the first box.

We basically, there might be any number of balls there, it's the whole 30 of course.

But that's all we know.

Okay, we can make a trivial statement, there's at least zero balls there.

We basically are saying nothing, but let's just say a trivial statement here.

Okay, but now let's look at the second box.

And the number of balls there is greater than the number of balls in

the first box, why?

So we enumerated boxes in increasing number of black balls, and

the number of balls in the first box and in the second box are different.

So we should have strictly greater number of black

balls in the second box than in the first box.

So there should be at least one black ball in the second box.

Now let's consider referred box.

Again, the number of black balls here should be greater

than the number of black balls in the second box.

It should be greater or equal than the number of black balls in the second box,

because we should enumerate boxes in the increasing order.

And it cannot be equal, because we have different number,

we have assumed that we have a different number of black balls in all boxes.

So there should be at least two black balls in the third box.

Okay, now we can proceed in the same way further.

So in the fourth box we should have greater of a number of black balls than in

the third one, so that should be at least three black balls.

Then in the fifth one, so there's four and so on and so forth.

In the end, we have at least nine black balls in the tenth box.

Okay, so that's what we have.

Now let's see how many balls.

So how many balls do we have in all boxes in total, so

let's sum up all of these numbers.

And if we sum up numbers from zero to nine,

we see that there are at least four to five balls in all the of boxes.

And note that this is a contradiction.

We know that we have 30 balls in total.

And now assumed that we have solved our, so we have placed balls in

boxes in such a way that is required in the formulation of the problem.

And now, we have 45 balls, and

this is a contradiction to the original formulation of the puzzle.

We have 30 black balls in the formulation and 45 black balls here.

So this is a contradiction, and so our assumption was wrong.

Our assumption was that we can do it.

And so, it is wrong and so we cannot do it, and

we have shown this rigorously.

[SOUND]

[MUSIC]

Balls in Boxes

What is a Proof?

Meet the Instructors