Alibaba is the leader of Forty Thieves. One day, the thieves found 100 golden coins. The Forty Thieves wanted 80 golden coins, but the greedy Alibaba just want to own all the treasure. So he said to the thieves that:
I will divide the treasure to 2 groups with a positive integer number of coins.
Then, I choose a random group and divide it into 2 other groups with a positive integer number of coins.
I will continue this until there are 100 groups in total.
At any time of this process, If you can find 40 groups with a total of exactly 80 coins, then you can take this.
But if you cannot, you get nothing.
The thieves definitely can take 40 groups like that after a-th divide times whatever how Alibaba divide. What is the smallest of the value of a?
SOLUTION Consider the time we have 60 groups. Let $x$ be the number of groups that contain 1 coin. There are $60-x$ groups having at least 2 coins in each group. Because the total number of coins is 100 coins, we have inequation: $x + 2(60-x) \leq 100,$ i.e., $20 \leq x$. So by the time we have 60 groups, we have at least 20 groups contain 1 coin. So we chose 40 groups, leaving 20 groups which each contain a single coin. The 40 groups we chose have a total of 80 coins.
IS THE SOLUTION CORRECT?
Best Answer
Your answer of 60 groups for 100 gold coins is correct. By 60 groups, thieves would have surely found 40 such groups adding to 80 gold coins. It is easy to see how there is always an arrangement of groups for less than 60 groups where no 40 groups add up to 80.
Let's try for 59 groups.
After first division of 100 gold coins -
Say, $G_1 = 42$ and $G_2 = 58$
Now you can keep dividing $G_2$ into smaller groups till there are 58 groups, $G_2$ to $G_{59}$, with 1 gold coin each. But in the process, you would have never come across any 40 groups adding to 80 gold coins. It is simply because if you take $G_1 = 42$, you need 39 more groups but you need only 38 coins. Without $G_1$, you anyway have less than 80 gold coins.
When you take 60 groups, the largest size of $G_1$ can be 41 coins with rest 59 groups with 1 coin each. Even with that, you can do it because you need 39 coins from rest 39 groups. If you have smaller size of $G_1$, you may end sooner.