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 2 of 4: Count all subset sums

Previous step Next step

63+64+64+64=255=2^8-1

Detailed analysis

The four families occupy disjoint residue or size ranges and contain respectively 63, 64, 64, and 64 sums. They therefore give 255 distinct sums, exactly the number of nonempty subsets of an eight-element set. The construction proves part (a).