Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [closed]

Question

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142.

But I don't know what next. Any help would be appreciated

Answer 1

Suppose that any $3$ chosen people have at most a total age of $141$. Then, $x_1 + x_2 + x_3 \le 141$ and so is $x_4 + x_5 + x_6$. This indicates that $x_7 \ge 50$.

Repeating the same process exchanging the roles of $x_i$'s yields $x_i \ge 50$ for any $i$. Which leads to a contradiction.

Answer 2

You can form $\binom{7}{3}$ triplets, i.e. 35 triplets. Every men participates in $\binom{6}{2}$ triplets, i.e 15. So the sum of all 35 triplets is $15 \times 332 = 4980$, which means the average is $\frac{4980}{35} = 142.427...$ so there has to be at least one triplet with total age of at least 142. Actually since all years are integers this proves that there has to be a triplet with total sum of at least 143.

Answer 3

Assume $x_1\le x_2\le\ldots\le x_7$. Here's a proof that $x_5+x_6+x_7\ge144$ (which answers an observation made by TonyK in comments).

Suppose $x_5+x_6+x_7\le143$. Then $x_1+x_2+x_3+x_4\ge332-143=189$, which implies $x_4\ge189/4=47.25$. Since the ages are assumed to be integers, we have $48\le x_4\le x_5\le x_6\le x_7$, which contradicts the supposition.

Answer 4

I find the complexity of the methods shown here to be strange. There is a much simpler solution. $332$ years divided among $7$ people works out to be a little more than $47$ years per person. Specifically, because $7 \cdot 47 = 329$, there are three extra years. So the most even distribution of ages is:

$$47,47,47,47,48,48,48.$$

Obviously, there is a group of three whose ages add up to at least $142$ (in fact, it is $144$). Further note that any time you take a year from someone, you must give it to someone else to keep the sum constant. Taking a year from an older person just redistributes the years and taking a year from a younger person does not help in trying to get a lower sum.

To elaborate on this, you can do one of four redistributions at the beginning: from a $47$ to a $47$, from a $47$ to a $48$, from a $48$ to a $47$, and from a $48$ to a $48$. After these, the outcomes (when sorted again) will be:

$$46,47,47,48,48,48,48$$ $$46,47,47,47,48,48,49$$ $$47,47,47,47,48,48,48$$ $$47,47,47,47,47,48,49$$

As you can see, in every case, the three greatest ages have a sum that is at least $3 \cdot 48 = 144$. Now note that the next time you take a year from someone and give it to someone else, if the first person is older, then you will get one of the five configurations seen already. The only way to get a configuration not seen before is to take a year from a younger person, and this will never lower the sum of the ages of the three oldest people.

To look at it another way, if every person was $47$ years old, then every triple of persons has an age sum of $141$. The instant you give anyone an extra year, there is a triple with an age sum of $142$. Adding two more extra years doesn't help.

Answer 5

The average of the age sum over all possible triples is three times the average age per person (since each person occurs the same number of times). Since the average age per person is above $142\,/\,3$, the average age sum per triple is above $142$, so at least one triple must have age sum at least $142$.

Answer 6

The "strong form" of the Pigeonhole Principle can be stated as follows:

Put $n$ discrete objects into $k$ boxes. Then at least one of the boxes contains $\lceil n/k \rceil$ or more objects.

The notation $\lceil \cdot \rceil$ denotes the "ceiling" function, that is, $\lceil n/k \rceil$ is $n/k$ rounded up to the least integer that is greater than or equal to $n/k$.

We have $7$ people and $332$ years of life that are distributed among those people in whole numbers of years. Set $n = 332$ and $k = 7$ and apply the Pigeonhole Principle. There is at least one person in the group who is age $\lceil n/k \rceil$ or older. But

$$\left\lceil \frac nk \right\rceil = \left\lceil \frac{332}{7} \right\rceil = \left\lceil 47 + \frac37 \right\rceil = 48.$$

So we can find at least one person in the group whose age is at least $48$ years. Select such a person; let that person's age be $x_1$. Then $$x_1 \geq 48. \tag 1$$

Now consider the remaining people in the group. There are $6$of them, and their total number of years of age is $332 - x_1$. Apply the Pigeonhole Principle again, but this time with $n = 332 - x_1$ and $k=6$:

