Question

Let A = {x1, x2, . . . , x12} be a set of 12 positive integers, not necessarily distinct, such that xi ≤ 150, 1 ≤ i ≤ 12. Prove that there are at least two different 6-element subsets S1 and S2 of A such that the sum of the elements in S1 is equal to the sum of the elements in S2. Use Pigeonhole principal.

Answer 1

By pigeon hole principle, at least 2 subsets of A have same sum

Explanation:

Let A = {x1, x2, . . . , x12} where i ≤ xi≤150

for any 6 element subset S of A, the sum of numbers in S is at least 6 since all integers are positive and it is at most 150+149+148+147+146+145= 885. so we consider number of pigeon holes = number of possible sums= 885 and number of pigeons = number of subsets of A of size 6= ¹²C₆= 924

Since number of pigeons is greater than number of pigeon holes, by pigeon hole principle, at least 2 subsets of A have same sum