Problem 4

Let

n

and

b

be positive integers. We say

n

b

-discerning if there exists a set consisting of

n

different positive integers less than

b

that has no two different subsets

U

and

V

such that the sum of all elements in

U

equals the sum of all elements in

V

. (a) Prove that

8

100

-discerning. (b) Prove that

9

is not

100

-discerning.

Step 4 of 4: Contradict the bound below one hundred

Previous step Next step

(s_4+\cdots+s_9)-(s_1+s_2+s_3)\ge419,\quad (s_1+s_2+s_3+s_6+s_7+s_8+s_9)-(s_4+s_5)\ge399

Detailed analysis

Now count subsets having two, three, or four elements greater than s_3. There are 400 such subsets, so the second endpoint difference is at least 399. Adding the two inequalities gives s_6+s_7+s_8+s_9 at least 409. But each of these four numbers is at most 99, so their sum is at most 394, a contradiction. Thus part (b) follows.