7 fishermen caught exactly 100 fish and no two had caught the same number of fish. Then there are three who have together captured at least 50 fish.

Question

$7$ fishermen caught exactly $100$ fish and no two had caught the same number of fish. Prove that there are three fishermen who have captured together at least $50$ fish.

---

Try: Suppose $k$th fisher caught $r_k$ fishes and that we have $$r_1<r_2<r_3<r_4<r_5<r_6<r_7$$ and let $r(ijk) := r_i+r_j+r_k$. Now suppose $r(ijk)<49$ for all triples $\{i,j,k\}$. Then we have $$r(123)<r(124)<r(125)<r(345)<r(367)<r(467)<r(567)\leq 49$$ so $$300\leq 3(r_1+\cdots+r_7)\leq 49+48+47+46+45+44+43= 322$$

and no contradiction. Any idea how to resolve this?

Edit: Actually we have from $r(5,6,7)\leq 49$ that $r(4,6,7)\leq 48$ and $r(3,6,7)\leq 47$ and then $r(3,4,5)\leq r(3,6,7) - 4 \leq 43$ and $r(1,2,5)\leq r(3,4,5)-4\leq 39$ and $r(1,2,4)\leq 38$ and $r(1,2,3)\leq 37$ so we have:

$$300\leq 49+48+47+43+39+38+37= 301$$ but again no contradiction.

Answer 1

Let's work with the lowest four numbers instead of the other suggestions.

Supposing there is a counterexample, then the lowest four must add to at least $51$ (else the highest three add to $50$ or more).

Since $14+13+12+11=50$ the lowest four numbers would have to include one number at least equal to $15$ to get a total as big as $51$.

Then the greatest three numbers must be at least $16+17+18=51$, which is a contradiction to the assumption that there exists a counterexample.

The examples $18+17+15+14+13+12+11=100$ and $19+16+15+14+13+12+11=100$ show that the bound is tight.

Answer 2

If the maximum number of fish caught is $m$, then the total number of fish caught is no more than $m+(m-1)+...+(m-6)$. So there is one fisherman that caught at least 18 fish. Repeat this process for the second and third highest number of fish caught and you should be good.

I should add that this is a common proof technique in combinatorics and graph theory. To show that something with a certain property exists, choose the "extremal" such something, and prove that property holds for the extremal object. For instance, to show in a graph where each vertex has degree at least $d$ there is a path of length at least $d$, and one proof starts by simply showing a maximal path has length at least $d$.

Answer 3

I think I have a solution. First note that if $r_4 \geq 15$ then we have:

$r_5 \geq 16$

$r_6 \geq 17$

$r_8 \geq 18$

so $r_5 + r_6 + r_7 \geq 16 + 17 +18 = 51$ which is impossible.

Therefore $r_4 < 15$

Also note that if $r_4 \leq 14$ then:

$r_3 \leq 13$

$r_2 \leq 12$

$r_1 \leq 11$

thus $r_1 + r_2 + r_3 + r_4 \leq 50$ which implies that $r_5 + r_6 + r_7 \geq 50$ so that cannot be. Thus we have $r_4 > 15$ which is a contradiction.

Answer 4

Suppose Not means no $3$ fishers have more than $49$

$\implies r_5+r_6+r_7 ≤ 49$

$\implies r_5 ≤ 15$

$\implies r_5$ can not be more than $15$ if it was $16$ or above then the $r_5+r_6+r_7≥ 16+17+18=51$ and that will contradict the first assumption that $r_5+r_6+r_7 ≤ 49$

Therefore $r_5 ≤ 15$

But $r_1<r_2<r_3<r_4<r_5<r_6<r_7$

mean $r_4 ≤14$ & $r_3 ≤13$ & $r_2 ≤12$ & $r_1 ≤11$

$\implies r_1 + r_2 + r_3 + r_4 ≤ 11 + 12 + 13 + 14$

$\implies r_1 + r_2 + r_3 + r_4 ≤ 50$

$\implies (r_1 + r_2 + r_3 + r_4) + (r_5 + r_6 + r_7) ≤ 50 + 49 < 100$ (Contradiction)

Therefore at least 3 fishermen together caught 50 fishes or more

Answer 5

Minimizing the problem:

$7$ dwarfs with tiny buckets - a bucket can not contain more than $7$ fish - go fishing.
As dwarfs have a strict hierarchy, no two of them may catch the same number of fish.
At evening they return with $1+2+3+4+5+6+7 = 28$ fish.

Dwarfs are quite hungry, so the next day they use their larger $10+7$-fish-buckets,
and they return with $11+12+13+14+15+16+17 = 98$ fish.

On their way home they find $2$ more fish. After a short battle they agree that those $2$ fish go to the dwarfs which were most successful, thus maintaining the hierarchy:

