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

Posts: 226
Thanks: 77

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
cjem is online now  
Reply

  My Math Forum > College Math Forum > Number Theory

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 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 © 2018 My Math Forum. All rights reserved.