1
$\begingroup$

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.

$\endgroup$

closed as off-topic by Shaun, Namaste, Paul Frost, Saad, user10354138 Nov 24 '18 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, Namaste, Paul Frost, Saad, user10354138
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Can you show your work? You will get better help. $\endgroup$ – tarit goswami Nov 23 '18 at 13:06
  • $\begingroup$ 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. $\endgroup$ – Divyansh Hardia Nov 23 '18 at 14:10
  • 1
    $\begingroup$ There are no sets of positive integers with six members whose sum is 13. (The elements of a set are distinct by definition.) $\endgroup$ – David Hartley Nov 23 '18 at 17:36
  • $\begingroup$ Please consider identical elements. $\endgroup$ – Divyansh Hardia Nov 23 '18 at 19:08
4
$\begingroup$

Hint. Let $1\leq a_1\leq a_2\leq a_3\leq a_4\leq a_5\leq a_6$. We know that $\sum_{k=1}^n a_k=13$.

Now consider the following cases:

1) If $a_4\geq 4$ then $$10=13-1-1-1\geq 13-a_1-a_2-a_3\\=a_4+a_5+a_6\geq 4\cdot 3=12$$ which is a contradiction.

2) If $a_4=3$ then ...

3) If $a_4\leq 2$ then ...

I don't think that the Pigeonhole principle is strictly necessary here.

$\endgroup$
  • $\begingroup$ I tried to do something similar, but starting with $a_1\ge3$ and $a_1\lt3$. 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? $\endgroup$ – F.Carette Nov 23 '18 at 13:35
  • $\begingroup$ @F.Carette See my edit. Is it quicker? $\endgroup$ – Robert Z Nov 23 '18 at 13:41
  • $\begingroup$ A bit quicker indeed! +1 $\endgroup$ – F.Carette Nov 23 '18 at 13:44
2
$\begingroup$

(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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
-1
$\begingroup$

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$.

$\endgroup$
-1
$\begingroup$

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?

$\endgroup$

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