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 3 of 4: Apply the first pigeonhole count

Previous step Next step

\binom93+\binom94+\binom95+\binom96=420

Detailed analysis

Assume nine elements exist and order them as s_1<...<s_9<100. Among subsets of sizes three through six, all sums are distinct and lie between the smallest three-element sum and the largest six-element sum. Hence their range has at least 420 integers, so the difference between those endpoint sums is at least 419.