Bob has the collection of coins. Each of them weights an integer number of grams, and their total weight is equal to grams. Let be positive integers such that .
Find the smallest possible number of for which Bob always (independently of coin's weights and for all possible ) can partition his collection into three groups so that the total weight of the coins in the first, second, and third groups is equal to , and grams, respectively.
Solution
Answer: .
Let be the weights of the coins in Bob's collection. If there exists an such that , and , then, obviously, Bob cannot partition his collection into three equally weighted groups. It is easy to see that if , then there can exist an (e.g., , ). Therefore, .
We now show that the smallest possible value of is .
First, note that if , then , where . Indeed, if , then , and in this case , contrary to the problem condition.
Without loss of generality, we suppose that . Thus . So the first coins combine into the first group ().
We renumber the remaining weights: . The total weight of these coins is equal to
which implies
In particular, since .
Now we show how to form the third group with the weight equal to .
Consider the sums:
If one of these sums is equal to , then the corresponding coins combine into the third group, and the remaining coins combine into the second group with the weight equal to . Otherwise, there exists a , such that and . In particular, , i.e. . This means that among the numbers , , ..., there are no 's. Moreover, this means that . So
and the corresponding coins combine into the third group. The remaining coins combine into the second group with weight equal to .