$11+12+13+14+15+17+18 = 100$ fish

The most fishy dwarfs caught (at least) $15+17+18 = 50$ fish

Answer 6

a = 0 b = 1 c = 2 d = 3 e = 4 f = 6 g = 84 In other words no mathematical solution to this riddle since there are many possible answers

Answer 7

Ah OK - The title of this riddle is not the same as the riddle itself

7 fishermen caught exactly 100 fish and no two had caught the same number of fish. Then there are three who have together captured at least 50 fish.

and -

7 fishermen caught exactly 100 fish and no two had caught the same number of fish. Prove that there are three who have captured together at least 50

• are two different puzzles. The answer to the second puzzle is simply to take the average catch (doesn't matter that it's not a whole number) and multiply by three. If the answer is more than 50 then you've proved it's impossible for 7 fishermen to have caught 100 fish together without the three biggest catches totalling more than 50. That is however not the case. The average catch would be $14.28, 3 * 14.28 = 42.85$ - therefore it is possible for 7 fishermen to catch 100 fish without any three topping 50. e.g. two fishermen catch 15 each and five catch 14.

Answer 8

I use a simple not so mathematical approach and simple logic. If 7 fisherman catch 100 fish combined but no 2 catch the same number of fish, I would start by solving the first part and then tweaking the numbers to satisfy the 2nd.

Part 1: The average # of fish caught per fisherman is $100/7 = 14.3.$ However, I am assuming fractional fish are not allowed so let's round to 14. $7*14=98$.

Part 2: I will use 14 as the midpoint and since there are an odd number of fishermen, we can say $11,12,13,14,15,16,17$ is a way to get 98 total fish caught such that no 2 fishermen caught the same # of fish. However we are 2 short so we just bump up the 16 to 18 so we now have $11,12,13,14,15,17,18$ which has the top 3 catchers at 50 fish combined. Deviating father away from the average of 14, such as if we had made the lowest fish catcher at 10 instead of 11, will only make the top 3 catchers even higher than 50 cuz then we would have one less total fish at the lower end which would have to be made up at the upper end since there are no "gaps" in the "middle". For example, 10,12,13,14,15,16,20. Now the top 3 catchers have 51 instead of 50. This pattern will continue. There is no way around it.

Answer 9

$11+..+17 = 98$. To reach $100$ and keep distinct, can only add $2$ to the largest two numbers, making the largest $3$ numbers add to $15+16+17+2 = 50$.

Answer 10

Suppose the values are:

r1 r2 r3 r4 r5 r6 r7

are the catches, starting from the lowest r1 to the greatest r7.

r1<r2<r3<r4<r5<r6<r7

You have 100 fish total, so derive the equation:

r1 + r2 + r3 + r4 + r5 + r6 + r7 = 100   (1)

Since r1-r7 are different integers, derive the inequalities:

    r1 ≤ r2 - 1      or (2) r2 ≥ r1 + 1
    r2 ≤ r3 - 1            r3 ≥ r2 + 1
    r3 ≤ r4 - 1            r4 ≥ r3 + 1
    r4 ≤ r5 - 1            r5 ≥ r4 + 1
    r5 ≤ r6 - 1            r6 ≥ r5 + 1
    r6 ≤ r7 - 1            r7 ≥ r6 + 1

Step one: Combine the inequalities 2(by adding their parts) to get r7 on the left part:

(3)  Add all of them
    r2 + r3 + r4 + r5 + r6 + r7 ≥ r1 + r2 + r3 + r4 + r5 + r6 + 6 
    -> r7 ≥ r1 + 6
    add the last 5
    r3 + r4 + r5 + r6 + r7 ≥ r2 + r3 + r4 + r5 + r6 + 5
    -> r7 ≥ r2 + 5
    add the last 4
    r4 + r5 + r6 + r7 ≥ r3 + r4 + r5 + r6 + 4
    -> r7 ≥ r3 + 4
    add the last 3
    r5 + r6 + r7 ≥ r4 + r5 + r6 + 4
    -> r7 ≥ r4 + 3
    add the last 2
    r6 + r7 ≥ r5 + r6 + 4
    -> r7 ≥ r5 + 2
    Use the last one as is:
    r7 ≥ r6 + 1

You can combine the equation 1 with the inequalities 3, by adding them, left parts and right parts separately:

r1 + r2 + r3 + r4 + r5 + r6 + r7 + 6r7 ≥ 100 + r1 + 6 + r2 + 5 + r3 + 4 + r4 + 3 + r5 + 2 + r6 + 1
->  7r7 ≥ 121
->  r7 ≥ 17,28

Since r7 is an integer, this means r7 ≥ 18. (4)

