Pigeon hole principle: Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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?

Answer 6

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