The pigeonhole principle: a counting concept with countless applications

academics High School math
By Jack M.

All of our tutors are available to work with any student with broadband Internet access, no matter where you are.The Cambridge Coaching homework help tutors mission is to mentor middle and high school students in mu-2Consider the following questions:

  1. Are there two people in Boston with exactly the same number of hairs on their heads?

  2. You only own red, yellow, and blue socks. You’re pulling socks out of your sock drawer but the room is pitch black and you can’t see their color. What is the minimum number of socks you need to pull to guarantee that you leave your room with a matching pair of socks?

  3. A group of people meet up and some number of them shake hands with each other. Is it possible that every person in the group shook hands with a different number of people? (People can’t shake their own hand).

At first blush, it might seem like these questions require very different approaches to answer. However, at the heart of the solution to each of these problems lies a simple mathematical concept called “the pigeonhole principle.”

The pigeonhole principle states: if n objects are placed into m holes and there are more objects than holes (n > m), then there is at least one hole containing more than one object.

For example, if you place 10 pigeons into 8 holes, at least one of the holes must have more than one pigeon in it: how could you place each pigeon into its own hole when there are fewer holes than pigeons? Another example: if you pick any 5 cards from a standard 52 card deck, then at least 2 of the 5 will have the same suit. You’re putting 5 pigeons (cards) into 4 holes (suits). Note that it’s also possible that more than 2 of the 5 cards share a suit. This is okay. Usually the pigeonhole principle is used to argue that at least 2 objects share some property, even if in fact many more do.  

This concept might seem so intuitive that it doesn’t deserve its own name, but it is ubiquitous in math and computer science and has many far-reaching and unexpected consequences. Often the challenge in applying the pigeonhole principle is realizing which elements of your word problem should be thought of as holes and which should be thought of as pigeons. The most common case is when you are trying to argue that there exist two objects (or mathematical constructs) that share some property. You can then think of the objects as pigeons and the holes as properties. Let’s see how the pigeonhole principle applies to our three opening questions.

Are there two people in Boston with exactly the same number of hairs on their heads? 

Before reading on, think about how you might go about answering this. What are the pigeons and what are the holes? Some googling reveals that the human head has on average about 100,000-150,000 hair follicles on it and even the hairiest among us won’t have more than 500,000. This means that, at most, there are about 500,000 options for how many hairs someone can have: if someone had exactly 1 hair, another had exactly 2 hairs etc. all the way up to 500,000, that only leaves room for 500,000 unique hair counts. Meanwhile, the population of Boston city proper is around 710,000 people. So there simply aren’t enough holes (possible hair counts) for all of the pigeons (Bostonians), and we can conclude that there must be at least two people in Boston with exactly the same number of hairs on their heads.

What about the socks?

Try your hand at the sock puzzle. We have 3 colors and our goal is to find the minimum number of socks such that at least 2 of them share a color. Sound familiar? Think of the colors as holes and the socks as pigeons. If we pick 4 socks, at least 2 of them must share a color in the same way that if we try to put 4 pigeons into 3 holes, at least 2 pigeons must share a hole.

About that handshake…

The handshake problem is a little subtler.  We will argue that when n people meet and some subset of them shake hands, at least 2 of them must have shaken hands with exactly the same number of other people. The holes will correspond to the number of handshakes, and the people will be the pigeons. Each of the n people can take part in anywhere from 0 to n-1 handshakes (remember they can’t shake their own hands). 0 to n-1 is a total of n different numbers of handshakes (for example if n=3, then each person can shake a total of 0, 1, or 2 hands). We also have n people, so at first it seems like we have just enough holes for our pigeons. The extra layer here is to notice that if there is anybody in the group that shook n-1 hands (everybody but themselves), then nobody in the group could have shaken 0 hands. So either nobody shook 0 hands or nobody shook n-1 hands. This brings us down to only n-1 different numbers of possible handshakes for the group and n people. So, the pigeonhole principle applies and says that there must be at least 2 people who took part in exactly the same number of handshakes. Our answer to question #3 is that it is impossible for everyone in a group to shake hands with a different number of people.

The pigeonhole principle is a great example of how even simple insights can have far-reaching implications.

Jack graduated summa cum laude and Phi Betta Kappa from Tufts with a BA in Mathematics. After conducting research in cognitive neuroscience at MIT, he earned his Phd in Theoretical Computer Science at Harvard.

Comments

topicTopics
academics study skills MCAT medical school admissions SAT expository writing college admissions English MD/PhD admissions strategy writing LSAT GMAT GRE physics chemistry math biology graduate admissions academic advice ACT interview prep law school admissions test anxiety language learning premed MBA admissions career advice personal statements homework help AP exams creative writing MD study schedules computer science test prep Common Application summer activities history mathematics philosophy organic chemistry secondary applications economics supplements research 1L PSAT admissions coaching grammar law psychology statistics & probability legal studies ESL CARS SSAT covid-19 dental admissions logic games reading comprehension engineering USMLE calculus PhD admissions Spanish mentorship parents Latin biochemistry case coaching verbal reasoning DAT English literature STEM excel medical school political science skills AMCAS French Linguistics MBA coursework Tutoring Approaches academic integrity chinese letters of recommendation Anki DO Social Advocacy admissions advice algebra artificial intelligence astrophysics business cell biology classics diversity statement gap year genetics geometry kinematics linear algebra mechanical engineering mental health presentations quantitative reasoning study abroad technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay art history athletics business skills careers cold emails data science dental school finance first generation student functions information sessions international students internships logic networking poetry resume revising science social sciences software engineering tech industry trigonometry writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function freewriting genomics graphing harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system neurology neuroscience object-oriented programming office hours operating systems