Dealing with Pigeonhole Principle Problems [closed]
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.
combinatorics contest-math pigeonhole-principle
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
$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.
add a comment |
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.
combinatorics contest-math pigeonhole-principle
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
$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
add a comment |
1
1
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.
combinatorics contest-math pigeonhole-principle
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
$endgroup$
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.
combinatorics contest-math pigeonhole-principle
combinatorics contest-math pigeonhole-principle
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
edited Jan 7 at 0:28
N. F. Taussig
44.2k93356
44.2k93356
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
asked Jan 6 at 23:02
Matthew TanMatthew Tan
755
755
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.
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
add a comment |
$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
$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
$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
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$
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$
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
$begingroup$
It's here, from 2006, without solution: mathematicalfoodforthought.com/2006/04
$endgroup$
– Gerry Myerson
Jan 6 at 23:25
add a comment |
1 Answer
1
active
oldest
votes
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?
answered Jan 7 at 5:34
T. FoT. Fo
466311
$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
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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?
answered Jan 7 at 5:34
T. FoT. Fo
466311
$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
add a comment |
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?
answered Jan 7 at 5:34
T. FoT. Fo
466311
$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
add a comment |
2
2
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?
answered Jan 7 at 5:34
T. FoT. Fo
466311
$endgroup$
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?
answered Jan 7 at 5:34
T. FoT. Fo
466311
edited Jan 7 at 5:53
answered Jan 7 at 5:34
T. FoT. Fo
466311
answered Jan 7 at 5:34
T. FoT. Fo
466311
answered Jan 7 at 5:34
T. FoT. Fo
466311
466311
$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
add a comment |
$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
$begingroup$
@Ford Sorry, can you explain further? I am not able to get it properly.
$endgroup$
– jayant98
Jan 7 at 5:42
$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$
@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
$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
add a comment |
$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