Mixing
Proof Writing: Handshakes in a Party
$begingroup$
I am a high school student self-studying for the Olympiad and came across this question in the book Challenge and Thrill of Pre-College Mathematics:
Prove that in any party the number of people who made an odd number of handshakes is always even.
I managed to ascertain some sort of proof, but it seems very heuristic rather than formal.
My attempt:
Clearly if two people shake hands, then we can say that each person experiences one handshake, which brings the total sum of experienced handshakes up to $2$. Building on this we can say that if there were $n$ handshakes then the number of experienced handshakes is $2n$.
At this point I remembered that I had read somewhere that these sort of questions can be answered using graph theory, which makes my statement equivalent to proving that the sum of the degrees of each node of a graph has to be even.
I think it is possible to say that since for each edge drawn there are $2$ nodes which each gain a degree, the sum of the degrees should be twice the number of edges, which implies that the number of edges is always even.
Thus if there so happens that there is an odd number of people who have experienced an odd number of handshakes, by parity the total number of experienced handshakes will be odd, which contradicts the above assertion, rendering the statement wrong.
Furthermore, I stumbled across this question in a number theory chapter, and the book itself does not have any chapter about graphs. Thus, I have two questions:
(1) How do I write the above proof, and (2) is there some number theoretic way to prove it?
proof-verification graph-theory proof-writing
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
$endgroup$
|
show 1 more comment
$begingroup$
I am a high school student self-studying for the Olympiad and came across this question in the book Challenge and Thrill of Pre-College Mathematics:
Prove that in any party the number of people who made an odd number of handshakes is always even.
I managed to ascertain some sort of proof, but it seems very heuristic rather than formal.
My attempt:
Clearly if two people shake hands, then we can say that each person experiences one handshake, which brings the total sum of experienced handshakes up to $2$. Building on this we can say that if there were $n$ handshakes then the number of experienced handshakes is $2n$.
At this point I remembered that I had read somewhere that these sort of questions can be answered using graph theory, which makes my statement equivalent to proving that the sum of the degrees of each node of a graph has to be even.
I think it is possible to say that since for each edge drawn there are $2$ nodes which each gain a degree, the sum of the degrees should be twice the number of edges, which implies that the number of edges is always even.
Thus if there so happens that there is an odd number of people who have experienced an odd number of handshakes, by parity the total number of experienced handshakes will be odd, which contradicts the above assertion, rendering the statement wrong.
Furthermore, I stumbled across this question in a number theory chapter, and the book itself does not have any chapter about graphs. Thus, I have two questions:
(1) How do I write the above proof, and (2) is there some number theoretic way to prove it?
proof-verification graph-theory proof-writing
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
$endgroup$
3
$begingroup$
Don't you mean the number of people who shook hands an odd number of times is always even?
$endgroup$
– fleablood
Jan 22 at 7:11
$begingroup$
Whoops, my bad. Just editing it right now.
$endgroup$
– Naman Kumar
Jan 22 at 7:14
1
$begingroup$
Hint: can you prove that an odd number of odd terms always adds to an odd number? Then can you prove that if you add any number of even terms to that you still get an even number? So if there were an odd number of people experiencing an odd number of shakes and everyone else experiences an even number, then there will be an odd number experienced. But the number experienced is twice the number of shakes.
$endgroup$
– fleablood
Jan 22 at 7:40
$begingroup$
@fleablood If I take the odd numbers as $2a_1+1, 2a_2+1+...+ 2a_{2n+1}+1$, and then adding them to get $2(a_1+a_2+...+a_{2n+1}+n)+1$, which is odd, is that correct?
$endgroup$
– Naman Kumar
Jan 22 at 8:05
1
$begingroup$
That's a very clear way of putting. I actually didn't have a method in mind but as pairs of odd number add to an even number an odd group of odds would "pair off" to make a bunch of evens and one lonely odd. But that's the idea... you add up the hand shakes by the even number people and you get an even number, you add up the hand shakes by the odd number people and you either get an even or an odd depending only whether there are an even or an odd number of them. The final result is even so that means the odd number people must experience an even number of shakes....
$endgroup$
– fleablood
Jan 22 at 18:44
|
show 1 more comment
$begingroup$
I am a high school student self-studying for the Olympiad and came across this question in the book Challenge and Thrill of Pre-College Mathematics:
Prove that in any party the number of people who made an odd number of handshakes is always even.
I managed to ascertain some sort of proof, but it seems very heuristic rather than formal.
My attempt:
Clearly if two people shake hands, then we can say that each person experiences one handshake, which brings the total sum of experienced handshakes up to $2$. Building on this we can say that if there were $n$ handshakes then the number of experienced handshakes is $2n$.
At this point I remembered that I had read somewhere that these sort of questions can be answered using graph theory, which makes my statement equivalent to proving that the sum of the degrees of each node of a graph has to be even.
I think it is possible to say that since for each edge drawn there are $2$ nodes which each gain a degree, the sum of the degrees should be twice the number of edges, which implies that the number of edges is always even.
Thus if there so happens that there is an odd number of people who have experienced an odd number of handshakes, by parity the total number of experienced handshakes will be odd, which contradicts the above assertion, rendering the statement wrong.
Furthermore, I stumbled across this question in a number theory chapter, and the book itself does not have any chapter about graphs. Thus, I have two questions:
(1) How do I write the above proof, and (2) is there some number theoretic way to prove it?
proof-verification graph-theory proof-writing
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
$endgroup$
I am a high school student self-studying for the Olympiad and came across this question in the book Challenge and Thrill of Pre-College Mathematics:
Prove that in any party the number of people who made an odd number of handshakes is always even.
I managed to ascertain some sort of proof, but it seems very heuristic rather than formal.
My attempt:
Clearly if two people shake hands, then we can say that each person experiences one handshake, which brings the total sum of experienced handshakes up to $2$. Building on this we can say that if there were $n$ handshakes then the number of experienced handshakes is $2n$.
At this point I remembered that I had read somewhere that these sort of questions can be answered using graph theory, which makes my statement equivalent to proving that the sum of the degrees of each node of a graph has to be even.
I think it is possible to say that since for each edge drawn there are $2$ nodes which each gain a degree, the sum of the degrees should be twice the number of edges, which implies that the number of edges is always even.
Thus if there so happens that there is an odd number of people who have experienced an odd number of handshakes, by parity the total number of experienced handshakes will be odd, which contradicts the above assertion, rendering the statement wrong.
Furthermore, I stumbled across this question in a number theory chapter, and the book itself does not have any chapter about graphs. Thus, I have two questions:
(1) How do I write the above proof, and (2) is there some number theoretic way to prove it?
proof-verification graph-theory proof-writing
proof-verification graph-theory proof-writing
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
edited Jan 22 at 7:15
Naman Kumar
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
asked Jan 22 at 6:59
Naman KumarNaman Kumar
22813
22813
3
$begingroup$
Don't you mean the number of people who shook hands an odd number of times is always even?
$endgroup$
– fleablood
Jan 22 at 7:11
$begingroup$
Whoops, my bad. Just editing it right now.
$endgroup$
– Naman Kumar
Jan 22 at 7:14
1
$begingroup$
Hint: can you prove that an odd number of odd terms always adds to an odd number? Then can you prove that if you add any number of even terms to that you still get an even number? So if there were an odd number of people experiencing an odd number of shakes and everyone else experiences an even number, then there will be an odd number experienced. But the number experienced is twice the number of shakes.
$endgroup$
– fleablood
Jan 22 at 7:40
$begingroup$
@fleablood If I take the odd numbers as $2a_1+1, 2a_2+1+...+ 2a_{2n+1}+1$, and then adding them to get $2(a_1+a_2+...+a_{2n+1}+n)+1$, which is odd, is that correct?
$endgroup$
– Naman Kumar
Jan 22 at 8:05
1
$begingroup$
That's a very clear way of putting. I actually didn't have a method in mind but as pairs of odd number add to an even number an odd group of odds would "pair off" to make a bunch of evens and one lonely odd. But that's the idea... you add up the hand shakes by the even number people and you get an even number, you add up the hand shakes by the odd number people and you either get an even or an odd depending only whether there are an even or an odd number of them. The final result is even so that means the odd number people must experience an even number of shakes....
$endgroup$
– fleablood
Jan 22 at 18:44
|
show 1 more comment
3
$begingroup$
Don't you mean the number of people who shook hands an odd number of times is always even?
$endgroup$
– fleablood
Jan 22 at 7:11
$begingroup$
Whoops, my bad. Just editing it right now.
$endgroup$
– Naman Kumar
Jan 22 at 7:14
1
$begingroup$
Hint: can you prove that an odd number of odd terms always adds to an odd number? Then can you prove that if you add any number of even terms to that you still get an even number? So if there were an odd number of people experiencing an odd number of shakes and everyone else experiences an even number, then there will be an odd number experienced. But the number experienced is twice the number of shakes.
$endgroup$
– fleablood
Jan 22 at 7:40
$begingroup$
@fleablood If I take the odd numbers as $2a_1+1, 2a_2+1+...+ 2a_{2n+1}+1$, and then adding them to get $2(a_1+a_2+...+a_{2n+1}+n)+1$, which is odd, is that correct?
$endgroup$
– Naman Kumar
Jan 22 at 8:05
1
$begingroup$
That's a very clear way of putting. I actually didn't have a method in mind but as pairs of odd number add to an even number an odd group of odds would "pair off" to make a bunch of evens and one lonely odd. But that's the idea... you add up the hand shakes by the even number people and you get an even number, you add up the hand shakes by the odd number people and you either get an even or an odd depending only whether there are an even or an odd number of them. The final result is even so that means the odd number people must experience an even number of shakes....
$endgroup$
– fleablood
Jan 22 at 18:44
3
3
$begingroup$
Don't you mean the number of people who shook hands an odd number of times is always even?
$endgroup$
– fleablood
Jan 22 at 7:11
$begingroup$
Don't you mean the number of people who shook hands an odd number of times is always even?
$endgroup$
– fleablood
Jan 22 at 7:11
$begingroup$
Whoops, my bad. Just editing it right now.
$endgroup$
– Naman Kumar
Jan 22 at 7:14
$begingroup$
Whoops, my bad. Just editing it right now.
$endgroup$
– Naman Kumar
Jan 22 at 7:14
1
1
$begingroup$
Hint: can you prove that an odd number of odd terms always adds to an odd number? Then can you prove that if you add any number of even terms to that you still get an even number? So if there were an odd number of people experiencing an odd number of shakes and everyone else experiences an even number, then there will be an odd number experienced. But the number experienced is twice the number of shakes.
$endgroup$
– fleablood
Jan 22 at 7:40
$begingroup$
Hint: can you prove that an odd number of odd terms always adds to an odd number? Then can you prove that if you add any number of even terms to that you still get an even number? So if there were an odd number of people experiencing an odd number of shakes and everyone else experiences an even number, then there will be an odd number experienced. But the number experienced is twice the number of shakes.
$endgroup$
– fleablood
Jan 22 at 7:40
$begingroup$
@fleablood If I take the odd numbers as $2a_1+1, 2a_2+1+...+ 2a_{2n+1}+1$, and then adding them to get $2(a_1+a_2+...+a_{2n+1}+n)+1$, which is odd, is that correct?
$endgroup$
– Naman Kumar
Jan 22 at 8:05
$begingroup$
@fleablood If I take the odd numbers as $2a_1+1, 2a_2+1+...+ 2a_{2n+1}+1$, and then adding them to get $2(a_1+a_2+...+a_{2n+1}+n)+1$, which is odd, is that correct?
$endgroup$
– Naman Kumar
Jan 22 at 8:05
1
1
$begingroup$
That's a very clear way of putting. I actually didn't have a method in mind but as pairs of odd number add to an even number an odd group of odds would "pair off" to make a bunch of evens and one lonely odd. But that's the idea... you add up the hand shakes by the even number people and you get an even number, you add up the hand shakes by the odd number people and you either get an even or an odd depending only whether there are an even or an odd number of them. The final result is even so that means the odd number people must experience an even number of shakes....
$endgroup$
– fleablood
Jan 22 at 18:44
$begingroup$
That's a very clear way of putting. I actually didn't have a method in mind but as pairs of odd number add to an even number an odd group of odds would "pair off" to make a bunch of evens and one lonely odd. But that's the idea... you add up the hand shakes by the even number people and you get an even number, you add up the hand shakes by the odd number people and you either get an even or an odd depending only whether there are an even or an odd number of them. The final result is even so that means the odd number people must experience an even number of shakes....
$endgroup$
– fleablood
Jan 22 at 18:44
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
Your proof looks good. In fact, you can skip the two middle paragraphs of your attempt and just use the first and the last. The total number of experienced handshakes is even, and therefore the number of people who experienced an odd number of handshakes must also be even. No need to mix graph theory into that answer.
The number theory behind this is that the sum of an odd number of odd numbers is odd. So this is a number theoretical proof.
answered Jan 22 at 7:09
ArthurArthur
117k7116200
$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%2f3082834%2fproof-writing-handshakes-in-a-party%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$
Your proof looks good. In fact, you can skip the two middle paragraphs of your attempt and just use the first and the last. The total number of experienced handshakes is even, and therefore the number of people who experienced an odd number of handshakes must also be even. No need to mix graph theory into that answer.
The number theory behind this is that the sum of an odd number of odd numbers is odd. So this is a number theoretical proof.
answered Jan 22 at 7:09
ArthurArthur
117k7116200
$endgroup$
add a comment |
$begingroup$
Your proof looks good. In fact, you can skip the two middle paragraphs of your attempt and just use the first and the last. The total number of experienced handshakes is even, and therefore the number of people who experienced an odd number of handshakes must also be even. No need to mix graph theory into that answer.
The number theory behind this is that the sum of an odd number of odd numbers is odd. So this is a number theoretical proof.
answered Jan 22 at 7:09
ArthurArthur
117k7116200
$endgroup$
add a comment |
$begingroup$
Your proof looks good. In fact, you can skip the two middle paragraphs of your attempt and just use the first and the last. The total number of experienced handshakes is even, and therefore the number of people who experienced an odd number of handshakes must also be even. No need to mix graph theory into that answer.
The number theory behind this is that the sum of an odd number of odd numbers is odd. So this is a number theoretical proof.
answered Jan 22 at 7:09
ArthurArthur
117k7116200
$endgroup$
Your proof looks good. In fact, you can skip the two middle paragraphs of your attempt and just use the first and the last. The total number of experienced handshakes is even, and therefore the number of people who experienced an odd number of handshakes must also be even. No need to mix graph theory into that answer.
The number theory behind this is that the sum of an odd number of odd numbers is odd. So this is a number theoretical proof.
answered Jan 22 at 7:09
ArthurArthur
117k7116200
edited Jan 22 at 7:15
answered Jan 22 at 7:09
ArthurArthur
117k7116200
answered Jan 22 at 7:09
ArthurArthur
117k7116200
answered Jan 22 at 7:09
ArthurArthur
117k7116200
117k7116200
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%2f3082834%2fproof-writing-handshakes-in-a-party%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$
Don't you mean the number of people who shook hands an odd number of times is always even?
$endgroup$
– fleablood
Jan 22 at 7:11
$begingroup$
Whoops, my bad. Just editing it right now.
$endgroup$
– Naman Kumar
Jan 22 at 7:14
1
$begingroup$
Hint: can you prove that an odd number of odd terms always adds to an odd number? Then can you prove that if you add any number of even terms to that you still get an even number? So if there were an odd number of people experiencing an odd number of shakes and everyone else experiences an even number, then there will be an odd number experienced. But the number experienced is twice the number of shakes.
$endgroup$
– fleablood
Jan 22 at 7:40
$begingroup$
@fleablood If I take the odd numbers as $2a_1+1, 2a_2+1+...+ 2a_{2n+1}+1$, and then adding them to get $2(a_1+a_2+...+a_{2n+1}+n)+1$, which is odd, is that correct?
$endgroup$
– Naman Kumar
Jan 22 at 8:05
1
$begingroup$
That's a very clear way of putting. I actually didn't have a method in mind but as pairs of odd number add to an even number an odd group of odds would "pair off" to make a bunch of evens and one lonely odd. But that's the idea... you add up the hand shakes by the even number people and you get an even number, you add up the hand shakes by the odd number people and you either get an even or an odd depending only whether there are an even or an odd number of them. The final result is even so that means the odd number people must experience an even number of shakes....
$endgroup$
– fleablood
Jan 22 at 18:44