Thread: A question about sets

Hi

Can someone help me with the following problem? I'd particularly appreciate an explanation, and hints on how to prove it. - THANKS in advance

Q) Suppose there is list of 10 integers n1,n2,n3, ...,n10, each of which lies
between 1 and 50 inclusively.

(part a) Let S be a nonempty subset of the list entries. Show that if I add up the
integers in S then the total lies between 1 and 500.

(b) Show that it is always possible to find two different subsets S and S' of the list
entries such that the sum of the integers in S equals the sum of the integers
in S'

.

Part (a) says that the sum of k numbers, each of which is from 1 to 50 and where 1 ≤ k ≤ 10, lies between 1 and 500. This is obvious.

For part (b) use the pigeonhole principle where pigeons are subsets and holes are numbers from 1 to 500.

Originally Posted by emakarov

Part (a) says that the sum of k numbers, each of which is from 1 to 50 and where 1 ≤ k ≤ 10, lies between 1 and 500. This is obvious.

For part (b) use the pigeonhole principle where pigeons are subsets and holes are numbers from 1 to 500.

Thank you

Originally Posted by emakarov

For part (b) use the pigeonhole principle where pigeons are subsets and holes are numbers from 1 to 500.

I came up with the following proof, could you kindly give some feedback or corrections as my proof writing ability is still a work in progress!

Suppose you have two different subsets, S & S'. Then by the Pidgeonhole principle, since S'>S, there has to be at least two integers between 1 - 500 that are contained in both sets.

Originally Posted by zzizi

Suppose you have two different subsets, S & S'. Then by the Pidgeonhole principle, since S'>S, there has to be at least two integers between 1 - 500 that are contained in both sets.

Sorry, this won't work. First, you start the proof by considering two arbitrary subsets S and S'. Such a proof corresponds to a theorem that starts with "For all subsets S and S', ..." One prove universal claims by considering an arbitrary object. In your case, however, the claim starts with "There exist two subsets S and S' such that ..." To prove it, you either need to construct these subsets or invoke another result that proves existence, such as pigeonhole principle. Viewed from another angle, it is wrong to start a proof by considering some S and S' when your task is to prove that such subsets (with equal sums) exist!

Second, S' > S does not make sense because S and S' are subsets, not numbers, and it is not clear what it means for one subset to be greater than another. Also, you have not shown S' > S, so you can's say "since S'>S."

Third, it is not clear how your situation satisfies the premise of the pigeonhole principle. Finally, the problem does not ask to show that two numbers belong to both sets, rather, that there exist two sets with the same sum.

To appy pigeonhole principle, you need to calculate how many nonempty subsets of 10 numbers (pigeons) there are. Each number is associated with its sum (hole). You can apply the principle if the number of subsets is greater than the number of possible sums.

Thank you very much for your advice and help.