(13) (50 points) Let be given integers, . For any -element set , consider the sums of the elements of all -element subsets of , and let the set of these sums be . The number of elements in the set is denoted as . Find the maximum value of .
Problem 774
Official solution
(13) The maximum value of is .
Since has -element subsets, it is obvious that .
Below, we point out that for the set , the corresponding equals , i.e., the sum of elements of any two different -element subsets of are not equal. Thus, the maximum value of is .
In fact, if the set has two different -element subsets , , such that the sums of the elements of and are equal, then
Since (1) can be viewed as the binary representation of the positive integer , and since are distinct and are distinct, by the uniqueness of the binary representation of positive integers, we deduce from (1) that the set , must be the same as , thus the subsets , which is a contradiction.
This proves our conclusion.