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