Browse · MathNet
PrintBelarusian Mathematical Olympiad
Belarus counting and probability
Problem
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 .
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 .
Final answer
201
Techniques
Games / greedy algorithmsColoring schemes, extremal arguments