Pigeon Hole Principle Proof integrated with sets

Question

I saw this EXACT question a couple days ago on this website. There was a hint but no final answer because the post got shut down.

Original Post:Discrete Math and Combinatorics, Proving subset exists under certain conditions

Question: Show that any set of 8 positive integers whose sum is 20 has a subset summing to 4. These 8 positive integers do not have to be distinct.

My "Answer": I was thinking this could be split up into 5 cases: {2, 2}, {1, 3}, {1, 1, 1, 1,}, {4}, {1, 1, 2} are the subsets out of some arbitrary set that satisfy the condition that a subset has to sum to 4 (the other elements in the set just have to make everything sum to 20, does not matter what they are). I don't really know how to integrate Pigeon hole principle into this however. Like what would the holes/pigeons be?

User "N.F. Taussig" gave the hint: Hint: If such a subset does not exist, then 44 cannot be a summand, there can be at most one 22, and you cannot have both 11 and 33. What is the smallest sum you can obtain under these conditions?

Honestly, mathematical proofs like these are not my strong suit at all. I don't really understand the hint the user provided either and would like some clarification on this.

Answer 1

There is a subset with at least $2$ members that sums to $4$. Proof: Suppose not. Then

(i). There can be at most three $1$'s among the members (as $1+1+1+1=4$).. If there are two or three $1$'s there cannot be a $2$ ( as $2+1+1=4$) nor a $3$ (as $3+1=4$) but that leaves at least $5$ other members with a value of $4$ or more, each, and a total sum of at least $5(4)+3(1)>20.$

(ii). If there is one $1$ then there is at most one $2$ (as $2+2=4$) and no $3$'s (as $3+1=4$) leaving at least $6$ members with values of $4$ or more,each, and a total sum greater than $6(4)>20.$

(iii). If there are no $1$'s there is at most one $2$ (as $2+2=4)$ and at least $7$ members with values of $3$ or more, each, for a total sum greater than $7(3)>20.$

Answer 2

"I was thinking this could be split up into 5 cases: "

Advice. To prove something must happen, don't try to figure out how to do it. Try to figure out how NOT to do it and prove it is impossible.

So I want to AVOID having any of them add up to $4$.

The easiest way to do that is to not have any numbers $1,2,3,4$ that might accidently add up to $4$. But if all our numbers are at least $5$ our sum will be at least $8*5 = 40$ which is WAY more than $20$. So we're going to have to have some numbers $1,2,3,4$.

We can have any $4$s (because $4=4$). But what if we only have $3$s? We can add $3$'s till the cows come home and never get $4$. As long as we have no $1$s, we can have threes and be perfectly safe.

But if all our numbers are at least $3$ we get at least $8*3=24 > 20$. That's better than $40$ but still not good enough.

So we need some $1$s and $2$s.

The absolute maximum number of $1$s we can have is three, because if we have four or more, $1+1+1+1=4$.

If we have three $1$ we can't have any $2,3,$ or $4$s, because $1+1+2$ and $1+3 = 4$ (and $4 = 4$). So this wold mean the remaining five numbers are and least $5$ and our sum is at least $1+1+1+5*5 = 28> 0$. Yikes! that's worse.

The same argument if we have two $1$; we can't have any $2,3$ or $4$ and our sum is at least $1+1+6*5=32>0$.

If we have one $1$ we can't have any $3$s or $4$s but we can have one $2$. But only one $2$ as $2+2 = 4$. But then our sum is at least $1+2+6*5= 33> 20$.

If we don't have any $1$s we must have $2$s. And we can't have more than one $2$ because $2+2 = 4$. But now we can have as many $3$s as we like. If we can have only one $2$ and no $1$s, the remaining numbers must be at $3$. So our sum is at least $2 + 7*3 = 23 > 20$.

So we simply can not get a sum less than $23$ if we must have $8$ numbers and no combination of them adds to $4$.