# 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]

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

• As Stefan4024 shows, there must be three people whose ages sum to at least $143$. James claims that there must be three people whose ages sum to at least $144$, but his argument is flawed (see my comment). However, I can't find an example where $143$ is the maximum, so perhaps $144$ is provable. Anybody? Commented Aug 27, 2015 at 12:18
• @TonyK: If the maximum age is $48$, there must be three of those, and they sum to $144$. Else the maximum is $m\ge49$ and the remaining $6$ add up to $332-m$, so the average pair of them has age sum $(332-m)/3$, so there must be at least one pair with age sum $\lceil(332-m)/3\rceil$, and together with the person of maximum age they form a triplet with age sum $m+\lceil(332-m)/3\rceil$. This is minimal for minimal $m$, and for $m=49$ it's $144$. Commented Aug 27, 2015 at 12:45
• "i need to find three of these which sum is 142" -- you simply misread the problem. At least 142, not exactly 142. Commented Aug 27, 2015 at 15:11
• @TonyK, see my answer for another proof with 144 as the bound. Commented Aug 27, 2015 at 15:28
• @TonyK My answer shows the minimum to be $143$ (if you complete the last step, which I "left as an exercise for the reader"). But I like Barry Cipra's answer a lot better. While Stefan4024 also got just $143$, I like his method better than mine, too. Commented Aug 27, 2015 at 20:06

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.

• Small correction: You can only conclude that $x_i \ge 332 - 2 \cdot 141 = 50$. Commented Aug 27, 2015 at 10:51

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.

• Last sentence - unless I've missed the point, doesn't it prove that there has to be a triplet with a total sum of at least 143 (rather than 143 exactly)? For instance, all ages might be even. Commented Aug 28, 2015 at 7:54
• @abligh Yes you are right there has to be a triplet with a sum of at least 143, rather than exactly 143. The most simpliest of examples is 326, 1, 1, 1, 1, 1, 1 Commented Aug 28, 2015 at 8:40

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.

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.

• This is in fact a nice idea, but I think one needs a bit more care to elaborate such an "equilibrum" argument to work with several resdistribution steps. At which moment you certainly exceed thet complexity of Barry Cipra's argument. Commented Aug 28, 2015 at 13:34
• @HagenvonEitzen: That's true, greater rigor would mean a little more complexity. However, I see this as one of those things that is intuitively true and simple, which also holds up under deeper analysis. Commented Aug 28, 2015 at 18:05

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

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.

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.

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

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

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.

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.

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 =><=

• $x_1+x_2+x_3<142 \\ x_2+x_3+x_4<142\\ x_3+x_4+x_5<142\\ x_4+x_5+x_6<142\\ x_5+x_6+x_7<142\\ x_6+x_7+x_1<142\\ x_7+x_1+x_2<142\\ \text{Then} \\ 3\cdot x_1+3\cdot x_2+3\cdot x_3+3\cdot x_4+3\cdot x_5+3\cdot x_6+3\cdot x_7<7\cdot 142\\x_1+x_2+x_3+x_4+x_5+x_6+x_7<\dfrac{7\cdot 142}{3}<332\\ \text{Contradiction because}\\x_1+x_2+x_3+x_4+x_5+x_6+x_7\ge 332$ Commented Aug 28, 2015 at 23:23

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

• $4 \times 47 + 3 \times 48 = 332$, so you don't need any 50-year-olds. Commented Aug 27, 2015 at 12:08
• It was only an illustration of what can be argued using only averages - which has to be the simplest method of solving the question. As soon as you drop the age of the ONE old guy, you only increase the number of relatively old guys in relation to the number of young guys. If you choose only the oldest guys to make up your triple, you still can't get less than 144. Commented Aug 27, 2015 at 13:47