Our next puzzle is the following.

We're given two-digit numbers that has integers 10,

11, 12 and so on, 99.

And we would like to take

as many of them as possible subject to the following constraint.

We are not allowed to take simultaneously two numbers X and Y,

if X + Y = 100.

But then otherwise, we are not allowed to take simultaneously x and 100 - X.

So the question is what is the maximum possible number of

two-digit integers that we can take under the given constraint?

So let's start solving this problem.

So first of all, if we take the smallest possible number, which is 10,

then it means that we cannot take 90 simultaneously together with 10, right?

And vice versa.

If we take 90 then we cannot take 10.

So in a sense 10 and 90 form a pair

such that from this pair we can take at most one number.

For exactly the same reason,

the numbers 11 and 89 also form the same pair.

From this pair we can take at most one number.

So continuing in the same question,

we discover 40 such pairs starting from 10 and 90 and going to 49 and 51.

Also there are ten like free numbers remaining.

So these are numbers without any pairs.

One of them is 50 because 50 is a pair for itself.

And the other nine numbers are 91,

92 and so on, 99.

For all these numbers there are no two-digit number that can be added to them to get 100.

So this tells us already that we

cannot take more than 50 numbers under the given constraint.

Why is that? Well, because we have

10 free numbers and all the remaining 80 numbers are paired.

And from each pair we can take at most one number.

So in total we call we can take

at most 10 plus 40 numbers which gives us 50 numbers, right?

So this is actually the universal part.

We've just proved that any solution cannot be of size more than 50.

At the same time,

it is not so difficult to contract the solution of size 50.

Just take all the numbers which are at least 50.

There are 50 such numbers and it is clear that it is a solution.

If you take any two numbers from the set,

the sum is going to be greater than 100. Okay?

So it was not very difficult.

But just to follow the same patterns that we discussed in the previous video,

let's wrap it as a formal theorem and let's prove it following the same pattern.

So the statement is the following:

the maximum number of two-digit numbers that one can take subject to

the constraint that there are no two numbers whose sum is equal to 100 is equal to 50.

So the first part is as usual,

universal, we need to show a solution.

And the solution is for example the numbers starting from 50.

It is not difficult to check that it is indeed a solution.

On the other hand, let's show the universal part that any solution has size at most 50.

To show this now that we have 40 pairs and we have 90 numbers in total

and we have among these 90 numbers

there are 40 pairs and from each pair we can pick at most one number.

So in total from each pair we need to exclude at least one number.

So in total we have at most 90 minus 40 which is equal to 50 numbers.

Subset without x and 100-x

What is a Proof?

与讲师见面