Mixing
Dance competition
$begingroup$
Twenty boys and twenty girls were invited to a prom. During the dance competition $99$ pairs (consisting of a boy and a girl) made a dance performance. All pairs were unique. Prove that there exist such two boys and such two girls that each boy danced with both girls.
What I managed to do myself:
I found the number of pairs consisting of $2$ girls: it's $frac{20!}{18!cdot 2!}=190$
combinatorics graph-theory combinations
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
asked Oct 28 '16 at 19:39
SamHarSamHar
776
$endgroup$
|
show 9 more comments
$begingroup$
Twenty boys and twenty girls were invited to a prom. During the dance competition $99$ pairs (consisting of a boy and a girl) made a dance performance. All pairs were unique. Prove that there exist such two boys and such two girls that each boy danced with both girls.
What I managed to do myself:
I found the number of pairs consisting of $2$ girls: it's $frac{20!}{18!cdot 2!}=190$
combinatorics graph-theory combinations
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
asked Oct 28 '16 at 19:39
SamHarSamHar
776
$endgroup$
$begingroup$
Maybe try starting with $n$ boys and $n$ girls and try to determine $f(n)=$the maximum number of unique pairs that can dance together if there are no such two boys and girls, then show that $f(20)lt 99$. You can look for a pattern with small values of $n$.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:07
$begingroup$
This would usually be phrased as a question about how many edges a bipartite graph on 20+20 nodes with girth at least 6 can have. Attempts to search for that turns up references to a Reiman's inequality -- which however is not tight enough for this purpose (It doesn't exploit the graph being bipartite either).
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:12
$begingroup$
So far you've done one basic calculation. You might see if you can come up with any of these other quantities, which might be relevant: number of pairs consisting of a boy and a girl, number of ways to pick 2 boys and 2 girls, and anything else that occurs to you. This won't get you the solution by itself, but it can help you think about the problem, and it's good practice if you're just learning combinatorics.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:13
$begingroup$
@HenningMakholm do you mean Riemann? or is there a Reiman too?
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:19
$begingroup$
@GabrielBurns: There's a Reiman too; the inequality in question is cited as "Reiman (1958)", long after Bernhard Riemann's time.
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:20
|
show 9 more comments
$begingroup$
Twenty boys and twenty girls were invited to a prom. During the dance competition $99$ pairs (consisting of a boy and a girl) made a dance performance. All pairs were unique. Prove that there exist such two boys and such two girls that each boy danced with both girls.
What I managed to do myself:
I found the number of pairs consisting of $2$ girls: it's $frac{20!}{18!cdot 2!}=190$
combinatorics graph-theory combinations
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
asked Oct 28 '16 at 19:39
SamHarSamHar
776
$endgroup$
Twenty boys and twenty girls were invited to a prom. During the dance competition $99$ pairs (consisting of a boy and a girl) made a dance performance. All pairs were unique. Prove that there exist such two boys and such two girls that each boy danced with both girls.
What I managed to do myself:
I found the number of pairs consisting of $2$ girls: it's $frac{20!}{18!cdot 2!}=190$
combinatorics graph-theory combinations
combinatorics graph-theory combinations
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
asked Oct 28 '16 at 19:39
SamHarSamHar
776
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
asked Oct 28 '16 at 19:39
SamHarSamHar
776
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
edited Oct 28 '16 at 20:44
Irregular User
2,88251843
2,88251843
asked Oct 28 '16 at 19:39
SamHarSamHar
776
asked Oct 28 '16 at 19:39
SamHarSamHar
776
asked Oct 28 '16 at 19:39
SamHarSamHar
776
776
$begingroup$
Maybe try starting with $n$ boys and $n$ girls and try to determine $f(n)=$the maximum number of unique pairs that can dance together if there are no such two boys and girls, then show that $f(20)lt 99$. You can look for a pattern with small values of $n$.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:07
$begingroup$
This would usually be phrased as a question about how many edges a bipartite graph on 20+20 nodes with girth at least 6 can have. Attempts to search for that turns up references to a Reiman's inequality -- which however is not tight enough for this purpose (It doesn't exploit the graph being bipartite either).
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:12
$begingroup$
So far you've done one basic calculation. You might see if you can come up with any of these other quantities, which might be relevant: number of pairs consisting of a boy and a girl, number of ways to pick 2 boys and 2 girls, and anything else that occurs to you. This won't get you the solution by itself, but it can help you think about the problem, and it's good practice if you're just learning combinatorics.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:13
$begingroup$
@HenningMakholm do you mean Riemann? or is there a Reiman too?
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:19
$begingroup$
@GabrielBurns: There's a Reiman too; the inequality in question is cited as "Reiman (1958)", long after Bernhard Riemann's time.
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:20
|
show 9 more comments
$begingroup$
Maybe try starting with $n$ boys and $n$ girls and try to determine $f(n)=$the maximum number of unique pairs that can dance together if there are no such two boys and girls, then show that $f(20)lt 99$. You can look for a pattern with small values of $n$.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:07
$begingroup$
This would usually be phrased as a question about how many edges a bipartite graph on 20+20 nodes with girth at least 6 can have. Attempts to search for that turns up references to a Reiman's inequality -- which however is not tight enough for this purpose (It doesn't exploit the graph being bipartite either).
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:12
$begingroup$
So far you've done one basic calculation. You might see if you can come up with any of these other quantities, which might be relevant: number of pairs consisting of a boy and a girl, number of ways to pick 2 boys and 2 girls, and anything else that occurs to you. This won't get you the solution by itself, but it can help you think about the problem, and it's good practice if you're just learning combinatorics.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:13
$begingroup$
@HenningMakholm do you mean Riemann? or is there a Reiman too?
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:19
$begingroup$
@GabrielBurns: There's a Reiman too; the inequality in question is cited as "Reiman (1958)", long after Bernhard Riemann's time.
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:20
$begingroup$
Maybe try starting with $n$ boys and $n$ girls and try to determine $f(n)=$the maximum number of unique pairs that can dance together if there are no such two boys and girls, then show that $f(20)lt 99$. You can look for a pattern with small values of $n$.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:07
$begingroup$
Maybe try starting with $n$ boys and $n$ girls and try to determine $f(n)=$the maximum number of unique pairs that can dance together if there are no such two boys and girls, then show that $f(20)lt 99$. You can look for a pattern with small values of $n$.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:07
$begingroup$
This would usually be phrased as a question about how many edges a bipartite graph on 20+20 nodes with girth at least 6 can have. Attempts to search for that turns up references to a Reiman's inequality -- which however is not tight enough for this purpose (It doesn't exploit the graph being bipartite either).
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:12
$begingroup$
This would usually be phrased as a question about how many edges a bipartite graph on 20+20 nodes with girth at least 6 can have. Attempts to search for that turns up references to a Reiman's inequality -- which however is not tight enough for this purpose (It doesn't exploit the graph being bipartite either).
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:12
$begingroup$
So far you've done one basic calculation. You might see if you can come up with any of these other quantities, which might be relevant: number of pairs consisting of a boy and a girl, number of ways to pick 2 boys and 2 girls, and anything else that occurs to you. This won't get you the solution by itself, but it can help you think about the problem, and it's good practice if you're just learning combinatorics.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:13
$begingroup$
So far you've done one basic calculation. You might see if you can come up with any of these other quantities, which might be relevant: number of pairs consisting of a boy and a girl, number of ways to pick 2 boys and 2 girls, and anything else that occurs to you. This won't get you the solution by itself, but it can help you think about the problem, and it's good practice if you're just learning combinatorics.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:13
$begingroup$
@HenningMakholm do you mean Riemann? or is there a Reiman too?
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:19
$begingroup$
@HenningMakholm do you mean Riemann? or is there a Reiman too?
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:19
$begingroup$
@GabrielBurns: There's a Reiman too; the inequality in question is cited as "Reiman (1958)", long after Bernhard Riemann's time.
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:20
$begingroup$
@GabrielBurns: There's a Reiman too; the inequality in question is cited as "Reiman (1958)", long after Bernhard Riemann's time.
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:20
|
show 9 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Assume that there is no two boys and two girls that each boy danced with both girls.
Let the girls are G1, G2, ...G20, and they danced with n1, n2, ...n20 boys.
We have that
n1 + n2 + ... + n20 = 99*2 = 198
For a girl, say G1, we can select 2 boys from the n1 boys who danced with G1. There are C(n1,2) = n1*(n1-1)/2 such pair of boys. Similar, for girl G2, we have C(n2,2) pairs of boy who danced with G2. We say, the boy-pairs of G1 and G2 has no overlap, otherwise we will have boy B1 and B2, they both danced with G1 and G2, contradiction.
Boy-pairs of each girl should have no overlap. So, the sum should be not greater than C(20,2)=190
It's to say:
C(n1,2)+C(n2,2)+...+C(n20,2)<=190
but the left side is
(n1^2 + n2^2 + ... + n20^2 - n1 - n2 - ... -n20)/2
it's greater or equal than
( ((n1+...+n20)/20)^2 * 20 - (n1+...+n20) )/2
= ( (198/20)^2 * 20 - 198 ) / 2
= 881.1
contradiction
answered Jan 28 at 11:55
Rocky.LRocky.L
1
$endgroup$
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%2f1989514%2fdance-competition%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$
Assume that there is no two boys and two girls that each boy danced with both girls.
Let the girls are G1, G2, ...G20, and they danced with n1, n2, ...n20 boys.
We have that
n1 + n2 + ... + n20 = 99*2 = 198
For a girl, say G1, we can select 2 boys from the n1 boys who danced with G1. There are C(n1,2) = n1*(n1-1)/2 such pair of boys. Similar, for girl G2, we have C(n2,2) pairs of boy who danced with G2. We say, the boy-pairs of G1 and G2 has no overlap, otherwise we will have boy B1 and B2, they both danced with G1 and G2, contradiction.
Boy-pairs of each girl should have no overlap. So, the sum should be not greater than C(20,2)=190
It's to say:
C(n1,2)+C(n2,2)+...+C(n20,2)<=190
but the left side is
(n1^2 + n2^2 + ... + n20^2 - n1 - n2 - ... -n20)/2
it's greater or equal than
( ((n1+...+n20)/20)^2 * 20 - (n1+...+n20) )/2
= ( (198/20)^2 * 20 - 198 ) / 2
= 881.1
contradiction
answered Jan 28 at 11:55
Rocky.LRocky.L
1
$endgroup$
add a comment |
$begingroup$
Assume that there is no two boys and two girls that each boy danced with both girls.
Let the girls are G1, G2, ...G20, and they danced with n1, n2, ...n20 boys.
We have that
n1 + n2 + ... + n20 = 99*2 = 198
For a girl, say G1, we can select 2 boys from the n1 boys who danced with G1. There are C(n1,2) = n1*(n1-1)/2 such pair of boys. Similar, for girl G2, we have C(n2,2) pairs of boy who danced with G2. We say, the boy-pairs of G1 and G2 has no overlap, otherwise we will have boy B1 and B2, they both danced with G1 and G2, contradiction.
Boy-pairs of each girl should have no overlap. So, the sum should be not greater than C(20,2)=190
It's to say:
C(n1,2)+C(n2,2)+...+C(n20,2)<=190
but the left side is
(n1^2 + n2^2 + ... + n20^2 - n1 - n2 - ... -n20)/2
it's greater or equal than
( ((n1+...+n20)/20)^2 * 20 - (n1+...+n20) )/2
= ( (198/20)^2 * 20 - 198 ) / 2
= 881.1
contradiction
answered Jan 28 at 11:55
Rocky.LRocky.L
1
$endgroup$
add a comment |
$begingroup$
Assume that there is no two boys and two girls that each boy danced with both girls.
Let the girls are G1, G2, ...G20, and they danced with n1, n2, ...n20 boys.
We have that
n1 + n2 + ... + n20 = 99*2 = 198
For a girl, say G1, we can select 2 boys from the n1 boys who danced with G1. There are C(n1,2) = n1*(n1-1)/2 such pair of boys. Similar, for girl G2, we have C(n2,2) pairs of boy who danced with G2. We say, the boy-pairs of G1 and G2 has no overlap, otherwise we will have boy B1 and B2, they both danced with G1 and G2, contradiction.
Boy-pairs of each girl should have no overlap. So, the sum should be not greater than C(20,2)=190
It's to say:
C(n1,2)+C(n2,2)+...+C(n20,2)<=190
but the left side is
(n1^2 + n2^2 + ... + n20^2 - n1 - n2 - ... -n20)/2
it's greater or equal than
( ((n1+...+n20)/20)^2 * 20 - (n1+...+n20) )/2
= ( (198/20)^2 * 20 - 198 ) / 2
= 881.1
contradiction
answered Jan 28 at 11:55
Rocky.LRocky.L
1
$endgroup$
Assume that there is no two boys and two girls that each boy danced with both girls.
Let the girls are G1, G2, ...G20, and they danced with n1, n2, ...n20 boys.
We have that
n1 + n2 + ... + n20 = 99*2 = 198
For a girl, say G1, we can select 2 boys from the n1 boys who danced with G1. There are C(n1,2) = n1*(n1-1)/2 such pair of boys. Similar, for girl G2, we have C(n2,2) pairs of boy who danced with G2. We say, the boy-pairs of G1 and G2 has no overlap, otherwise we will have boy B1 and B2, they both danced with G1 and G2, contradiction.
Boy-pairs of each girl should have no overlap. So, the sum should be not greater than C(20,2)=190
It's to say:
C(n1,2)+C(n2,2)+...+C(n20,2)<=190
but the left side is
(n1^2 + n2^2 + ... + n20^2 - n1 - n2 - ... -n20)/2
it's greater or equal than
( ((n1+...+n20)/20)^2 * 20 - (n1+...+n20) )/2
= ( (198/20)^2 * 20 - 198 ) / 2
= 881.1
contradiction
answered Jan 28 at 11:55
Rocky.LRocky.L
1
answered Jan 28 at 11:55
Rocky.LRocky.L
1
answered Jan 28 at 11:55
Rocky.LRocky.L
1
answered Jan 28 at 11:55
Rocky.LRocky.L
1
1
add a comment |
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%2f1989514%2fdance-competition%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$
Maybe try starting with $n$ boys and $n$ girls and try to determine $f(n)=$the maximum number of unique pairs that can dance together if there are no such two boys and girls, then show that $f(20)lt 99$. You can look for a pattern with small values of $n$.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:07
$begingroup$
This would usually be phrased as a question about how many edges a bipartite graph on 20+20 nodes with girth at least 6 can have. Attempts to search for that turns up references to a Reiman's inequality -- which however is not tight enough for this purpose (It doesn't exploit the graph being bipartite either).
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:12
$begingroup$
So far you've done one basic calculation. You might see if you can come up with any of these other quantities, which might be relevant: number of pairs consisting of a boy and a girl, number of ways to pick 2 boys and 2 girls, and anything else that occurs to you. This won't get you the solution by itself, but it can help you think about the problem, and it's good practice if you're just learning combinatorics.
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:13
$begingroup$
@HenningMakholm do you mean Riemann? or is there a Reiman too?
$endgroup$
– Gabriel Burns
Oct 28 '16 at 20:19
$begingroup$
@GabrielBurns: There's a Reiman too; the inequality in question is cited as "Reiman (1958)", long after Bernhard Riemann's time.
$endgroup$
– Henning Makholm
Oct 28 '16 at 20:20