there are possible proper subsets of . (A proper subset of is non empty subset of which is not equal to ). Let be a proper subset of .

Denote the sum of all the elements in by .

then for all proper subsets of .

So for any proper subset of there were admissible values of .

Now apply the Pigeon Hole Principle (a.k.a the dirchilet's box principle).

we had proper subsets and had only possible values of . So according to the Pigeon Hole Principle there are two proper subsets and of such that . If we are done. Else if then consider the proper subsets and that is delete the common elements from both and .