prove that every set of 10 two digit numbers has two disjoint subsets with the same sum of elements.
In this question i don't know how to choose the pigeon holes, or what will be the pigeon holes
2026-04-01 02:05:47.1775009147
how to find pigeon holes in a question related to pigeon hole principle
237 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Some of the better "pigeon hole" problems are quite subtle and it is not trivial to figure out how the principle will be used.
In this case, think of all the different sums you can create. (How many subsets, of all possible cardinalities, does a set with 10 elements have?) Those are the pigeons.
On the other hand, the sums are at most 1,000 (ten numbers, all two digits at most). These are the holes.
The pigeon hole principle, after you do the count in the second paragraph, will tell you that two of those sums, for two different subsets, must be equal. This doesn't give you DISJOINT subsets, but you can simply cancel out the common terms.