My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Thanks Tree1Thanks
  • 1 Post By cjem
LinkBack Thread Tools Display Modes
September 13th, 2018, 02:20 PM   #1
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.
tardy4daparty is offline  
September 13th, 2018, 04:12 PM   #2
Senior Member
Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

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.
Thanks from Maschke
cjem is offline  

  My Math Forum > College Math Forum > Number Theory

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 08:49 PM
Pigeonhole Principle Solarmew Applied Math 6 May 27th, 2012 07:03 AM
Pigeonhole principle... please help! merlin2222 Algebra 2 June 27th, 2011 02:27 PM
Pigeonhole Principle. deadlyned Number Theory 1 March 12th, 2011 01:34 PM
Pigeonhole principle..please help! merlin2222 Applied Math 0 December 31st, 1969 04:00 PM

Copyright © 2019 My Math Forum. All rights reserved.