Our final optimality puzzle is,
it deals with numbers once again and it is
slightly more complicated than the previous ones.
So in this case we are given numbers from 1 to 50,
integers from 1 to 50 and our goal is to take as many of them as possible
with the constraint that we are not allowed to take x and 2x, simultaneously.
Okay so the question is what is the maximum number of
such integers that we can take to satisfy this constraint?
Okay, let's try to reason about this problem as usual.
So first of all the simplest constraint says that we can
not take 1 and 2 simultaneously so there is a conflict between 1 and 2.
But this is not the only complex that 2 participates in.
The other one is between 2 and 4.
You cannot take 2 and 4 simultaneously and you can actually extend this further.
So we extend this through a so-called chain which consists of 1,
2, 4, 8, 16 and 32, right?
So from this chain we now said we are not
allowed to take any two neighbors in this chain.
So this is just one of the chains.
Another such chain is for example it starts from 3.
So it is 3 then 6 then 12 then 24 and then 48, right?
For this chain we also know that from it we can not take any two neighbors
and in general you can partition all the ground set into such chains.
Each set chain starts with its own odd number.
So it is probably instructive to visualise it like this.
So in this case the first chain starts with the number 1
and we've seen it through 1, 2, 4, 8, 16, 32.
So this is on my first chain.
The next one starts with the next odd number,
3, 6, 12, 24, 58.
So it is already shorter.
The next one starts at 5 then 10 then 20 then 48.
It is already of size 4 and so on.
So when we reach the number 27 all the chains already are of the same,
of the length 1, I'm sorry.
So for all the chains starting with 27, for example 29, 31, 32,
all these chains consist of just a single integer number.
Okay then what it claims here is that the chains are independent.
So what this means so first of all each number appears in exactly one chain.
To actually finds this chain just take a number,
for example, I don't know,
46 and start dividing by 2.
So if you divide 46 by 2 you get 23 which means that this is,
that we know the beginning of your chain.
So each chain has
a unique odd starting number which means that all of them do not intersect.
And what is also important is that there are no conflicts between different chains.
So if you take any number like eight,
and if you take any other number from any other cell,
for example 28, we know for sure that these are not numbers of the form x and 2x.
All numbers of the form x and 2x,
they lie in the same chain.
Okay. This is already great because this means that we reduced
our problem of taking as many numbers from our ground set up,
all the numbers from 1 to 50 to the following problem.
We have chains, they are independent so our goal
is just for each chain to select the possible,
the maximum possible number.
Right. But this problem is much easier.
So if you have a chain,
for example this one and you know that you can not take any two consecutive numbers,
any two neighbors from this chain and you would like to maximize the number of
elements that you take,then of course the optimal strategy is to
start from the very beginning and to take every second number,
for example, this chain is going to be as follows: 1, 4 and 16.
For the next chain it is going to be for this one 3, 12 and 48.
For the next one it is going to be 5 and 20.
Clearly, for the chain starting with 5 so 5,
10, 20 and 40 you can not take more than two elements, right?
So this actually shows us that the optimal strategy of
taking as many numbers as possible is, in any chain to take every second number.
So this gives us this a solution which consists of the following highlighted numbers.
So we first take all the odd numbers,
there are 25 of them,
then we take also these six numbers and these two numbers.
So it is 25 plus 6 plus 2 which is 33.
So first of all it is a solution,
we see that it is indeed a solution so that there are
no two numbers that are of the form x and 2x.
And why it is optimal?
Well, just because we partition the ground set in the independent pieces and for
each such piece we prove that we've taken as many elements from these pieces,
from this particular piece as possible.
So this finally proves that 33 is indeed an optimal solution in this case.
