Mixing
A conference uses $4$ main languages. Prove that there is a language that at least $dfrac{3}{5}$ of the...
$begingroup$
A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $dfrac{3}{5}$ of the delegates know.
Source: Romania TST 2002
My attempt:
Suppose we have $n$ people and that $l_i$ people speak language $L_i$.
We want to prove that $l_i$ is at least $3n/5$ for some $iin{1,2,3,4}$.
Say it is not true. Then we have $l_i<3n/5=:m$ for all $i$.
Because of condition we have
$$ {nchoose 2} leq sum_{i=1}^4{l_ichoose 2} < 4times {mchoose
2}$$ From here we get $11n>35$ and there is no contradiction if
$n>3$.
Update (1.20.2019): I am now trying to develop the idea that was mentioned by Servaes in the commentary.
Lemma: Among any $4$ delegates there are $3$ that speaks the same languague.
Proof: If somebody speaks only one languague we are done. Say there is somenone that speaks exactly 2 languagues $L_1$ and $L_2$. Then by pigeonhole out of 3 there are two in the same "hole" and we are done again.
Suppose that everyone speaks at least 3 languague. Then by double counting between languagues and 4 people we have $$4cdot 3leq 4cdot limplies lgeq 3$$
where $l$ is maximum cardinality of $L_i$ in this double counting and we are done. $square $
Any idea how to finish now?
combinatorics optimization extremal-combinatorics algebraic-combinatorics
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
$endgroup$
add a comment |
$begingroup$
A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $dfrac{3}{5}$ of the delegates know.
Source: Romania TST 2002
My attempt:
Suppose we have $n$ people and that $l_i$ people speak language $L_i$.
We want to prove that $l_i$ is at least $3n/5$ for some $iin{1,2,3,4}$.
Say it is not true. Then we have $l_i<3n/5=:m$ for all $i$.
Because of condition we have
$$ {nchoose 2} leq sum_{i=1}^4{l_ichoose 2} < 4times {mchoose
2}$$ From here we get $11n>35$ and there is no contradiction if
$n>3$.
Update (1.20.2019): I am now trying to develop the idea that was mentioned by Servaes in the commentary.
Lemma: Among any $4$ delegates there are $3$ that speaks the same languague.
Proof: If somebody speaks only one languague we are done. Say there is somenone that speaks exactly 2 languagues $L_1$ and $L_2$. Then by pigeonhole out of 3 there are two in the same "hole" and we are done again.
Suppose that everyone speaks at least 3 languague. Then by double counting between languagues and 4 people we have $$4cdot 3leq 4cdot limplies lgeq 3$$
where $l$ is maximum cardinality of $L_i$ in this double counting and we are done. $square $
Any idea how to finish now?
combinatorics optimization extremal-combinatorics algebraic-combinatorics
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
$endgroup$
$begingroup$
Out of any $5$ delegates, there must be at least $3$ that speak a common language...
$endgroup$
– Servaes
May 15 '18 at 15:34
1
$begingroup$
More background (but not a solution): mathoverflow.net/questions/254012/…
$endgroup$
– vadim123
May 15 '18 at 15:34
$begingroup$
Consider a person who speaks the fewest languages, and let this number be $k$. If $k=1$, then everyone must speak this language. If $k=4$, everyone speaks all four. If $k=2$, there are at least $n/2$ people who speak one of these two languages. So consider the fractions of people who speak exactly ${{1,2,3}$, ${1,2,4}$, ${1,3,4}$ and ${2,3,4}$.
$endgroup$
– Aravind
May 15 '18 at 16:32
$begingroup$
@aravind, I agree with your case analysis for $k=1,4$. How does $k=2$ help? $n/2<3n/5$.
$endgroup$
– vadim123
May 15 '18 at 17:28
add a comment |
$begingroup$
A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $dfrac{3}{5}$ of the delegates know.
Source: Romania TST 2002
My attempt:
Suppose we have $n$ people and that $l_i$ people speak language $L_i$.
We want to prove that $l_i$ is at least $3n/5$ for some $iin{1,2,3,4}$.
Say it is not true. Then we have $l_i<3n/5=:m$ for all $i$.
Because of condition we have
$$ {nchoose 2} leq sum_{i=1}^4{l_ichoose 2} < 4times {mchoose
2}$$ From here we get $11n>35$ and there is no contradiction if
$n>3$.
Update (1.20.2019): I am now trying to develop the idea that was mentioned by Servaes in the commentary.
Lemma: Among any $4$ delegates there are $3$ that speaks the same languague.
Proof: If somebody speaks only one languague we are done. Say there is somenone that speaks exactly 2 languagues $L_1$ and $L_2$. Then by pigeonhole out of 3 there are two in the same "hole" and we are done again.
Suppose that everyone speaks at least 3 languague. Then by double counting between languagues and 4 people we have $$4cdot 3leq 4cdot limplies lgeq 3$$
where $l$ is maximum cardinality of $L_i$ in this double counting and we are done. $square $
Any idea how to finish now?
combinatorics optimization extremal-combinatorics algebraic-combinatorics
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
$endgroup$
A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $dfrac{3}{5}$ of the delegates know.
Source: Romania TST 2002
My attempt:
Suppose we have $n$ people and that $l_i$ people speak language $L_i$.
We want to prove that $l_i$ is at least $3n/5$ for some $iin{1,2,3,4}$.
Say it is not true. Then we have $l_i<3n/5=:m$ for all $i$.
Because of condition we have
$$ {nchoose 2} leq sum_{i=1}^4{l_ichoose 2} < 4times {mchoose
2}$$ From here we get $11n>35$ and there is no contradiction if
$n>3$.
Update (1.20.2019): I am now trying to develop the idea that was mentioned by Servaes in the commentary.
Lemma: Among any $4$ delegates there are $3$ that speaks the same languague.
Proof: If somebody speaks only one languague we are done. Say there is somenone that speaks exactly 2 languagues $L_1$ and $L_2$. Then by pigeonhole out of 3 there are two in the same "hole" and we are done again.
Suppose that everyone speaks at least 3 languague. Then by double counting between languagues and 4 people we have $$4cdot 3leq 4cdot limplies lgeq 3$$
where $l$ is maximum cardinality of $L_i$ in this double counting and we are done. $square $
Any idea how to finish now?
combinatorics optimization extremal-combinatorics algebraic-combinatorics
combinatorics optimization extremal-combinatorics algebraic-combinatorics
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
edited Feb 11 at 11:29
greedoid
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
asked May 15 '18 at 14:40
greedoidgreedoid
45.8k1159116
45.8k1159116
$begingroup$
Out of any $5$ delegates, there must be at least $3$ that speak a common language...
$endgroup$
– Servaes
May 15 '18 at 15:34
1
$begingroup$
More background (but not a solution): mathoverflow.net/questions/254012/…
$endgroup$
– vadim123
May 15 '18 at 15:34
$begingroup$
Consider a person who speaks the fewest languages, and let this number be $k$. If $k=1$, then everyone must speak this language. If $k=4$, everyone speaks all four. If $k=2$, there are at least $n/2$ people who speak one of these two languages. So consider the fractions of people who speak exactly ${{1,2,3}$, ${1,2,4}$, ${1,3,4}$ and ${2,3,4}$.
$endgroup$
– Aravind
May 15 '18 at 16:32
$begingroup$
@aravind, I agree with your case analysis for $k=1,4$. How does $k=2$ help? $n/2<3n/5$.
$endgroup$
– vadim123
May 15 '18 at 17:28
add a comment |
$begingroup$
Out of any $5$ delegates, there must be at least $3$ that speak a common language...
$endgroup$
– Servaes
May 15 '18 at 15:34
1
$begingroup$
More background (but not a solution): mathoverflow.net/questions/254012/…
$endgroup$
– vadim123
May 15 '18 at 15:34
$begingroup$
Consider a person who speaks the fewest languages, and let this number be $k$. If $k=1$, then everyone must speak this language. If $k=4$, everyone speaks all four. If $k=2$, there are at least $n/2$ people who speak one of these two languages. So consider the fractions of people who speak exactly ${{1,2,3}$, ${1,2,4}$, ${1,3,4}$ and ${2,3,4}$.
$endgroup$
– Aravind
May 15 '18 at 16:32
$begingroup$
@aravind, I agree with your case analysis for $k=1,4$. How does $k=2$ help? $n/2<3n/5$.
$endgroup$
– vadim123
May 15 '18 at 17:28
$begingroup$
Out of any $5$ delegates, there must be at least $3$ that speak a common language...
$endgroup$
– Servaes
May 15 '18 at 15:34
$begingroup$
Out of any $5$ delegates, there must be at least $3$ that speak a common language...
$endgroup$
– Servaes
May 15 '18 at 15:34
1
1
$begingroup$
More background (but not a solution): mathoverflow.net/questions/254012/…
$endgroup$
– vadim123
May 15 '18 at 15:34
$begingroup$
More background (but not a solution): mathoverflow.net/questions/254012/…
$endgroup$
– vadim123
May 15 '18 at 15:34
$begingroup$
Consider a person who speaks the fewest languages, and let this number be $k$. If $k=1$, then everyone must speak this language. If $k=4$, everyone speaks all four. If $k=2$, there are at least $n/2$ people who speak one of these two languages. So consider the fractions of people who speak exactly ${{1,2,3}$, ${1,2,4}$, ${1,3,4}$ and ${2,3,4}$.
$endgroup$
– Aravind
May 15 '18 at 16:32
$begingroup$
Consider a person who speaks the fewest languages, and let this number be $k$. If $k=1$, then everyone must speak this language. If $k=4$, everyone speaks all four. If $k=2$, there are at least $n/2$ people who speak one of these two languages. So consider the fractions of people who speak exactly ${{1,2,3}$, ${1,2,4}$, ${1,3,4}$ and ${2,3,4}$.
$endgroup$
– Aravind
May 15 '18 at 16:32
$begingroup$
@aravind, I agree with your case analysis for $k=1,4$. How does $k=2$ help? $n/2<3n/5$.
$endgroup$
– vadim123
May 15 '18 at 17:28
$begingroup$
@aravind, I agree with your case analysis for $k=1,4$. How does $k=2$ help? $n/2<3n/5$.
$endgroup$
– vadim123
May 15 '18 at 17:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If somebody speaks only one language, then everybody speaks that language, and we're done. If somebody speaks all four languages, then the desired statement follows by induction after removing that person from the conference. So WLOG suppose everybody speaks two or three languages.
Put the four languages at the vertices of a tetrahedron. If somebody speaks two languages, put them on the edge between the two corresponding vertices, and similarly if they speak three languages put them on the corresponding face. The requirement that everyone have a common language means that two opposite edges cannot be simultaneously occupied. This leaves only two possible topologies for the occupied edges: Either the occupied edges all share a vertex, or they form a triangle. The occupied faces are totally unconstrained, as a face always shares a vertex with any edge (or other face). The number of speakers of a language is the sum of the number of people on each face and edge incident with that language's vertex.
The sharp case is if all occupied edges share a vertex (see figure below; the occupied edges are shown in red). Then the only way for that vertex to not have at least 3/5 of the conference is for some fraction $x>2/5$ to be on the opposite face $F$ (shown in blue). There's a fraction $1-x$ not on $F$, and at least a third of these must be incident with some vertex of $F$ (by pidgeonhole). This vertex thus has at least $x+(1-x)/3 = 1/3+2x/3$ of the conference, which is $>3/5$ because $x>2/5$.
The other case is where there are three occupied edges forming a triangle, which encloses some face $F$ (shown in blue below). For each vertex of the triangle, there is one edge of the triangle and one face of the tetrahedron which are not incident on it. By pidgeonholing, one of the three vertices of the triangle must have less than a third of the conference in the non-incident edge or face. Thus at least $2/3>3/5$ of the conference speaks the language of that vertex. QED
answered May 15 '18 at 21:01
YlyYly
6,82421539
$endgroup$
1
$begingroup$
Beautiful geometric argument!
$endgroup$
– vadim123
May 15 '18 at 21:13
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2782326%2fa-conference-uses-4-main-languages-prove-that-there-is-a-language-that-at-lea%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If somebody speaks only one language, then everybody speaks that language, and we're done. If somebody speaks all four languages, then the desired statement follows by induction after removing that person from the conference. So WLOG suppose everybody speaks two or three languages.
Put the four languages at the vertices of a tetrahedron. If somebody speaks two languages, put them on the edge between the two corresponding vertices, and similarly if they speak three languages put them on the corresponding face. The requirement that everyone have a common language means that two opposite edges cannot be simultaneously occupied. This leaves only two possible topologies for the occupied edges: Either the occupied edges all share a vertex, or they form a triangle. The occupied faces are totally unconstrained, as a face always shares a vertex with any edge (or other face). The number of speakers of a language is the sum of the number of people on each face and edge incident with that language's vertex.
The sharp case is if all occupied edges share a vertex (see figure below; the occupied edges are shown in red). Then the only way for that vertex to not have at least 3/5 of the conference is for some fraction $x>2/5$ to be on the opposite face $F$ (shown in blue). There's a fraction $1-x$ not on $F$, and at least a third of these must be incident with some vertex of $F$ (by pidgeonhole). This vertex thus has at least $x+(1-x)/3 = 1/3+2x/3$ of the conference, which is $>3/5$ because $x>2/5$.
The other case is where there are three occupied edges forming a triangle, which encloses some face $F$ (shown in blue below). For each vertex of the triangle, there is one edge of the triangle and one face of the tetrahedron which are not incident on it. By pidgeonholing, one of the three vertices of the triangle must have less than a third of the conference in the non-incident edge or face. Thus at least $2/3>3/5$ of the conference speaks the language of that vertex. QED
answered May 15 '18 at 21:01
YlyYly
6,82421539
$endgroup$
1
$begingroup$
Beautiful geometric argument!
$endgroup$
– vadim123
May 15 '18 at 21:13
add a comment |
$begingroup$
If somebody speaks only one language, then everybody speaks that language, and we're done. If somebody speaks all four languages, then the desired statement follows by induction after removing that person from the conference. So WLOG suppose everybody speaks two or three languages.
Put the four languages at the vertices of a tetrahedron. If somebody speaks two languages, put them on the edge between the two corresponding vertices, and similarly if they speak three languages put them on the corresponding face. The requirement that everyone have a common language means that two opposite edges cannot be simultaneously occupied. This leaves only two possible topologies for the occupied edges: Either the occupied edges all share a vertex, or they form a triangle. The occupied faces are totally unconstrained, as a face always shares a vertex with any edge (or other face). The number of speakers of a language is the sum of the number of people on each face and edge incident with that language's vertex.
The sharp case is if all occupied edges share a vertex (see figure below; the occupied edges are shown in red). Then the only way for that vertex to not have at least 3/5 of the conference is for some fraction $x>2/5$ to be on the opposite face $F$ (shown in blue). There's a fraction $1-x$ not on $F$, and at least a third of these must be incident with some vertex of $F$ (by pidgeonhole). This vertex thus has at least $x+(1-x)/3 = 1/3+2x/3$ of the conference, which is $>3/5$ because $x>2/5$.
The other case is where there are three occupied edges forming a triangle, which encloses some face $F$ (shown in blue below). For each vertex of the triangle, there is one edge of the triangle and one face of the tetrahedron which are not incident on it. By pidgeonholing, one of the three vertices of the triangle must have less than a third of the conference in the non-incident edge or face. Thus at least $2/3>3/5$ of the conference speaks the language of that vertex. QED
answered May 15 '18 at 21:01
YlyYly
6,82421539
$endgroup$
1
$begingroup$
Beautiful geometric argument!
$endgroup$
– vadim123
May 15 '18 at 21:13
add a comment |
$begingroup$
If somebody speaks only one language, then everybody speaks that language, and we're done. If somebody speaks all four languages, then the desired statement follows by induction after removing that person from the conference. So WLOG suppose everybody speaks two or three languages.
Put the four languages at the vertices of a tetrahedron. If somebody speaks two languages, put them on the edge between the two corresponding vertices, and similarly if they speak three languages put them on the corresponding face. The requirement that everyone have a common language means that two opposite edges cannot be simultaneously occupied. This leaves only two possible topologies for the occupied edges: Either the occupied edges all share a vertex, or they form a triangle. The occupied faces are totally unconstrained, as a face always shares a vertex with any edge (or other face). The number of speakers of a language is the sum of the number of people on each face and edge incident with that language's vertex.
The sharp case is if all occupied edges share a vertex (see figure below; the occupied edges are shown in red). Then the only way for that vertex to not have at least 3/5 of the conference is for some fraction $x>2/5$ to be on the opposite face $F$ (shown in blue). There's a fraction $1-x$ not on $F$, and at least a third of these must be incident with some vertex of $F$ (by pidgeonhole). This vertex thus has at least $x+(1-x)/3 = 1/3+2x/3$ of the conference, which is $>3/5$ because $x>2/5$.
The other case is where there are three occupied edges forming a triangle, which encloses some face $F$ (shown in blue below). For each vertex of the triangle, there is one edge of the triangle and one face of the tetrahedron which are not incident on it. By pidgeonholing, one of the three vertices of the triangle must have less than a third of the conference in the non-incident edge or face. Thus at least $2/3>3/5$ of the conference speaks the language of that vertex. QED
answered May 15 '18 at 21:01
YlyYly
6,82421539
$endgroup$
If somebody speaks only one language, then everybody speaks that language, and we're done. If somebody speaks all four languages, then the desired statement follows by induction after removing that person from the conference. So WLOG suppose everybody speaks two or three languages.
Put the four languages at the vertices of a tetrahedron. If somebody speaks two languages, put them on the edge between the two corresponding vertices, and similarly if they speak three languages put them on the corresponding face. The requirement that everyone have a common language means that two opposite edges cannot be simultaneously occupied. This leaves only two possible topologies for the occupied edges: Either the occupied edges all share a vertex, or they form a triangle. The occupied faces are totally unconstrained, as a face always shares a vertex with any edge (or other face). The number of speakers of a language is the sum of the number of people on each face and edge incident with that language's vertex.
The sharp case is if all occupied edges share a vertex (see figure below; the occupied edges are shown in red). Then the only way for that vertex to not have at least 3/5 of the conference is for some fraction $x>2/5$ to be on the opposite face $F$ (shown in blue). There's a fraction $1-x$ not on $F$, and at least a third of these must be incident with some vertex of $F$ (by pidgeonhole). This vertex thus has at least $x+(1-x)/3 = 1/3+2x/3$ of the conference, which is $>3/5$ because $x>2/5$.
The other case is where there are three occupied edges forming a triangle, which encloses some face $F$ (shown in blue below). For each vertex of the triangle, there is one edge of the triangle and one face of the tetrahedron which are not incident on it. By pidgeonholing, one of the three vertices of the triangle must have less than a third of the conference in the non-incident edge or face. Thus at least $2/3>3/5$ of the conference speaks the language of that vertex. QED
answered May 15 '18 at 21:01
YlyYly
6,82421539
edited May 15 '18 at 21:26
answered May 15 '18 at 21:01
YlyYly
6,82421539
answered May 15 '18 at 21:01
YlyYly
6,82421539
answered May 15 '18 at 21:01
YlyYly
6,82421539
6,82421539
1
$begingroup$
Beautiful geometric argument!
$endgroup$
– vadim123
May 15 '18 at 21:13
add a comment |
1
$begingroup$
Beautiful geometric argument!
$endgroup$
– vadim123
May 15 '18 at 21:13
1
1
$begingroup$
Beautiful geometric argument!
$endgroup$
– vadim123
May 15 '18 at 21:13
$begingroup$
Beautiful geometric argument!
$endgroup$
– vadim123
May 15 '18 at 21:13
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2782326%2fa-conference-uses-4-main-languages-prove-that-there-is-a-language-that-at-lea%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Out of any $5$ delegates, there must be at least $3$ that speak a common language...
$endgroup$
– Servaes
May 15 '18 at 15:34
1
$begingroup$
More background (but not a solution): mathoverflow.net/questions/254012/…
$endgroup$
– vadim123
May 15 '18 at 15:34
$begingroup$
Consider a person who speaks the fewest languages, and let this number be $k$. If $k=1$, then everyone must speak this language. If $k=4$, everyone speaks all four. If $k=2$, there are at least $n/2$ people who speak one of these two languages. So consider the fractions of people who speak exactly ${{1,2,3}$, ${1,2,4}$, ${1,3,4}$ and ${2,3,4}$.
$endgroup$
– Aravind
May 15 '18 at 16:32
$begingroup$
@aravind, I agree with your case analysis for $k=1,4$. How does $k=2$ help? $n/2<3n/5$.
$endgroup$
– vadim123
May 15 '18 at 17:28