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.

$\endgroup$
5
  • 8
    $\begingroup$ It is actually known as the handshaking lemma. $\endgroup$ May 23 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$ May 24 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 at 19:25
  • 1
    $\begingroup$ Illustration: youtu.be/hoe24aSvLtw $\endgroup$ May 25 at 21:05
  • $\begingroup$ I noticed that you are also a Doctor, based on your handle ;) $\endgroup$ May 26 at 5:49

3 Answers 3

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.

$\endgroup$
2
  • 2
    $\begingroup$ Nice inductive proof. Feels more elegant than the "sum of a set of odd numbers" approach. $\endgroup$
    – fljx
    May 23 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 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.

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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