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.
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$$