This is a warning,
that if somebody asks you for an example,
maybe such an example doesn't exist.
So you should be prepared for the cases when the search doesn't help.
Let's look at the problem of splitting weights.
So imagine that you and your friend are preparing for a hike,
and you have identical backpacks,
and you want to be completely fair.
You have many items to bring for the hike,
but then you want to split them into groups of exactly the same weight.
For example, if you have three things of weights one,
two, three, then of course you put three in
one side and one into the other side and you are done.
So you can write like this.
And also, it's convenient to represent in another way,
so you can write,
instead of asking to split into two groups,
you can ask, "What kind of signs should be here?
Plus or minuses?"
So the total sum becomes zero.
So plus terms are equal to minus terms.
For our special case,
it's just plus one,
plus two, minus three.
Okay. This is the problem,
and the parameter of this problem is just the set of weights.
Let's try to consider some other more interesting example.
So imagine we have weights one, two, three, four, five,
seven, and we want to split them into two groups of equal weight.
But how do we do this?
The simplest question which you should ask yourself is,
"Just what is this equal weight?"
So we compute the total weight and we see that it's 22.
1, 3, 6, 10,
15, 22. Yeah, that's correct.
And then, if we want to split 22 into two groups,
each group should be 11,
and it's very easy to see a group of 11.
And after you find one group of 11,
the rest of course should be also 11,
and indeed, one plus two plus three is six plus 11.
So, you are done.
You'll find a group of weight 11 and then you know weight and the rest is also 11,
so everything is okay.
But not always, you are so lucky.
There can be cases when the task is impossible.
So imagine the weights are one, two, three,
four, five, six, not seven, but six.
And then, if you think,
"What is the total weight?"
It's 21, and maybe you already see that you cannot split this into
two equal groups for a very simple reason because 21 is not divisible by two.
And if you have two groups,
then they should be,
each group should have some integer weight,
so 21 will be a multiple of 2. So, not possible.
Now, just think of other case.
Imagine we have not one, two, three, four, five,
six, but 2, 4,
6, 8, 10 and 12.
Is it possible or not? Do you see?
Actually it's not possible, but do you see why?
Because it's actually the same problem.
We just take the same weights,
but twice bigger, so essentially we just change the unit,
we make a unit of weight twice more.
But you can also say that the total sum is not 21, but 42 now,
and 42 is divisible by two but the quotient is 21,
and it's odd, and you cannot get it by summing the even numbers.
Okay. Anyway. So this is just the bad news, now of course,
it's the special case there is nothing bad,
just the condition that we asked for something which doesn't exist.
But the bad news are coming,
and the bad news can be illustrated by the next example.
So imagine we have some other case, 1, 2,
3, 4, 5, 17,
not 7, but 17.
And if you count the total weight now,
it's 10 units bigger, so it's 32.
So it now is divisible by two, everything looks okay.
But, of course, if we divide it by two,
we get 16, and we have one piece of 17,
so 17 is too big.
If we put 17 somewhere,
there is not enough weights to put in the other side,
so this is another obstacle.
And the bad news really is that obstacles can be of different types,
and the problem is that there is no complete list of obstacles.
Of course, it would be nice to have some rule.
So if you want to split things into two group of equal weight,
you should check whether the sum is even,
whether there are not two big pieces, blah, blah, blah, blah,
and if some conditions are met,
then it's possible and you know how.
It's not the case.
For this problem, nobody know the complete list of
obstacles and nobody knows the way to check whether this is possible or not.
And maybe you heard the name NP-complete problem.
Actually, in scientific language,
it's translated into normal one as some infeasible problem.
So if you have, say, 10,000 numbers,
which is for computer 10,000 is something rather small.
But for this problem,
if you have 10,000 numbers,
then there is no way to check whether they can be split into two groups or not.
This is even worse.
There is no weights, it's a simplification.
We don't know how to do this.
And unfortunately, we cannot prove that such an algorithm doesn't exist.
You maybe heard about this P and NP problem,
this is exactly this question,
so whether there is an algorithm which solves this splitting weights problem.
So you see that you are now rather close to
the boundary of modern computer science knowledge,
or better to say that the boundary is very close to us,
because actually the problem is that people do not know much about NP-complete problems.
They tried it hard,
but no real success.
So what should you understand from this part of our course?
First, the structure of the proof depends on what you want to prove, of course.
Second, that if the statement is existential,
then you need only one example to prove it.
And also, you have no obligation to disclose how you find an example.
So if you cheated and asked the example from your friend,
probably it's morally not okay,
but from the mathematical proof point of view,
it's completely valid proof.
It's just a valid proof obtained by bad tools.
But still it's a proof.
And you should be prepared,
if you look for something,
this something may not exist at all and then you should not
spend the rest of your life looking for a solution.
It may not exist, and even maybe in some cases,
you can prove this,
but in some case,
unfortunately, it's very difficult.
So, maybe you're still in bad shape,
you don't know whether it exists or not,
this is also a possibility.
Alexander S. KulikovVisiting Professor
Michael LevinLecturer
Vladimir PodolskiiAssociate Professor
