HMMT 二月 2003 · 冲刺赛 · 第 45 题

英文解析

45. Find a set S of positive integers such that no two distinct subsets of S have the samensum. Your score will be b 20(2 /r − 2) c , where n is the number of elements in the set S ,
    and r is the largest element of S (assuming, of course, that this number is nonnegative).
    n − 1
    Comments: The obvious such sets are those of the form { 1 , 2 , 4 , . . . , 2 } , but theseachieve a score of 0. A bit of experimentation finds that the set { 3 , 5 , 6 , 7 } also works;
    this answer achieves 5 points. The set { 6 , 9 , 11 , 12 , 13 } achieves 9 points. Doing significantly better than this by hand computation becomes difficult. The referencehttp://www.combinatorics.org/Volume 5/PDF/v 5 i 1 r 3.pdf
    “A Construction for Sets of Integers with Distinct Subset Sums,”
    by Tom Bohman, 1997
    (from whence the above examples) provides a construction that achieves a score of 50.
    Erd˝ os conjectured in effect that a maximum possible score exists, but this conjectureremains open. The strongest known result in this direction is that, if S has n elements,
    √
    the largest element is at least a constant times 2 / n (proven by Erd˝ os and Moser inn
    1955, with an improvement on the constant by Elkies in 1986).
    Hej d˚ a!
    14