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 1 of 4: Give the eight-element construction

Previous step Next step

S=\{3,6,12,24,48,95,96,97\}=\{3\cdot2^k:0\le k\le5\}\cup\{95,96,97\}

Detailed analysis

Take the displayed set. The first six elements have subset sums 3t for every integer t from 1 through 63. Adding both 95 and 97 gives 192 plus those same sums; adding just 95 or just 97 gives sums congruent to minus one or one modulo three.