Let S be any subset of {1,2,3,...,100} of size 12. Prove that there exist at least 4 different subsets of S such that the sum of elements of each set is the same. (For example, if S = {1,4,5,21,22,31,40,42,60,73,88,99}, we have the following 4 subsets that all sum to 103: {21,22,60}, {1,4,5,22,31,40}, {4,99}, {4,5,21,73}).
I can see that this statement is true for a few base cases like S = {1,2,3,4,5,6,7,8,9,10,11,12} but I don't know how to prove that it's true for any S.
We recently learned pigeonhole principle in class so I think I'm suppose to incorporate this into my solution but I don't know how.
I don't even know where to start. Any help would be appreciated.
I can see that this statement is true for a few base cases like S = {1,2,3,4,5,6,7,8,9,10,11,12} but I don't know how to prove that it's true for any S.
We recently learned pigeonhole principle in class so I think I'm suppose to incorporate this into my solution but I don't know how.
I don't even know where to start. Any help would be appreciated.