September 13th, 2018, 03:20 PM  #1 
Newbie Joined: Sep 2018 From: United States Posts: 1 Thanks: 0  Pigeonhole Principle
you were one of four people attending a meeting. a round of handshakes took place. we do not know how many hands each person shook. However, regardless of the number of hands each person shook there must be two people who shook the same number of hands. Suppose we do not know whether everyone shook at least one hand. Write up a pigeonhole principle to show that there must be two people who shook the same number of hands. 
September 13th, 2018, 05:12 PM  #2 
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 286 Thanks: 88 Math Focus: Number Theory, Algebraic Geometry 
Call the people $A, B, C, D$ and let $f: \{A,B,C,D\} \to \mathbb{Z}$ be the function mapping each person to the number of hands they shook. The problem is to show that $f$ is not injective. Clearly $\operatorname{Im}(f) \subseteq \{0,1,2,3\}$. Notice that $0$ and $3$ can't both be in $\operatorname{Im}(f)$ (indeed, $3$ being an element of $\operatorname{Im}(f)$ means someone shook everyone else's hand, and so no one shook $0$ hands) and so $\operatorname{Im}(f) \leq 3 < \{A,B,C,D\}$. This implies that $f$ is not injective.


Tags 
handshakes, number theory, pigeonhole, principle, quantitative reasoning 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pigeonhole Principle!  Jet1045  Number Theory  16  August 9th, 2016 09:49 PM 
Pigeonhole Principle  Solarmew  Applied Math  6  May 27th, 2012 08:03 AM 
Pigeonhole principle... please help!  merlin2222  Algebra  2  June 27th, 2011 03:27 PM 
Pigeonhole Principle.  deadlyned  Number Theory  1  March 12th, 2011 02:34 PM 
Pigeonhole principle..please help!  merlin2222  Applied Math  0  December 31st, 1969 04:00 PM 