$$\left\lceil \frac{332 - x_1}{6} \right\rceil = \left\lceil 55 + \frac13 - \frac{x_1}{6} \right\rceil.$$

There is at least one person among the remaining six who has lived at least that many years. Choose one such person, and let $x_2$ be their age. We then know that $x_2 \geq \left\lceil 55 + \frac13 - \frac{x_1}{6} \right\rceil$. We can't write a simple number (like $48$) on the right-hand side of this expression, but we do know that $x_2$ is an integer and that $$ x_2 \geq 55 + \frac13 - \frac{x_1}{6},$$ because the ceiling function always produces a number at least as large as the number you put into it. This implies that $$ x_2 + \frac16 x_1 \geq 55 + \frac13. \tag 2$$

Now consider the five remaining people not yet chosen. Apply the Pigeonhole Principle again with $n = 332 - x_1 - x_2$ and $k = 5$:

$$\left\lceil \frac{332 - x_1 - x_2}{5} \right\rceil = \left\lceil 66 + \frac25 - \frac{x_1 + x_2}{5} \right\rceil.$$

At least one of the remaining five poeple has at least this number of years of age. Let that person's age be $x_3$. Then $$x_3 \geq \left\lceil 66 + \frac25 - \frac{x_1 + x_2}{5} \right\rceil,$$ and (following the same methods applied to $x_2$) this implies that $$x_3 + \frac15(x_1 + x_2) \geq 66 + \frac25. \tag 3$$

Now what can we say about $x_1 + x_2 + x_3$? We do not have any expressions $x_2 \geq p$ or $x_3 \geq q$ where $p$ and $q$ are known quantities, but we do have such an expression with $x_3 + \frac15(x_1 + x_2)$ on the left-hand side. So let's try writing \begin{align} x_1 + x_2 + x_3 & = x_1 + x_2 + \left(x_3 + \frac15(x_1 + x_2)\right) - \frac15(x_1 + x_2) \\ & = \frac45 x_1 + \frac45 x_2 + \left(x_3 + \frac15(x_1 + x_2)\right). \end{align} Now replace the first $x_2$ with the equal quantity $\left(x_2 + \frac16 x_1\right) - \frac16 x_1$. \begin{align} x_1 + x_2 + x_3 & = \frac45 x_1 + \frac45 x_2 + \left(x_3 + \frac15(x_1 + x_2)\right) \\ & = \frac45 x_1 + \frac45 \left(\left(x_2 + \frac16 x_1\right) - \frac16 x_1 \right) + \left(x_3 + \frac15(x_1 + x_2)\right) \\ & = \frac45 x_1 + \frac45 \left(x_2 + \frac16 x_1\right) - \frac{2}{15} x_1 + \left(x_3 + \frac15(x_1 + x_2)\right) \\ & = \frac23 x_1 + \frac45 \left(x_2 + \frac16 x_1\right) + \left(x_3 + \frac15(x_1 + x_2)\right) \\ \end{align}

Now apply the inequalities $(1)$, $(2)$, and $(3)$ that we found previously. Be prepared for a pleasant surprise.

Answer 7

Proof by contradiction :

Suppose that it is impossible to find 3 such numbers. Then for every triplet $ x_{i}, x_{j}, x_{k} \in \{x_{1}, ... , x_{7}\}, x_{i} + x_{j} + x_{k} < 142 $.

Thus we have $ \sum_{i=1}^{7} x_{i} < 142 + \sum_{i=4}^{7} x_{i} $ $(*)$

But we also have $ \sum_{k=4,k \ne j }^{7} x_{k} < 142, \forall j \in \{4,5,6,7\} $.

Summing these for all $j \in \{4,5,6,7\} $ we get $ 3 * (\sum_{i=4}^{7} x_{i}) < 4*142 $ and then $ (\sum_{i=4}^{7} x_{i}) < \frac{4}{3}*142 = 189.333 .. < 190 $ .

Replacing this in $(*)$ we get $ \sum_{i=1}^{7} x_{i} < 190 + 142 = 332 $, which is a contradiction.

Answer 8

Proof by contradiction. Given $\sum_{i=1}^{7} x_i = 332$, assume that we cannot pick three people whose ages sum to at least 142. This means that for all $i$, $j$, $k \in [1, 7]$ with $i \ne j$, $j \ne k$, and $i \ne k$, $x_i + x_j + x_k < 142$. With these two assumptions,

