Let be real numbers. Find the least positive integer with the following property: if there exist distinct sums of the form (with ) which are equal to , then .
Bulgaria, 2003
Solution
If the numbers are , (or ) there are sums that are equal to without the numbers themselves being . Therefore, knowing sums (or less) to be is not enough to conclude that the numbers are all .
Now we prove that is enough. Suppose we are given that sums are equal to . These sums contain, in total, terms, while there are only numbers. By the Pigeonhole Principle it follows that there is a number that appears (at least) times. Suppose appears (at least) times. is involved in sums, so there is only one sum, say , that is not necessarily . All the other ones are : . The first three equations simplify to , and then comparing the first and the last equation gives .
Finally, only participates in at most sums; the seventh one gives , and it follows immediately that .