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.

Comments

topicTopics
academics MCAT study skills SAT medical school admissions expository writing English college admissions GRE GMAT LSAT MD/PhD admissions chemistry math physics ACT writing biology language learning strategy law school admissions graduate admissions MBA admissions creative writing homework help MD test anxiety AP exams interview prep summer activities history philosophy career advice premed academic advice ESL economics grammar personal statements study schedules admissions coaching law statistics & probability PSAT computer science organic chemistry psychology SSAT covid-19 CARS legal studies logic games USMLE calculus parents reading comprehension 1L Latin Spanish dental admissions DAT engineering excel political science French Linguistics Tutoring Approaches chinese research DO MBA coursework Social Advocacy case coaching classics genetics kinematics secondary applications skills verbal reasoning ISEE academic integrity algebra business business skills careers diversity statement geometry medical school mental health social sciences trigonometry 2L 3L Anki EMT FlexMed Fourier Series Greek IB exams Italian MD/PhD programs STEM Sentence Correction Zoom amino acids analysis essay architecture art history artificial intelligence astrophysics athletics biochemistry capital markets cell biology central limit theorem chemical engineering chromatography climate change clinical experience curriculum data science dental school finance first generation student functions gap year harmonics health policy history of medicine history of science information sessions integrated reasoning international students investing investment banking mba meiosis mitosis music music theory neurology phrase structure rules plagiarism presentations pseudocode sociology software software engineering teaching tech industry transfer typology virtual interviews work and activities writing circles