1. $x_1 + x_2 + x_3 < 142$ and $x_4 + x_5 + x_6 < 142$ implies $x_7 > 48$.

2. $x_1 + x_2 + x_3 < 142$ and $x_5 + x_6 + x_7 < 142$ implies $x_4 > 48$.

3. $x_2 + x_3 + x_4 < 142$ and $x_5 + x_6 + x_7 < 142$ implies $x_1 > 48$.

But $x_1 + x_4 + x_7 > 3 \times 48 = 144 > 142$, which contradicts the assumption that for all $i$, $j$, $k$ with $i \ne j$, $j \ne k$, and $i \ne k$, $x_i + x_j + x_k < 142$. There there exists at least one combination of $i, j, k \in [1, 7]$ with $i \ne j$, $j \ne k$, and $i \ne k$, $x_i + x_j + x_k > 142$.

Answer 9

Given seven integers with sum $332$, label them such that $x_1 \geq x_2 \geq x_3 \geq x_4 \geq x_5 \geq x_6 \geq x_7$. Proof by decomposition into two cases: $x_3 \geq 48$ and $x_3 \lt 48$.

If $x_3 \geq 48$ then $x_1 + x_2 + x_3 \geq 48 + 48 + 48 = 144$ (by choice of labels). Therefore in this case $x_1 + x_2 + x_3 \gt 142$.

If $x_3 \lt 48$, or rather $x_3 \le 47$, then $x_4 + x_5 + x_6 + x_7 \le 47 + 47 + 47 + 47 = 188$ (by choice of labels). So we have $x_1 + x_2 + x_3 \ge 332 - 188 = 144$, therefore $x_1 + x_2 + x_3 \gt 142$.

Answer 10

Consider all of the three-element subsets of the seven numbers. The average sum of each subset must be 3/7 · 332 ≈ 142.3. If no subset sums to 142 or more, then every subset must be below average, which is impossible.

Answer 11

Proof by contradiction.

If you cannot select 3 elements in the set whose some is bigger or equal 142, for every triplet $ x_{i}, x_{j}, x_{k} \in \{x_{1}, ... , x_{7}\}, x_{i} + x_{j} + x_{k} < 142 $.

This implies:

$ x_{1}, x_{2}, x_{3} < 142 $,

$ x_{1}, x_{2}, x_{4} < 142 $,

..

$ x_{1}, x_{2}, x_{7} < 142 $,

$ x_{2}, x_{3}, x_{4} < 142 $,

.. and so on up to

$ x_{5}, x_{6}, x_{7} < 142 $.

If you sum up all the left and right side of the 35 inequalities (combining triplets in $ \{x_{1}, ... , x_{7}\} $ without repetitions) you will obtain a new inequality

$ 15 \sum_{i=1}^{7} x_{i} < 35 \times 142 $

that can be rewritten as

$ \sum_{i=1}^{7} x_{i} < \frac{35 \times 142}{15} $

i.e.

$ \sum_{i=1}^{7} x_{i} < 331.33$

but this is not possible as the text of the problem states that

$ \sum_{i=1}^{7} x_{i} = 332 $.

So this means that our initial assumption:

$ x_{i}, x_{j}, x_{k} \in \{x_{1}, ... , x_{7}\}, x_{i} + x_{j} + x_{k} < 142 $

is wrong and therefore it should exists at least a triplet whose sum is $ >= 142 $ q.e.d.

Answer 12

You need 7 inequations.

Suppose you can't select three people with the total age at least 142. Then: x1+x2+x3<142 (eq. 1) x2+x3+x4<142 (eq. 2) ... x5+x6+x7<142 (eq. 5) x1+ x6+x7 <142 (eq. 6) x1+x2+ +x7 <142 (eq. 7)

Then 3x1+3x2+....+3x7<7x142 => x1+x2+...+x7<7x142/3<332 =><=

Answer 13

The average integer age of all $7$ is $47$. $3 \times 47 = 141$. However, because $7 \times 47 = 329$, it follows that one person must have an age of $50$ in order for the total to be $332$. Take $2$ average people and the old guy and you have $144$.