1
$\begingroup$

Question: Eleven numbers are chosen from 1, 2, 3, ..., 99, 100. Show that there are two nonempty disjoint subsets of these eleven numbers whose elements have the same sum.

Does anyone know how to solve this question using the pigeonhole principle? I've tried to do so but encountered difficulty in determining which pigeonholes to select.

$\endgroup$

closed as off-topic by A. Pongrácz, Eevee Trainer, KReiser, Cesareo, José Carlos Santos Jan 7 at 8:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – A. Pongrácz, Eevee Trainer, KReiser, Cesareo, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Given the [contest-math] tag, could you please link to the contest this is from? It is MSE policy not to help with current contests, so we'd like to verify that this particular contest has ended. $\endgroup$ – Theo Bendit Jan 6 at 23:07
  • 2
    $\begingroup$ Small hint: if two distinct subsets have the same sum, then two nonempty disjoint subsets have the same sum. I've seen this question in a textbook, so if it's from an ongoing contest, then the people running the contest are copying their questions from published sources. $\endgroup$ – Gerry Myerson Jan 6 at 23:17
  • $\begingroup$ Here's a source from 1995: math.ust.hk/excalibur/v1_n1.pdf It's also at mathcircle.berkeley.edu/sites/default/files/archivedocs/… from 1999, but without solution. $\endgroup$ – Gerry Myerson Jan 6 at 23:19
  • $\begingroup$ It's here, from 2006, without solution: mathematicalfoodforthought.com/2006/04 $\endgroup$ – Gerry Myerson Jan 6 at 23:25
2
$\begingroup$

Hint:

Your set of 11 chosen numbers has $2^{11} - 2 = 2048$ distinct non-empty subsets (pigeons).

The smallest possible sum of a subset is $1$ and the largest is $90 + 91 + \ldots + 99 + 100 = 1045$ (pigeonholes).

Do you see how you can then apply the pigeonhole principle and @Gerry's hint?

$\endgroup$
  • $\begingroup$ @Ford Sorry, can you explain further? I am not able to get it properly. $\endgroup$ – jayant98 Jan 7 at 5:42
  • $\begingroup$ @DavidK good catch. I suppose we could make it non-empty subsets and then have there be $2^{11} - 2$ distinct subsets to keep the possible sums non-zero. $\endgroup$ – T. Fo Jan 7 at 5:46
  • $\begingroup$ I made a mistake. I just re-read the problem and I see it says "non-empty." Also the two subsets must be disjoint, so both are proper subsets. So $2^{11}-2$ is the number of subsets and the least sum is $1$ after all. $\endgroup$ – David K Jan 7 at 5:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.