4
$\begingroup$

At a congress there are some doctors, and everyone shakes a certain number of hands (never more than once with the same person). The doctors can be divided in two groups:

-Group O: the doctors who shook hands an odd number of times

-Group E: the doctors who shook hands an even number of times

Prove that the total number of doctors in group O is even.

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ It is actually known as the handshaking lemma. $\endgroup$
    – Jaap Scherphuis
    May 23, 2022 at 20:53
  • 2
    $\begingroup$ I'll note the stipulation of handshaking occurring "never more than once with the same person" actually makes no difference whatsoever. The result is still true even if a pair can shake hands multiple times. $\endgroup$
    – Nuclear Hoagie
    May 24, 2022 at 17:09
  • $\begingroup$ @Jaap Scherphuis It is advised to not answer questions in comments. Is it your thinking that this question/puzzle is trivial since it is based on a known lemma, and the comment functions like a downvote? Or is it just extra info? If the latter, it is better as a comment on an answer, or at least rot13, because it might ruin the puzzle for someone. $\endgroup$
    – JLee
    May 24, 2022 at 19:25
  • 1
    $\begingroup$ Illustration: youtu.be/hoe24aSvLtw $\endgroup$
    – David Conrad
    May 25, 2022 at 21:05
  • $\begingroup$ I noticed that you are also a Doctor, based on your handle ;) $\endgroup$
    – Dmitry Kamenetsky
    May 26, 2022 at 5:49

3 Answers 3

Reset to default
24
$\begingroup$

Every hand shake that occurs

will change the group membership of two doctors. This will either switch two doctors from one group to another, or have them trade groups.

Since

group membership can only change by -2, 0, or 2 for each handshake, the parity of the number of doctors in each group will never change.

Since Group O

starts with zero members, an even number, every handshake keeps it even.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Nice inductive proof. Feels more elegant than the "sum of a set of odd numbers" approach. $\endgroup$
    – fljx
    May 23, 2022 at 20:29
  • 2
    $\begingroup$ Great answer! For clarity, I would expand the first section to explicitly describe what happens to the size of Group O in each case. $\endgroup$
    – Qami
    May 25, 2022 at 18:39
15
$\begingroup$

This seems pretty straightforward:

The total number of hands that are involved in handshakes must be even (i.e. each handshake involves two hands). This must also be the sum of all the "shakes" from group E plus all the "shakes" from group O.

The total number of "shakes" from group E is obviously even. Thus the total number of "shakes" from group O must also be even. Since each person in group O contributes an odd number of "shakes" to the total, there must be an even number of doctors in that group.

Improve this answer
$\endgroup$
0
8
$\begingroup$

Every handshake involves two doctors, so is counted twice if you add up all the handshakes-per-doctor. So the total must be even.

The sum of handshakes from group E will always be even, so the sum from group O must also be even to make the total even.

All the counts in group O are odd, so there must be an even number of them for an even sum.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.