Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

at a party, 25 guests mingle and shake hands. prove that at least one guest must have shaken hands with an even number of guests.

share|improve this question
1  
Might help: The Handshaking theorem: en.wikipedia.org/wiki/Handshaking_lemma –  Sujaan Kunalan Jun 20 '13 at 3:49

1 Answer 1

up vote 5 down vote accepted

HINT: Number the guests $1$ through $25$. Let $a_k$ be the number of guests with whom guest $k$ shook hands. Suppose that the numbers $a_1,a_2,\dots,a_{25}$ are all odd.

  • Is $\sum_{k=1}^{25}a_k$ odd, or is it even?
  • Each handshake involves two people, so each handshake is counted twice in $\sum_{k=1}^{25}a_k$, once for each of the two people involved. What does this imply about whether $\sum_{k=1}^{25}a_k$ is odd or even?
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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