Pigeon hole principle: Prove that any set of six positive integers whose sum is 13 must contain at least one...
up vote
1
down vote
favorite
Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three.
My work. I am trying by using the Pigeon hole principle. I have proved that at least two non-empty disjoint subsets have the same sum but can't go any further.
discrete-mathematics pigeonhole-principle
closed as off-topic by Shaun, amWhy, Paul Frost, user302797, user10354138 Nov 24 at 16:25
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 improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Shaun, amWhy, Paul Frost, user302797, user10354138
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
1
down vote
favorite
Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three.
My work. I am trying by using the Pigeon hole principle. I have proved that at least two non-empty disjoint subsets have the same sum but can't go any further.
discrete-mathematics pigeonhole-principle
closed as off-topic by Shaun, amWhy, Paul Frost, user302797, user10354138 Nov 24 at 16:25
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 improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Shaun, amWhy, Paul Frost, user302797, user10354138
If this question can be reworded to fit the rules in the help center, please edit the question.
Can you show your work? You will get better help.
– tarit goswami
Nov 23 at 13:06
The question specifically asks for the use of Pigeon hole principle. Since each of the six numbers is not distinct, and a subset need not be of consecutive numbers, I couldn't really apply the principle. So far, I have established that there are 63 non-empty subsets, the sum of each of which lies between 1 and 13. Therefore, at least 5 subsets have the same sum. Removing the common elements from any two, we can get a pair of disjoint sets. But the problem is still not solved.
– Divyansh Hardia
Nov 23 at 14:10
1
There are no sets of positive integers with six members whose sum is 13. (The elements of a set are distinct by definition.)
– David Hartley
Nov 23 at 17:36
Please consider identical elements.
– Divyansh Hardia
Nov 23 at 19:08
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three.
My work. I am trying by using the Pigeon hole principle. I have proved that at least two non-empty disjoint subsets have the same sum but can't go any further.
discrete-mathematics pigeonhole-principle
Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three.
My work. I am trying by using the Pigeon hole principle. I have proved that at least two non-empty disjoint subsets have the same sum but can't go any further.
discrete-mathematics pigeonhole-principle
discrete-mathematics pigeonhole-principle
edited Nov 23 at 13:46
Robert Z
92.5k1059130
92.5k1059130
asked Nov 23 at 13:01
Divyansh Hardia
121
121
closed as off-topic by Shaun, amWhy, Paul Frost, user302797, user10354138 Nov 24 at 16:25
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 improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Shaun, amWhy, Paul Frost, user302797, user10354138
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Shaun, amWhy, Paul Frost, user302797, user10354138 Nov 24 at 16:25
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 improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Shaun, amWhy, Paul Frost, user302797, user10354138
If this question can be reworded to fit the rules in the help center, please edit the question.
Can you show your work? You will get better help.
– tarit goswami
Nov 23 at 13:06
The question specifically asks for the use of Pigeon hole principle. Since each of the six numbers is not distinct, and a subset need not be of consecutive numbers, I couldn't really apply the principle. So far, I have established that there are 63 non-empty subsets, the sum of each of which lies between 1 and 13. Therefore, at least 5 subsets have the same sum. Removing the common elements from any two, we can get a pair of disjoint sets. But the problem is still not solved.
– Divyansh Hardia
Nov 23 at 14:10
1
There are no sets of positive integers with six members whose sum is 13. (The elements of a set are distinct by definition.)
– David Hartley
Nov 23 at 17:36
Please consider identical elements.
– Divyansh Hardia
Nov 23 at 19:08
add a comment |
Can you show your work? You will get better help.
– tarit goswami
Nov 23 at 13:06
The question specifically asks for the use of Pigeon hole principle. Since each of the six numbers is not distinct, and a subset need not be of consecutive numbers, I couldn't really apply the principle. So far, I have established that there are 63 non-empty subsets, the sum of each of which lies between 1 and 13. Therefore, at least 5 subsets have the same sum. Removing the common elements from any two, we can get a pair of disjoint sets. But the problem is still not solved.
– Divyansh Hardia
Nov 23 at 14:10
1
There are no sets of positive integers with six members whose sum is 13. (The elements of a set are distinct by definition.)
– David Hartley
Nov 23 at 17:36
Please consider identical elements.
– Divyansh Hardia
Nov 23 at 19:08
Can you show your work? You will get better help.
– tarit goswami
Nov 23 at 13:06
Can you show your work? You will get better help.
– tarit goswami
Nov 23 at 13:06
The question specifically asks for the use of Pigeon hole principle. Since each of the six numbers is not distinct, and a subset need not be of consecutive numbers, I couldn't really apply the principle. So far, I have established that there are 63 non-empty subsets, the sum of each of which lies between 1 and 13. Therefore, at least 5 subsets have the same sum. Removing the common elements from any two, we can get a pair of disjoint sets. But the problem is still not solved.
– Divyansh Hardia
Nov 23 at 14:10
The question specifically asks for the use of Pigeon hole principle. Since each of the six numbers is not distinct, and a subset need not be of consecutive numbers, I couldn't really apply the principle. So far, I have established that there are 63 non-empty subsets, the sum of each of which lies between 1 and 13. Therefore, at least 5 subsets have the same sum. Removing the common elements from any two, we can get a pair of disjoint sets. But the problem is still not solved.
– Divyansh Hardia
Nov 23 at 14:10
1
1
There are no sets of positive integers with six members whose sum is 13. (The elements of a set are distinct by definition.)
– David Hartley
Nov 23 at 17:36
There are no sets of positive integers with six members whose sum is 13. (The elements of a set are distinct by definition.)
– David Hartley
Nov 23 at 17:36
Please consider identical elements.
– Divyansh Hardia
Nov 23 at 19:08
Please consider identical elements.
– Divyansh Hardia
Nov 23 at 19:08
add a comment |
6 Answers
6
active
oldest
votes
up vote
4
down vote
Hint. Let $1leq a_1leq a_2leq a_3leq a_4leq a_5leq a_6$. We know that $sum_{k=1}^n a_k=13$.
Now consider the following cases:
1) If $a_4geq 4$ then $$10=13-1-1-1geq 13-a_1-a_2-a_3\=a_4+a_5+a_6geq 4cdot 3=12$$
which is a contradiction.
2) If $a_4=3$ then ...
3) If $a_4leq 2$ then ...
I don't think that the Pigeonhole principle is strictly necessary here.
I tried to do something similar, but starting with $a_1ge3$ and $a_1lt3$. However, the case ${2,2,2,2,2,3}$ was quite boring to solve. Does assuming properties on $a_3$ rather than $a_1$ help proving it quickly?
– F.Carette
Nov 23 at 13:35
@F.Carette See my edit. Is it quicker?
– Robert Z
Nov 23 at 13:41
A bit quicker indeed! +1
– F.Carette
Nov 23 at 13:44
add a comment |
up vote
2
down vote
(Not pigeonhole)The numbers in the set $S$ cannot all be distinct, because you will get more than 13 as sum otherwise. So there has to have repeat. The only way to get 3 is $1+2$, $1+1+1$ or $3$. so It suffices to show $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Suppose not,
case 1: $S$ contains no 3 and less than three 1 and no 2. Then $S$ contains at most two 1 and the rest are at least 4 which is not possible.
case 2: $S$ contains no 3 and no 1. It is not possible again.
So $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Then you can get a subset whose sum is 3?
add a comment |
up vote
1
down vote
Clearly, some of the elements in the set must be below $4$. (Otherwise, the sum would be at least $4 cdot 6 =24$.)
Now we argue by contradiction. Suppose no subset has sum $3$. Then in particular, $3$ cannot occur in the set, and either $1$ or $2$ may not occur.
Suppose $1$ does not occur. If all elements equal $2$, the sum is $12$ instead of $13$. If at least one element is at least $4$, then the sum is at least $2+2+2+2+2+4=14$, contradiction.
Suppose $2$ does not occur. Note that there can be at most two $1$'s. So the total sum is at least $1+1+4+4+4+4=18$, contradiction.
As each case leads to a contradiction, we conclude that our initial assumption that no subset has sum $3$ must be false.
add a comment |
up vote
0
down vote
The set cannot contain the number 3.
Now consider how many of the numbers can be $ge 4$. Clearly there can not be more than three of them, or the sum would be $ge 13$. There can not be three either, because the sum of the other three numbers would be $ge 3$ and the sum of all 6 would be $ge 15$.
So there are at most 2 numbers $ge 4$, i.e. there are at least 4 numbers $le 2$.
If any of those four numbers is $1$, there is a subset ${1,2}$ or ${1,1,1}$ which sums to $3$.
Therefore, there are at least $4$ numbers equal to $2$, and the other numbers are all $ge 4$.
But that is impossible, because if all six numbers are equal to $2$ the sum is $12$, and if four or five are equal to 2 the sum is $ge 13$.
add a comment |
up vote
0
down vote
Represent the problem in the following manner.
You have 6 pigeonholes (representing each integer) and 13 pigeons (the total sum). Each hole must have at least one pigeon for the integers to be positive, so you can equivalently consider a problem with 6 pigeonholes and 7 pigeons (with some holes possibly having zero pigeons). Hey, that's kinda familiar...
By PHP, in the equivalent problem at least one hole must have 2 pigeons. Further, that hole can't have exactly 2 (since that'd represent 3 as a number), so it has to have at least 3.
The rest is left as an exercise for the reader.
Hint: is another hole is forced to have an exact number of pigeons now?
add a comment |
up vote
0
down vote
Note that since the overall sum is odd, you must have at least one odd number in your set (collection) of six. You must also have at least one even number, because the sum of six odd numbers would be even. That cuts down the possibilities quite quickly.
Suppose there were a contradiction.
Amongst odd numbers you can't have $3$ and if you have $1$ you can't have $2$ among the even numbers.
So either your smallest odd number is at least $5$ (and this is the only odd number, since three would take you over total). But then the evens would have to at least $10$ (five twos is the minimum) ...
Or you have at least one $1$. You can't have three ones, and you can have at most three odd (since only two can be less than $5$ and five odds would have to include three greater than $4$). The lowest total for evens, given there are no $2$s in this case, would be at least three fours = $12$, and you can't fit six in here either.
So neither case is possible, and there must be a sum of $3$.
add a comment |
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
Hint. Let $1leq a_1leq a_2leq a_3leq a_4leq a_5leq a_6$. We know that $sum_{k=1}^n a_k=13$.
Now consider the following cases:
1) If $a_4geq 4$ then $$10=13-1-1-1geq 13-a_1-a_2-a_3\=a_4+a_5+a_6geq 4cdot 3=12$$
which is a contradiction.
2) If $a_4=3$ then ...
3) If $a_4leq 2$ then ...
I don't think that the Pigeonhole principle is strictly necessary here.
I tried to do something similar, but starting with $a_1ge3$ and $a_1lt3$. However, the case ${2,2,2,2,2,3}$ was quite boring to solve. Does assuming properties on $a_3$ rather than $a_1$ help proving it quickly?
– F.Carette
Nov 23 at 13:35
@F.Carette See my edit. Is it quicker?
– Robert Z
Nov 23 at 13:41
A bit quicker indeed! +1
– F.Carette
Nov 23 at 13:44
add a comment |
up vote
4
down vote
Hint. Let $1leq a_1leq a_2leq a_3leq a_4leq a_5leq a_6$. We know that $sum_{k=1}^n a_k=13$.
Now consider the following cases:
1) If $a_4geq 4$ then $$10=13-1-1-1geq 13-a_1-a_2-a_3\=a_4+a_5+a_6geq 4cdot 3=12$$
which is a contradiction.
2) If $a_4=3$ then ...
3) If $a_4leq 2$ then ...
I don't think that the Pigeonhole principle is strictly necessary here.
I tried to do something similar, but starting with $a_1ge3$ and $a_1lt3$. However, the case ${2,2,2,2,2,3}$ was quite boring to solve. Does assuming properties on $a_3$ rather than $a_1$ help proving it quickly?
– F.Carette
Nov 23 at 13:35
@F.Carette See my edit. Is it quicker?
– Robert Z
Nov 23 at 13:41
A bit quicker indeed! +1
– F.Carette
Nov 23 at 13:44
add a comment |
up vote
4
down vote
up vote
4
down vote
Hint. Let $1leq a_1leq a_2leq a_3leq a_4leq a_5leq a_6$. We know that $sum_{k=1}^n a_k=13$.
Now consider the following cases:
1) If $a_4geq 4$ then $$10=13-1-1-1geq 13-a_1-a_2-a_3\=a_4+a_5+a_6geq 4cdot 3=12$$
which is a contradiction.
2) If $a_4=3$ then ...
3) If $a_4leq 2$ then ...
I don't think that the Pigeonhole principle is strictly necessary here.
Hint. Let $1leq a_1leq a_2leq a_3leq a_4leq a_5leq a_6$. We know that $sum_{k=1}^n a_k=13$.
Now consider the following cases:
1) If $a_4geq 4$ then $$10=13-1-1-1geq 13-a_1-a_2-a_3\=a_4+a_5+a_6geq 4cdot 3=12$$
which is a contradiction.
2) If $a_4=3$ then ...
3) If $a_4leq 2$ then ...
I don't think that the Pigeonhole principle is strictly necessary here.
edited Nov 23 at 13:37
answered Nov 23 at 13:28
Robert Z
92.5k1059130
92.5k1059130
I tried to do something similar, but starting with $a_1ge3$ and $a_1lt3$. However, the case ${2,2,2,2,2,3}$ was quite boring to solve. Does assuming properties on $a_3$ rather than $a_1$ help proving it quickly?
– F.Carette
Nov 23 at 13:35
@F.Carette See my edit. Is it quicker?
– Robert Z
Nov 23 at 13:41
A bit quicker indeed! +1
– F.Carette
Nov 23 at 13:44
add a comment |
I tried to do something similar, but starting with $a_1ge3$ and $a_1lt3$. However, the case ${2,2,2,2,2,3}$ was quite boring to solve. Does assuming properties on $a_3$ rather than $a_1$ help proving it quickly?
– F.Carette
Nov 23 at 13:35
@F.Carette See my edit. Is it quicker?
– Robert Z
Nov 23 at 13:41
A bit quicker indeed! +1
– F.Carette
Nov 23 at 13:44
I tried to do something similar, but starting with $a_1ge3$ and $a_1lt3$. However, the case ${2,2,2,2,2,3}$ was quite boring to solve. Does assuming properties on $a_3$ rather than $a_1$ help proving it quickly?
– F.Carette
Nov 23 at 13:35
I tried to do something similar, but starting with $a_1ge3$ and $a_1lt3$. However, the case ${2,2,2,2,2,3}$ was quite boring to solve. Does assuming properties on $a_3$ rather than $a_1$ help proving it quickly?
– F.Carette
Nov 23 at 13:35
@F.Carette See my edit. Is it quicker?
– Robert Z
Nov 23 at 13:41
@F.Carette See my edit. Is it quicker?
– Robert Z
Nov 23 at 13:41
A bit quicker indeed! +1
– F.Carette
Nov 23 at 13:44
A bit quicker indeed! +1
– F.Carette
Nov 23 at 13:44
add a comment |
up vote
2
down vote
(Not pigeonhole)The numbers in the set $S$ cannot all be distinct, because you will get more than 13 as sum otherwise. So there has to have repeat. The only way to get 3 is $1+2$, $1+1+1$ or $3$. so It suffices to show $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Suppose not,
case 1: $S$ contains no 3 and less than three 1 and no 2. Then $S$ contains at most two 1 and the rest are at least 4 which is not possible.
case 2: $S$ contains no 3 and no 1. It is not possible again.
So $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Then you can get a subset whose sum is 3?
add a comment |
up vote
2
down vote
(Not pigeonhole)The numbers in the set $S$ cannot all be distinct, because you will get more than 13 as sum otherwise. So there has to have repeat. The only way to get 3 is $1+2$, $1+1+1$ or $3$. so It suffices to show $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Suppose not,
case 1: $S$ contains no 3 and less than three 1 and no 2. Then $S$ contains at most two 1 and the rest are at least 4 which is not possible.
case 2: $S$ contains no 3 and no 1. It is not possible again.
So $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Then you can get a subset whose sum is 3?
add a comment |
up vote
2
down vote
up vote
2
down vote
(Not pigeonhole)The numbers in the set $S$ cannot all be distinct, because you will get more than 13 as sum otherwise. So there has to have repeat. The only way to get 3 is $1+2$, $1+1+1$ or $3$. so It suffices to show $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Suppose not,
case 1: $S$ contains no 3 and less than three 1 and no 2. Then $S$ contains at most two 1 and the rest are at least 4 which is not possible.
case 2: $S$ contains no 3 and no 1. It is not possible again.
So $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Then you can get a subset whose sum is 3?
(Not pigeonhole)The numbers in the set $S$ cannot all be distinct, because you will get more than 13 as sum otherwise. So there has to have repeat. The only way to get 3 is $1+2$, $1+1+1$ or $3$. so It suffices to show $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Suppose not,
case 1: $S$ contains no 3 and less than three 1 and no 2. Then $S$ contains at most two 1 and the rest are at least 4 which is not possible.
case 2: $S$ contains no 3 and no 1. It is not possible again.
So $S$ contains at least one 3 or at least three 1's or at least one 1 and one 2. Then you can get a subset whose sum is 3?
answered Nov 23 at 13:27
mathnoob
1,757322
1,757322
add a comment |
add a comment |
up vote
1
down vote
Clearly, some of the elements in the set must be below $4$. (Otherwise, the sum would be at least $4 cdot 6 =24$.)
Now we argue by contradiction. Suppose no subset has sum $3$. Then in particular, $3$ cannot occur in the set, and either $1$ or $2$ may not occur.
Suppose $1$ does not occur. If all elements equal $2$, the sum is $12$ instead of $13$. If at least one element is at least $4$, then the sum is at least $2+2+2+2+2+4=14$, contradiction.
Suppose $2$ does not occur. Note that there can be at most two $1$'s. So the total sum is at least $1+1+4+4+4+4=18$, contradiction.
As each case leads to a contradiction, we conclude that our initial assumption that no subset has sum $3$ must be false.
add a comment |
up vote
1
down vote
Clearly, some of the elements in the set must be below $4$. (Otherwise, the sum would be at least $4 cdot 6 =24$.)
Now we argue by contradiction. Suppose no subset has sum $3$. Then in particular, $3$ cannot occur in the set, and either $1$ or $2$ may not occur.
Suppose $1$ does not occur. If all elements equal $2$, the sum is $12$ instead of $13$. If at least one element is at least $4$, then the sum is at least $2+2+2+2+2+4=14$, contradiction.
Suppose $2$ does not occur. Note that there can be at most two $1$'s. So the total sum is at least $1+1+4+4+4+4=18$, contradiction.
As each case leads to a contradiction, we conclude that our initial assumption that no subset has sum $3$ must be false.
add a comment |
up vote
1
down vote
up vote
1
down vote
Clearly, some of the elements in the set must be below $4$. (Otherwise, the sum would be at least $4 cdot 6 =24$.)
Now we argue by contradiction. Suppose no subset has sum $3$. Then in particular, $3$ cannot occur in the set, and either $1$ or $2$ may not occur.
Suppose $1$ does not occur. If all elements equal $2$, the sum is $12$ instead of $13$. If at least one element is at least $4$, then the sum is at least $2+2+2+2+2+4=14$, contradiction.
Suppose $2$ does not occur. Note that there can be at most two $1$'s. So the total sum is at least $1+1+4+4+4+4=18$, contradiction.
As each case leads to a contradiction, we conclude that our initial assumption that no subset has sum $3$ must be false.
Clearly, some of the elements in the set must be below $4$. (Otherwise, the sum would be at least $4 cdot 6 =24$.)
Now we argue by contradiction. Suppose no subset has sum $3$. Then in particular, $3$ cannot occur in the set, and either $1$ or $2$ may not occur.
Suppose $1$ does not occur. If all elements equal $2$, the sum is $12$ instead of $13$. If at least one element is at least $4$, then the sum is at least $2+2+2+2+2+4=14$, contradiction.
Suppose $2$ does not occur. Note that there can be at most two $1$'s. So the total sum is at least $1+1+4+4+4+4=18$, contradiction.
As each case leads to a contradiction, we conclude that our initial assumption that no subset has sum $3$ must be false.
answered Nov 23 at 16:16
user133281
13.6k22551
13.6k22551
add a comment |
add a comment |
up vote
0
down vote
The set cannot contain the number 3.
Now consider how many of the numbers can be $ge 4$. Clearly there can not be more than three of them, or the sum would be $ge 13$. There can not be three either, because the sum of the other three numbers would be $ge 3$ and the sum of all 6 would be $ge 15$.
So there are at most 2 numbers $ge 4$, i.e. there are at least 4 numbers $le 2$.
If any of those four numbers is $1$, there is a subset ${1,2}$ or ${1,1,1}$ which sums to $3$.
Therefore, there are at least $4$ numbers equal to $2$, and the other numbers are all $ge 4$.
But that is impossible, because if all six numbers are equal to $2$ the sum is $12$, and if four or five are equal to 2 the sum is $ge 13$.
add a comment |
up vote
0
down vote
The set cannot contain the number 3.
Now consider how many of the numbers can be $ge 4$. Clearly there can not be more than three of them, or the sum would be $ge 13$. There can not be three either, because the sum of the other three numbers would be $ge 3$ and the sum of all 6 would be $ge 15$.
So there are at most 2 numbers $ge 4$, i.e. there are at least 4 numbers $le 2$.
If any of those four numbers is $1$, there is a subset ${1,2}$ or ${1,1,1}$ which sums to $3$.
Therefore, there are at least $4$ numbers equal to $2$, and the other numbers are all $ge 4$.
But that is impossible, because if all six numbers are equal to $2$ the sum is $12$, and if four or five are equal to 2 the sum is $ge 13$.
add a comment |
up vote
0
down vote
up vote
0
down vote
The set cannot contain the number 3.
Now consider how many of the numbers can be $ge 4$. Clearly there can not be more than three of them, or the sum would be $ge 13$. There can not be three either, because the sum of the other three numbers would be $ge 3$ and the sum of all 6 would be $ge 15$.
So there are at most 2 numbers $ge 4$, i.e. there are at least 4 numbers $le 2$.
If any of those four numbers is $1$, there is a subset ${1,2}$ or ${1,1,1}$ which sums to $3$.
Therefore, there are at least $4$ numbers equal to $2$, and the other numbers are all $ge 4$.
But that is impossible, because if all six numbers are equal to $2$ the sum is $12$, and if four or five are equal to 2 the sum is $ge 13$.
The set cannot contain the number 3.
Now consider how many of the numbers can be $ge 4$. Clearly there can not be more than three of them, or the sum would be $ge 13$. There can not be three either, because the sum of the other three numbers would be $ge 3$ and the sum of all 6 would be $ge 15$.
So there are at most 2 numbers $ge 4$, i.e. there are at least 4 numbers $le 2$.
If any of those four numbers is $1$, there is a subset ${1,2}$ or ${1,1,1}$ which sums to $3$.
Therefore, there are at least $4$ numbers equal to $2$, and the other numbers are all $ge 4$.
But that is impossible, because if all six numbers are equal to $2$ the sum is $12$, and if four or five are equal to 2 the sum is $ge 13$.
answered Nov 23 at 16:56
alephzero
63137
63137
add a comment |
add a comment |
up vote
0
down vote
Represent the problem in the following manner.
You have 6 pigeonholes (representing each integer) and 13 pigeons (the total sum). Each hole must have at least one pigeon for the integers to be positive, so you can equivalently consider a problem with 6 pigeonholes and 7 pigeons (with some holes possibly having zero pigeons). Hey, that's kinda familiar...
By PHP, in the equivalent problem at least one hole must have 2 pigeons. Further, that hole can't have exactly 2 (since that'd represent 3 as a number), so it has to have at least 3.
The rest is left as an exercise for the reader.
Hint: is another hole is forced to have an exact number of pigeons now?
add a comment |
up vote
0
down vote
Represent the problem in the following manner.
You have 6 pigeonholes (representing each integer) and 13 pigeons (the total sum). Each hole must have at least one pigeon for the integers to be positive, so you can equivalently consider a problem with 6 pigeonholes and 7 pigeons (with some holes possibly having zero pigeons). Hey, that's kinda familiar...
By PHP, in the equivalent problem at least one hole must have 2 pigeons. Further, that hole can't have exactly 2 (since that'd represent 3 as a number), so it has to have at least 3.
The rest is left as an exercise for the reader.
Hint: is another hole is forced to have an exact number of pigeons now?
add a comment |
up vote
0
down vote
up vote
0
down vote
Represent the problem in the following manner.
You have 6 pigeonholes (representing each integer) and 13 pigeons (the total sum). Each hole must have at least one pigeon for the integers to be positive, so you can equivalently consider a problem with 6 pigeonholes and 7 pigeons (with some holes possibly having zero pigeons). Hey, that's kinda familiar...
By PHP, in the equivalent problem at least one hole must have 2 pigeons. Further, that hole can't have exactly 2 (since that'd represent 3 as a number), so it has to have at least 3.
The rest is left as an exercise for the reader.
Hint: is another hole is forced to have an exact number of pigeons now?
Represent the problem in the following manner.
You have 6 pigeonholes (representing each integer) and 13 pigeons (the total sum). Each hole must have at least one pigeon for the integers to be positive, so you can equivalently consider a problem with 6 pigeonholes and 7 pigeons (with some holes possibly having zero pigeons). Hey, that's kinda familiar...
By PHP, in the equivalent problem at least one hole must have 2 pigeons. Further, that hole can't have exactly 2 (since that'd represent 3 as a number), so it has to have at least 3.
The rest is left as an exercise for the reader.
Hint: is another hole is forced to have an exact number of pigeons now?
answered Nov 23 at 21:20
user619010
1
1
add a comment |
add a comment |
up vote
0
down vote
Note that since the overall sum is odd, you must have at least one odd number in your set (collection) of six. You must also have at least one even number, because the sum of six odd numbers would be even. That cuts down the possibilities quite quickly.
Suppose there were a contradiction.
Amongst odd numbers you can't have $3$ and if you have $1$ you can't have $2$ among the even numbers.
So either your smallest odd number is at least $5$ (and this is the only odd number, since three would take you over total). But then the evens would have to at least $10$ (five twos is the minimum) ...
Or you have at least one $1$. You can't have three ones, and you can have at most three odd (since only two can be less than $5$ and five odds would have to include three greater than $4$). The lowest total for evens, given there are no $2$s in this case, would be at least three fours = $12$, and you can't fit six in here either.
So neither case is possible, and there must be a sum of $3$.
add a comment |
up vote
0
down vote
Note that since the overall sum is odd, you must have at least one odd number in your set (collection) of six. You must also have at least one even number, because the sum of six odd numbers would be even. That cuts down the possibilities quite quickly.
Suppose there were a contradiction.
Amongst odd numbers you can't have $3$ and if you have $1$ you can't have $2$ among the even numbers.
So either your smallest odd number is at least $5$ (and this is the only odd number, since three would take you over total). But then the evens would have to at least $10$ (five twos is the minimum) ...
Or you have at least one $1$. You can't have three ones, and you can have at most three odd (since only two can be less than $5$ and five odds would have to include three greater than $4$). The lowest total for evens, given there are no $2$s in this case, would be at least three fours = $12$, and you can't fit six in here either.
So neither case is possible, and there must be a sum of $3$.
add a comment |
up vote
0
down vote
up vote
0
down vote
Note that since the overall sum is odd, you must have at least one odd number in your set (collection) of six. You must also have at least one even number, because the sum of six odd numbers would be even. That cuts down the possibilities quite quickly.
Suppose there were a contradiction.
Amongst odd numbers you can't have $3$ and if you have $1$ you can't have $2$ among the even numbers.
So either your smallest odd number is at least $5$ (and this is the only odd number, since three would take you over total). But then the evens would have to at least $10$ (five twos is the minimum) ...
Or you have at least one $1$. You can't have three ones, and you can have at most three odd (since only two can be less than $5$ and five odds would have to include three greater than $4$). The lowest total for evens, given there are no $2$s in this case, would be at least three fours = $12$, and you can't fit six in here either.
So neither case is possible, and there must be a sum of $3$.
Note that since the overall sum is odd, you must have at least one odd number in your set (collection) of six. You must also have at least one even number, because the sum of six odd numbers would be even. That cuts down the possibilities quite quickly.
Suppose there were a contradiction.
Amongst odd numbers you can't have $3$ and if you have $1$ you can't have $2$ among the even numbers.
So either your smallest odd number is at least $5$ (and this is the only odd number, since three would take you over total). But then the evens would have to at least $10$ (five twos is the minimum) ...
Or you have at least one $1$. You can't have three ones, and you can have at most three odd (since only two can be less than $5$ and five odds would have to include three greater than $4$). The lowest total for evens, given there are no $2$s in this case, would be at least three fours = $12$, and you can't fit six in here either.
So neither case is possible, and there must be a sum of $3$.
answered Nov 24 at 3:01
Mark Bennet
80.1k981179
80.1k981179
add a comment |
add a comment |
Can you show your work? You will get better help.
– tarit goswami
Nov 23 at 13:06
The question specifically asks for the use of Pigeon hole principle. Since each of the six numbers is not distinct, and a subset need not be of consecutive numbers, I couldn't really apply the principle. So far, I have established that there are 63 non-empty subsets, the sum of each of which lies between 1 and 13. Therefore, at least 5 subsets have the same sum. Removing the common elements from any two, we can get a pair of disjoint sets. But the problem is still not solved.
– Divyansh Hardia
Nov 23 at 14:10
1
There are no sets of positive integers with six members whose sum is 13. (The elements of a set are distinct by definition.)
– David Hartley
Nov 23 at 17:36
Please consider identical elements.
– Divyansh Hardia
Nov 23 at 19:08