Let be a natural number. Ana chooses the non-zero natural numbers , and for each non-empty subset , she computes the sum , then arranges these sums in increasing order, obtaining the sequence .
Show that there exists a subset , with elements, such that, no matter what values Ana chooses for , these values can be determined by knowing all the values , for .
Cristi Săvescu
Solution
Assume . If we choose the subset , then among the sums , the values will appear for some . Clearly, , and if appears as a sum, then must have appeared before it.
Indeed, consider:
a) if , then the appearance is obvious.
b) if , then since and appears as some , the index corresponding to is less than , hence appeared earlier.
If , then at most sums can appear, corresponding to non-empty subsets of . Hence, we deduce that .
Therefore, the first two sums correspond to the numbers and . Then, inductively, after determining the numbers , we compute all the subset sums of , remove them from the list of known sums, and the smallest remaining sum must be .
So, we can determine the numbers .
If we also include the index , we obtain , which is the total sum of all numbers. Then we can compute , and thus all numbers.