Step 2: Combine the inequalities 2(by adding their parts) to get r6 on the left part:

Add the first 5
    r2 + r3 + r4 + r5 + r6 ≥ r1 + r2 + r3 + r4 + r5 + 5 
    -> r6 ≥ r1 + 5
Add the 2nd to 5th:
r3 + r4 + r5 + r6 ≥ r2 + r3 + r4 + r5 + 4
    -> r6 ≥ r2 + 4
Add the 3rd to 5th:
r4 + r5 + r6 ≥ r3 + r4 + r5 + 3
    -> r6 ≥ r3 + 3
Add the 4th to 5th:
r5 + r6 ≥ r4 + r5 + 2
    -> r6 ≥ r4 + 2
Keep the 5th as is:
    r6 ≥ r5 + 1

Combine equation 1 with these inequalities:

r1 + r2 + r3 + r4 + r5 + r6 + 5r6 + r7 ≥ 100 + r1 + 5 + r2 + 4 + r3 + 3 + r4 + 2 + r5 + 1
->   6r6 + r7 ≥ 115   (5)

From step 1, we got

r7 ≥ 18
->  5r7 ≥ 90    (6)

Combining inequalities 5 & 6:

6r6 + r7 + 5rt7 ≥ 115 + 90
6(r6 + r7) ≥ 205
r6 + r7 ≥ 34,16

So r6 + r7 ≥ 35 (7)

Step 3 Combine the inequalities 2 to get r5 on the left part:

Add the first 4
    r2 + r3 + r4 + r5 ≥ r1 + r2 + r3 + r4 + 4
    -> r5 ≥ r1 + 4
Add the 2nd to 4th:
r3 + r4 + r5 ≥ r2 + r3 + r4 + 3
    -> r5 ≥ r2 + 3
Add the 3rd to 5th:
r4 + r5 ≥ r3 + r4 + 2
    -> r5 ≥ r3 + 2
Keep the 4th as is:
    r5 ≥ r4 + 1

Combine equation 1 with the above 4 inequalities:

r1 + r2 + r3 + r4 + r5 + r6 + r7 + 4r5 ≥ 100 + r1 + 4 + r2 + 3 + r3 + 2 + r4 + 1
->   5r5 + r6 + r7 ≥ 110   (8)

From step 2, we got the inequality 7:

r6 + r7 ≥ 35
->  4(r6 + r7) ≥ 140    (9)

Finally combine inequalities 8 & 9:

5r5 + r6 + r7 + 4(r6 + r7) ≥ 110 + 140
->  5(r5 + r6 + r7) ≥ 250
->  r5 + r6 + r7 ≥ 50   (10)

So this last inequality 10 proves that the sum of the 3 greatest "catches" will be at least 50.

Answer 11

Let me present still another approach, which actually expands on @Vlad 's answer.

Let's arrange, like you did, the seven people according to the captured amounts $$ \left\{ \matrix{ r_{\,1} < r_{\,2} < \cdots < r_{\,7} \hfill \cr r_{\,1} + r_{\,2} + \cdots + r_{\,7} = 100 \hfill \cr} \right. $$

Each fisherman so ranked shall have at least one fish more than the one preceding him.
This difference bias amounts to $0+1+\cdots+6= 21 fishes$.
Take out the bias from each of them, so that we can write $$ \left\{ \matrix{ r'_{\,1} \le r'_{\,2} \le \cdots \le r'_{\,7} \hfill \cr r'_{\,1} + r'_{\,2} + \cdots + r'_{\,7} = 79 \hfill \cr} \right. $$ i.e.: they can have also the same unbiased amount of fishes, and some in the first positions even nothing.

Now let's associate to this the sequence of the progressive sums $$ \left\{ \matrix{ s'_{\,0} = 0,\;\;s'_{\,j} = \sum\limits_{1\, \le \,j\, \le \,7} {r'_{\,j} } \hfill \cr 0 = s'_{\,0} \le s'_{\,1} \le \cdots \le s'_{\,7} = 79 \hfill \cr} \right. $$ Thus clearly the graph of the progressive sums can reach at most the straight line $(0,0),\;(7,79)$ or remain below that.
The straight line is reached when the $r'$ are all equal.

That means that $$ s'_{\,4} \le \left\lfloor {{4 \over 7}79} \right\rfloor = 45 $$ But $45$ is not divisible by $4$; the extra fish cannot be given to $r'_{\,4}$ because that will make it greater than $r'_{\,5}$ and shall be assigned to the last group which will have $2$ extra fishes besides the $11$ flatly assigned to all the seven.

Since $6$ of the biased fishes were deducted from the first four, then we conclude that $$ s_{\,4} \le 50 $$ which demonstrates the thesis.