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

HMMT February 2003 — Guts Round — Problem 45

Find a set S of positive integers such that no two distinct subsets of S have the same n sum. 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). Hej d˚ a! 6

解析

Find a set S of positive integers such that no two distinct subsets of S have the same n sum. 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 these achieve 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 signif- icantly better than this by hand computation becomes difficult. The reference http://www.combinatorics.org/Volume 5/PDF/v5i1r3.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 conjecture remains open. The strongest known result in this direction is that, if S has n elements, √ n the largest element is at least a constant times 2 / n (proven by Erd˝ os and Moser in 1955, with an improvement on the constant by Elkies in 1986). Hej d˚ a! 14