0
$\begingroup$

Jerry is shaking hands with a group of people. There are $n \geq 2$ people there. Any person can shake any number of the other peoples' hands, including zero, but any two people can only shake each other's hands once. Shaking hands is a mutual event between exactly two people.

Prove or disprove the claim that there must always be at least two people who shook the same number of hands as each other.

I have two theories for this problem: this is a problem that involves the pigeonhole principle, with there being n-1 holes. Or that it is a problem that involves derangements. I am mainly not sure how to approach the problem.

$\endgroup$
3
$\begingroup$

Go with the pigeon hole proinciple. Each of the $n$ people will have shaken between $0$ and $n-1$ other peoples hands. If someone has shaken $n-1$ hands then they have shaken everyone elses hand & so there cannot be someone who has shaken $0$ hands.

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