Pigeonhole principle and finding the total ways for this

Question

The question is:

Given any $7$ positive integers whose sum is $100$, show there are $3$ of the numbers whose sum is at least $43$.

So I'm having trouble identifying the pigeonholes. However, I think I know the pigeons: the total number of solutions $\{x_1,x_2,\ldots,x_7\}$ of the equation $$x_1 + x_2 + \ldots + x_7 = 100$$ where $x_k\geq 1$ for all $k=1,2,\ldots,7$.

This looks like a partitioning problem (since it says "any $7$ positive integers", so $1 + 1 + 1 + 1 + 1 + 1 + 94 = 100$ is the same as
$94 + 1 + 1 + 1 + 1 + 1 + 1 = 100$),
so I'm not sure if I interpreted it correctly.

Answer 1

Reworded to work with pigeons and pigeonholes, this question is asking: "Say you have 100 pigeons and you wished to stuff them in $7$ [pigeon]holes. Show that there must be some set of $3$ holes such that there are at least $43$ pigeons in them."

We can start by attempting to evenly distribute the pigeons into the holes, with $14$ per hole and $2$ left over. Since all possible sets of $3$ pigeonholes have only $42$ pigeons in them, when we add the $2$ leftover pigeons, there must be at least one set of $3$ pigeonholes that have at least $43$ pigeons (at least one pigeonhole will have $15$, plus $2$ others of $14$).

Answer 2

Divide the given values into 3 sets, two of three elements and one with a single element. Note that at least one of the given elements is less than or equal to 14. Suppose the set with only one member contains this value. Thus, the sum of the two sets of 3 members is greater than or equal to 86. In fact, at least one of the two groups had a sum of their members greater or equal (in the case of both have the same sum) than 43.

Answer 3

Suppose otherwise. Then for all triples $(x_i,x_j,x_k)$ you have $x_i+x_j+x_k\leq 42$.

Let us add all possible triples together: $(x_1+x_2+x_3)+(x_1+x_2+x_4)+\dots+(x_5+x_6+x_7)$

There are $\binom{7}{3}$ triples so as each triple adds to at most $42$ we can bound the overall sum above by $42\binom{7}{3}$.

Each $x_i$ occurs in the overall sum a total of $\binom{6}{2}$ times, so we may simplify the sum as $\binom{6}{2}x_1+\binom{6}{2}x_2+\dots+\binom{6}{2}x_7$ which as $x_1+x_2+\dots+x_7=100$ simplifies further as $100\binom{6}{2}$

So, we would have $1500=100\binom{6}{2}\leq 42\binom{7}{3}=1470$, a contradiction.

Answer 4

Let arrange the addends with the sum 100 into an non-descending order: $x_1\le x_2\le\dots x_7$.
Let there are only 2 pigeonholes:

1. The 1st one for the first 4 (the lowest) addends.
2. The 2nd one for the last 3 (the highest) addends.

At least in one of them is at least 43 pigeons.

---

If it is the 2nd pinhole, the proof is finished (3 addends with the sum at least 43).

---

If it is not the 2nd pinhole, it must be the 1st pinhole. Let use the pigeonhole principle again.
Now we have:

• at least 58 pigeons (because in the 2nd pinhole is now at most 42), and
• 4 addends (pinholes).

The last addend of them (the greatest one) must have the value at least 15.
So the all 3 consequent elements of the original, 7-element's non-descending sequence must have value at least 15, too - so their sum is at least 45, which is in the contradiction with the assumption of this case.