Re: A question about sets

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.

Re: A question about sets

Quote:

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

Re: A question about sets

Quote:

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.

Re: A question about sets

Quote:

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.

Re: A question about sets

Thank you very much for your advice and help.