Question

Prove that no six positive integers, not exceeding 21, can have sums of all subsets different

Answer 1

SOLUTION

Given that,

So we have 6 positive integers all less than equal to 21.

smallest size of subset is 0 i e, of empty set it has sum equal to 0 as no elements are in it

And largest size is 6 with all integers in the subset

It can have the largest sum: 21+20+19+18+17+16 = 111

And total number of subsets is

2⁶ = 64 and number of possible sums is from 0 to 111 is 112

So if we have 64 boxes with i ^th box corresponding to subset with sum i and we assign each subset to the box i if the sum of its elements is i

Then we have 112 subsets and 64 boxes so by Pigeonhole principle at least two of the subsets are in the same box i e, at least two of the subsets have the same sum