My Math Forum Pigeonhole Principle

 Number Theory Number Theory Math Forum

 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: 283 Thanks: 85 Math Focus: Algebraic Number Theory, Arithmetic 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. Thanks from Maschke

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top