Vrftsjtryk

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.

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.

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

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.

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

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?