Mixing
Counting problem: proving
$begingroup$
Consider an antireflexive, symmetric relation "is a friend of". Proof that in a group of $n$ people, there will always be an even number of people with an odd number of friends.
What I've already tried:
Suppose $A$ is the set of people with $|A| = n$. Consider the function $f: A to mathbb{N}_{<n}$ that maps a person to the number of friends he/she has ($<n$ because the relation we're looking at is antireflexive). The codomain of $f$ has exactly $n$ elements. $A$ and $mathbb{N}_{<n}$ have the same number of elements and therefor we can always find a bijection, and thus a surjection, between the two sets. If $n$ is even, we can map all people to $n-1$, meaning everybody is everybody's friend. If $n$ is odd, we randomly take $(n-1)/2$ people and map them to $n-2$; the other half of the people can be mapped to $0$. This completes the proof.
I don't know if this is the correct way of proving these type of questions. Does anyone have other methods/ideas? Is my proof correct?
Thanks.
combinatorics discrete-mathematics
asked Jan 27 at 9:47
ZacharyZachary
1919
$endgroup$
add a comment |
$begingroup$
Consider an antireflexive, symmetric relation "is a friend of". Proof that in a group of $n$ people, there will always be an even number of people with an odd number of friends.
What I've already tried:
Suppose $A$ is the set of people with $|A| = n$. Consider the function $f: A to mathbb{N}_{<n}$ that maps a person to the number of friends he/she has ($<n$ because the relation we're looking at is antireflexive). The codomain of $f$ has exactly $n$ elements. $A$ and $mathbb{N}_{<n}$ have the same number of elements and therefor we can always find a bijection, and thus a surjection, between the two sets. If $n$ is even, we can map all people to $n-1$, meaning everybody is everybody's friend. If $n$ is odd, we randomly take $(n-1)/2$ people and map them to $n-2$; the other half of the people can be mapped to $0$. This completes the proof.
I don't know if this is the correct way of proving these type of questions. Does anyone have other methods/ideas? Is my proof correct?
Thanks.
combinatorics discrete-mathematics
asked Jan 27 at 9:47
ZacharyZachary
1919
$endgroup$
3
$begingroup$
This is a graph theory problem.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:49
2
$begingroup$
handshaking lemma is not it?
$endgroup$
– Bijayan Ray
Jan 27 at 9:50
2
$begingroup$
You seem to be deciding who should be friends with each other. You should accept that they have already decided who are friends already.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:51
add a comment |
$begingroup$
Consider an antireflexive, symmetric relation "is a friend of". Proof that in a group of $n$ people, there will always be an even number of people with an odd number of friends.
What I've already tried:
Suppose $A$ is the set of people with $|A| = n$. Consider the function $f: A to mathbb{N}_{<n}$ that maps a person to the number of friends he/she has ($<n$ because the relation we're looking at is antireflexive). The codomain of $f$ has exactly $n$ elements. $A$ and $mathbb{N}_{<n}$ have the same number of elements and therefor we can always find a bijection, and thus a surjection, between the two sets. If $n$ is even, we can map all people to $n-1$, meaning everybody is everybody's friend. If $n$ is odd, we randomly take $(n-1)/2$ people and map them to $n-2$; the other half of the people can be mapped to $0$. This completes the proof.
I don't know if this is the correct way of proving these type of questions. Does anyone have other methods/ideas? Is my proof correct?
Thanks.
combinatorics discrete-mathematics
asked Jan 27 at 9:47
ZacharyZachary
1919
$endgroup$
Consider an antireflexive, symmetric relation "is a friend of". Proof that in a group of $n$ people, there will always be an even number of people with an odd number of friends.
What I've already tried:
Suppose $A$ is the set of people with $|A| = n$. Consider the function $f: A to mathbb{N}_{<n}$ that maps a person to the number of friends he/she has ($<n$ because the relation we're looking at is antireflexive). The codomain of $f$ has exactly $n$ elements. $A$ and $mathbb{N}_{<n}$ have the same number of elements and therefor we can always find a bijection, and thus a surjection, between the two sets. If $n$ is even, we can map all people to $n-1$, meaning everybody is everybody's friend. If $n$ is odd, we randomly take $(n-1)/2$ people and map them to $n-2$; the other half of the people can be mapped to $0$. This completes the proof.
I don't know if this is the correct way of proving these type of questions. Does anyone have other methods/ideas? Is my proof correct?
Thanks.
combinatorics discrete-mathematics
combinatorics discrete-mathematics
asked Jan 27 at 9:47
ZacharyZachary
1919
asked Jan 27 at 9:47
ZacharyZachary
1919
asked Jan 27 at 9:47
ZacharyZachary
1919
asked Jan 27 at 9:47
ZacharyZachary
1919
asked Jan 27 at 9:47
ZacharyZachary
1919
1919
3
$begingroup$
This is a graph theory problem.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:49
2
$begingroup$
handshaking lemma is not it?
$endgroup$
– Bijayan Ray
Jan 27 at 9:50
2
$begingroup$
You seem to be deciding who should be friends with each other. You should accept that they have already decided who are friends already.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:51
add a comment |
3
$begingroup$
This is a graph theory problem.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:49
2
$begingroup$
handshaking lemma is not it?
$endgroup$
– Bijayan Ray
Jan 27 at 9:50
2
$begingroup$
You seem to be deciding who should be friends with each other. You should accept that they have already decided who are friends already.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:51
3
3
$begingroup$
This is a graph theory problem.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:49
$begingroup$
This is a graph theory problem.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:49
2
2
$begingroup$
handshaking lemma is not it?
$endgroup$
– Bijayan Ray
Jan 27 at 9:50
$begingroup$
handshaking lemma is not it?
$endgroup$
– Bijayan Ray
Jan 27 at 9:50
2
2
$begingroup$
You seem to be deciding who should be friends with each other. You should accept that they have already decided who are friends already.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:51
$begingroup$
You seem to be deciding who should be friends with each other. You should accept that they have already decided who are friends already.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:51
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Consider the $v_k$ denote a person observe that the total number of 'is friend of' is even because $v_x$ 'is friend of' $v_y$ implies the converse too. So now if number of people with odd number of friend is odd the "the total number of 'is friend of'" would be odd too hence contradiction which proves the assertion (you may also refer Wikipedia "handshaking lemma " for general graph theoretic proof)
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
$endgroup$
add a comment |
$begingroup$
Assume there are an odd number of people with an odd number of friends. Then the total number of friendship is $frac{text{odd*odd+even*even}}{2}$ which is not an integer. This is a contradiction.
answered Jan 27 at 10:05
abc...abc...
3,237738
$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%2f3089346%2fcounting-problem-proving%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Consider the $v_k$ denote a person observe that the total number of 'is friend of' is even because $v_x$ 'is friend of' $v_y$ implies the converse too. So now if number of people with odd number of friend is odd the "the total number of 'is friend of'" would be odd too hence contradiction which proves the assertion (you may also refer Wikipedia "handshaking lemma " for general graph theoretic proof)
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
$endgroup$
add a comment |
$begingroup$
Consider the $v_k$ denote a person observe that the total number of 'is friend of' is even because $v_x$ 'is friend of' $v_y$ implies the converse too. So now if number of people with odd number of friend is odd the "the total number of 'is friend of'" would be odd too hence contradiction which proves the assertion (you may also refer Wikipedia "handshaking lemma " for general graph theoretic proof)
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
$endgroup$
add a comment |
$begingroup$
Consider the $v_k$ denote a person observe that the total number of 'is friend of' is even because $v_x$ 'is friend of' $v_y$ implies the converse too. So now if number of people with odd number of friend is odd the "the total number of 'is friend of'" would be odd too hence contradiction which proves the assertion (you may also refer Wikipedia "handshaking lemma " for general graph theoretic proof)
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
$endgroup$
Consider the $v_k$ denote a person observe that the total number of 'is friend of' is even because $v_x$ 'is friend of' $v_y$ implies the converse too. So now if number of people with odd number of friend is odd the "the total number of 'is friend of'" would be odd too hence contradiction which proves the assertion (you may also refer Wikipedia "handshaking lemma " for general graph theoretic proof)
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
answered Jan 27 at 9:57
Bijayan RayBijayan Ray
136112
136112
add a comment |
add a comment |
$begingroup$
Assume there are an odd number of people with an odd number of friends. Then the total number of friendship is $frac{text{odd*odd+even*even}}{2}$ which is not an integer. This is a contradiction.
answered Jan 27 at 10:05
abc...abc...
3,237738
$endgroup$
add a comment |
$begingroup$
Assume there are an odd number of people with an odd number of friends. Then the total number of friendship is $frac{text{odd*odd+even*even}}{2}$ which is not an integer. This is a contradiction.
answered Jan 27 at 10:05
abc...abc...
3,237738
$endgroup$
add a comment |
$begingroup$
Assume there are an odd number of people with an odd number of friends. Then the total number of friendship is $frac{text{odd*odd+even*even}}{2}$ which is not an integer. This is a contradiction.
answered Jan 27 at 10:05
abc...abc...
3,237738
$endgroup$
Assume there are an odd number of people with an odd number of friends. Then the total number of friendship is $frac{text{odd*odd+even*even}}{2}$ which is not an integer. This is a contradiction.
answered Jan 27 at 10:05
abc...abc...
3,237738
answered Jan 27 at 10:05
abc...abc...
3,237738
answered Jan 27 at 10:05
abc...abc...
3,237738
answered Jan 27 at 10:05
abc...abc...
3,237738
3,237738
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%2f3089346%2fcounting-problem-proving%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
3
$begingroup$
This is a graph theory problem.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:49
2
$begingroup$
handshaking lemma is not it?
$endgroup$
– Bijayan Ray
Jan 27 at 9:50
2
$begingroup$
You seem to be deciding who should be friends with each other. You should accept that they have already decided who are friends already.
$endgroup$
– Lord Shark the Unknown
Jan 27 at 9:51