52
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You can somewhat refine your approach: you have $r(567)\le 49$, $r(467)\le 48$, $r(367)\le 47$, $r(345)\le 45$ and $r(125)\le 43$, $r(124)\le 42$ and $r(123)\le 41$. Then $300\le 41+42+43+45+47+48+49=315$. And you can probably show not all of these can be maximal, else individual numbers would be equal. $\endgroup$ – Kusma Sep 30 '18 at 15:01
  • $\begingroup$ So the question is that three caught between them at least $50$ fish. And the fact that the constraint doesn't give an immediate solution does not mean that there is a solution - specific numbers have to be allocated. $\endgroup$ – Mark Bennet Sep 30 '18 at 15:04
  • $\begingroup$ Nowhere in the question statement did Greedoid find a contradiction...he never created an actual assignment of fish that did not work, he just tried a reasonable argument that did not pan out $\endgroup$ – TomGrubb Sep 30 '18 at 15:05
  • 8
    $\begingroup$ I am no expert in fishing, but as a mathematician I find it reasonable that the first man caught $13.9$ fish, the second one $14.1$, and each of the others $0.1$ fish more than the preceding man, and we have $$100=13.9+14.1+14.2+14.3+14.4+14.5+14.6.$$ This is a bad joke. $\endgroup$ – Jeppe Stig Nielsen Oct 1 '18 at 22:41
  • 3
    $\begingroup$ @JeppeStigNielsen let's remember that $$ fish \in \mathbb{N} $$ :o) $\endgroup$ – DarkCygnus Oct 2 '18 at 18:58

11 Answers 11

103
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A similar approach works with the largest numbers: then $r_5$ can at most be 15 which forces $r_1+\dots +r_4 \leq 50$. $\endgroup$ – Sebastian Bechtel Sep 30 '18 at 18:36
  • $\begingroup$ Can't one of the seven catch zero fish? Creating two more solutions. $\endgroup$ – Rob Oct 1 '18 at 1:39
  • 2
    $\begingroup$ @Rob You are right that zero is a possibility, but if one catches zero, the other six catch $100$ and even if two could catch the same, they couldn't all catch the same ($100$ is not a multiple of $6$). So the top three would catch more than $50$ and the bottom three would catch fewer. I'm not sure what you mean by a "solution" - but zero cannot be included if the top three catch exactly $50$ fish. $\endgroup$ – Mark Bennet Oct 1 '18 at 7:46
  • $\begingroup$ In your answer you say: "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." --- but 14+13+12+0 = 39 and 29+17+15+14+13+12+0 = 100, with 29+17+15 = 61. None of my solution is excluded by the constraints of the question but are in opposition to what you said in your answer (quoted above). Greedoid required: "... three who have captured together at least 50 fish."; with 7!=, totaling 100. $\endgroup$ – Rob Oct 1 '18 at 11:16
  • 7
    $\begingroup$ @Rob: What problem do you mean that you have found solutions for? The original question asked for a proof, not a solution, and Mark Bennet set out to see what it would take to find a counterexample, which you didn't find. $\endgroup$ – HelloGoodbye Oct 1 '18 at 12:15
26
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ If the most fish caught is $18$ that gives a tight result - there is a little work to check what happens if the largest number of fish caught is greater than $18$ $\endgroup$ – Mark Bennet Sep 30 '18 at 15:12
  • 1
    $\begingroup$ @MarkBennet right, my thought was to iterate, i.e. After you choose the max $m$, replace $100$ with $100-m$ and $7$ fishers with $6$, this gives a bound on the second highest, etc. Thanks for pointing this out $\endgroup$ – TomGrubb Sep 30 '18 at 15:15
  • $\begingroup$ Not a problem - it actually gets a bit easier. This works and was my first way of doing it. $\endgroup$ – Mark Bennet Sep 30 '18 at 15:26
  • 1
    $\begingroup$ Thank you for your solution. I accept Mark's solution because it is more accessible for kinds about 14 years. $\endgroup$ – Maria Mazur Sep 30 '18 at 15:45
  • $\begingroup$ @greedoid no prob! I would accept marks as well :) $\endgroup$ – TomGrubb Sep 30 '18 at 15:45
8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I like it. Could also be written like this: Suppose $r_4\ge 15$ (leads to contradiction). Then suppose $r_4\le 14$ (leads to contradiction). We conclude that $14<r_4<15$ which is absurd. $\endgroup$ – Jeppe Stig Nielsen Oct 1 '18 at 22:56
  • 1
    $\begingroup$ It would, I think, be much better to say simply: if r4≥15 then the conclusion holds; and if r4<15, the conclusion holds. Therefore, since there is (obviously) at least one solution, the conclusion holds. $\endgroup$ – peak Oct 4 '18 at 22:52
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Very good and .. concise(+1). I could fully grasp your answer after having elaborated mine: if you don't mind I would cancel it and put as an addendum to yours, which would be due, since the core idea is yours. $\endgroup$ – G Cab Oct 8 '18 at 21:52
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @greedoid thx for beautifying $\endgroup$ – ack Oct 11 '18 at 9:51
1
$\begingroup$

Suppose Not means no 3 fishers have more than 49

$\implies r5+r6+r7 ≤ 49$

$\implies r5 ≤ 15$

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

Therefore $r5 ≤ 15$

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

mean $r4 ≤14$ & $r3 ≤13$ & $r2 ≤12$ & $r1 ≤11$

$\implies r1 + r2 + r3 + r4 ≤ 11 + 12 + 13 + 14$

$\implies r1 + r2 + r3 + r4 ≤ 50$

$\implies (r1 + r2 + r3 + r4) + (r5 + r6 + r7) ≤ 50 + 49 < 100$ (Contradiction)

Therefore at least 3 fishermen together caught 50 fishes or more

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But the statement is true in all of them $\endgroup$ – asdf Oct 2 '18 at 8:15
  • 1
    $\begingroup$ Even in your answer is AT LEAST one triple ≥ 50 - (a,b,g) $\endgroup$ – ack Oct 2 '18 at 8:19
-2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ sorry - forgot no two catches should be equal $\endgroup$ – Colin Oct 2 '18 at 8:29
  • $\begingroup$ . . which means of course that the four lowest catches under the 14.28 mean would have to able to top 50 to disprove the statement but; 14 + 13 +12 + 11 = 50 precisely proving that the top 3 catches must amount to at least 50. $\endgroup$ – Colin Oct 2 '18 at 8:46

protected by Maria Mazur Mar 22 at 21:21

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.