Is this a valid proof using Pigeon Hole Principle?

35 Views Asked by At

Pigeon Hole Question from last semester
S = { 1, 2, 3, . . . 100 }

examples of sets that add to 3: {1 , 2}
examples of sets that add to 4: {1 , 3}
examples of sets that add to 5: {3 , 2}, {4 , 1}
examples of sets that add to 6: {4 , 2}, {5 , 1}
examples of sets that add to 7: {4 , 3}, {5 , 2}, {6 , 1}
examples of sets that add to 8: {2 , 6}, {5 , 3}, {7 , 1}
examples of sets that add to 9: {1 , 8}, {2 , 7}, {5 , 4}, {3 , 6}

There are 10 pigeons and 9 holes. Therefore by PHP there are 2 elements in a subset.
From the above eamples we see that there exists two or more subsets that can be made
which add to the same number and as the sum increases so does the possible subsets.

2

There are 2 best solutions below

1
On

No need for PHP. Just note that $$1+3+4+5+6+7+8+9+10+12 = 2+3+4+5+6+7+8+9+10+11$$

0
On

The subsets of size $10$ have a sum that ranges from $55$ to $955$, and presumably all sums are possible, hence $901$ distinct values.

But there are $\displaystyle\binom{100}{10}$ ways to form the sums, which is a much larger number.