Mixing
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.
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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 $$300leq 3(r_1+cdots+r_7)leq 49+48+47+46+45+44+43= 322$$
and no contradiction. Any idea how to resolve this?
combinatorics contest-math pigeonhole-principle
edited 22 mins ago
Théophile
18k12740
asked 50 mins ago
greedoid
29.9k93980
add a comment |Â
up vote
2
down vote
favorite
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 $$300leq 3(r_1+cdots+r_7)leq 49+48+47+46+45+44+43= 322$$
and no contradiction. Any idea how to resolve this?
combinatorics contest-math pigeonhole-principle
edited 22 mins ago
Théophile
18k12740
asked 50 mins ago
greedoid
29.9k93980
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 $300le 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.
– Kusma
41 mins ago
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.
– Mark Bennet
38 mins ago
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
– TomGrubb
37 mins ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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 $$300leq 3(r_1+cdots+r_7)leq 49+48+47+46+45+44+43= 322$$
and no contradiction. Any idea how to resolve this?
combinatorics contest-math pigeonhole-principle
edited 22 mins ago
Théophile
18k12740
asked 50 mins ago
greedoid
29.9k93980
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 $$300leq 3(r_1+cdots+r_7)leq 49+48+47+46+45+44+43= 322$$
and no contradiction. Any idea how to resolve this?
combinatorics contest-math pigeonhole-principle
combinatorics contest-math pigeonhole-principle
edited 22 mins ago
Théophile
18k12740
asked 50 mins ago
greedoid
29.9k93980
edited 22 mins ago
Théophile
18k12740
asked 50 mins ago
greedoid
29.9k93980
edited 22 mins ago
Théophile
18k12740
edited 22 mins ago
Théophile
18k12740
edited 22 mins ago
Théophile
18k12740
18k12740
asked 50 mins ago
greedoid
29.9k93980
asked 50 mins ago
greedoid
29.9k93980
asked 50 mins ago
greedoid
29.9k93980
29.9k93980
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 $300le 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.
– Kusma
41 mins ago
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.
– Mark Bennet
38 mins ago
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
– TomGrubb
37 mins ago
add a comment |Â
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 $300le 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.
– Kusma
41 mins ago
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.
– Mark Bennet
38 mins ago
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
– TomGrubb
37 mins ago
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 $300le 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.
– Kusma
41 mins ago
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 $300le 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.
– Kusma
41 mins ago
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.
– Mark Bennet
38 mins ago
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.
– Mark Bennet
38 mins ago
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
– TomGrubb
37 mins ago
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
– TomGrubb
37 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Let's work with the lowest four numbers instead of the other suggestions. Suppose 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 he assumption that a counterexample exists.
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.
answered 12 mins ago
Mark Bennet
77.7k775175
Very clean. I always love how the numerology works out on these +1
– TomGrubb
10 mins ago
add a comment |Â
up vote
4
down vote
If the maximum number of fishes caught is $m$, then the total number of fishes 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.
Edit: 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$, one proof starts by simply showing a maximal path has length at least $d$.
answered 38 mins ago
TomGrubb
10.2k11336
1
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$
– Mark Bennet
29 mins ago
@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
– TomGrubb
26 mins ago
Not a problem - it actually gets a bit easier. This works and was my first way of doing it.
– Mark Bennet
15 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Let's work with the lowest four numbers instead of the other suggestions. Suppose 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 he assumption that a counterexample exists.
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.
answered 12 mins ago
Mark Bennet
77.7k775175
Very clean. I always love how the numerology works out on these +1
– TomGrubb
10 mins ago
add a comment |Â
up vote
3
down vote
accepted
Let's work with the lowest four numbers instead of the other suggestions. Suppose 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 he assumption that a counterexample exists.
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.
answered 12 mins ago
Mark Bennet
77.7k775175
Very clean. I always love how the numerology works out on these +1
– TomGrubb
10 mins ago
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Let's work with the lowest four numbers instead of the other suggestions. Suppose 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 he assumption that a counterexample exists.
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.
answered 12 mins ago
Mark Bennet
77.7k775175
Let's work with the lowest four numbers instead of the other suggestions. Suppose 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 he assumption that a counterexample exists.
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.
answered 12 mins ago
Mark Bennet
77.7k775175
answered 12 mins ago
Mark Bennet
77.7k775175
answered 12 mins ago
Mark Bennet
77.7k775175
answered 12 mins ago
Mark Bennet
77.7k775175
77.7k775175
Very clean. I always love how the numerology works out on these +1
– TomGrubb
10 mins ago
add a comment |Â
Very clean. I always love how the numerology works out on these +1
– TomGrubb
10 mins ago
Very clean. I always love how the numerology works out on these +1
– TomGrubb
10 mins ago
Very clean. I always love how the numerology works out on these +1
– TomGrubb
10 mins ago
add a comment |Â
up vote
4
down vote
If the maximum number of fishes caught is $m$, then the total number of fishes 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.
Edit: 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$, one proof starts by simply showing a maximal path has length at least $d$.
answered 38 mins ago
TomGrubb
10.2k11336
1
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$
– Mark Bennet
29 mins ago
@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
– TomGrubb
26 mins ago
Not a problem - it actually gets a bit easier. This works and was my first way of doing it.
– Mark Bennet
15 mins ago
add a comment |Â
up vote
4
down vote
If the maximum number of fishes caught is $m$, then the total number of fishes 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.
Edit: 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$, one proof starts by simply showing a maximal path has length at least $d$.
answered 38 mins ago
TomGrubb
10.2k11336
1
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$
– Mark Bennet
29 mins ago
@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
– TomGrubb
26 mins ago
Not a problem - it actually gets a bit easier. This works and was my first way of doing it.
– Mark Bennet
15 mins ago
add a comment |Â
up vote
4
down vote
up vote
4
down vote
If the maximum number of fishes caught is $m$, then the total number of fishes 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.
Edit: 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$, one proof starts by simply showing a maximal path has length at least $d$.
answered 38 mins ago
TomGrubb
10.2k11336
If the maximum number of fishes caught is $m$, then the total number of fishes 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.
Edit: 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$, one proof starts by simply showing a maximal path has length at least $d$.
answered 38 mins ago
TomGrubb
10.2k11336
edited 28 mins ago
answered 38 mins ago
TomGrubb
10.2k11336
answered 38 mins ago
TomGrubb
10.2k11336
answered 38 mins ago
TomGrubb
10.2k11336
10.2k11336
1
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$
– Mark Bennet
29 mins ago
@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
– TomGrubb
26 mins ago
Not a problem - it actually gets a bit easier. This works and was my first way of doing it.
– Mark Bennet
15 mins ago
add a comment |Â
1
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$
– Mark Bennet
29 mins ago
@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
– TomGrubb
26 mins ago
Not a problem - it actually gets a bit easier. This works and was my first way of doing it.
– Mark Bennet
15 mins ago
1
1
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$
– Mark Bennet
29 mins ago
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$
– Mark Bennet
29 mins ago
@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
– TomGrubb
26 mins ago
@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
– TomGrubb
26 mins ago
Not a problem - it actually gets a bit easier. This works and was my first way of doing it.
– Mark Bennet
15 mins ago
Not a problem - it actually gets a bit easier. This works and was my first way of doing it.
– Mark Bennet
15 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2936741%2f7-fishermen-caught-exactly-100-fish-and-no-two-had-caught-the-same-number-of-fis%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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 $300le 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.
– Kusma
41 mins ago
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.
– Mark Bennet
38 mins ago
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
– TomGrubb
37 mins ago