The Pigeonhole Principle | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 5.3 Free with a free account

The Pigeonhole Principle

Discrete Mathematics · Chapter 5: Counting Methods and Basic ProbabilitySection 5.3 · lesson 29 of 879 min · free with a free account

← The Addition and Multiplication RulesNext lesson: Permutations and Ordered Arrangements →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Why overlaps are guaranteed in finite collections.

  • State and prove the simple pigeonhole principle
  • Use the generalized form to get a numeric floor
  • Solve the socks and shared-birthday problems
  • Separate a certainty from a probability threshold

Transcript

Everything said in the video, section by section (1,355 words). Read along, or search it.

Counting Methods and Basic Probability

The Pigeonhole Principle

This section is about the pigeonhole principle, one of the simplest and most widely used ideas in combinatorics. We'll state it in its basic form, then extend it to a general version that gives an actual number. And we'll work through the two classic illustrations every treatment of the topic reaches eventually. Socks in a drawer, and shared birthdays.

The Opening Problem

150 Records, 100 Buckets

A hash table stores records by computing a hash of each record's key, and using the result to pick one of a fixed number of buckets. Suppose a table has one hundred buckets, and one hundred fifty records are inserted. No matter how carefully the hash function is designed, even if it spreads keys perfectly uniformly at random, at least one bucket is guaranteed to hold more than one record. That's not a statement about bad luck, or a poorly chosen hash function. It's a plain counting fact. It holds for any hash function at all, as long as more records go in than there are buckets to receive them.

Theorem - Simple Form

More Items Than Containers

The principle is named for a homely image. Pigeons settling into the pigeonholes of a mail sorting cabinet. But the statement is about any items, sorted into any containers. If n items are placed into m containers, and n is greater than m, then at least one container holds more than one item. The proof is by contradiction. Suppose instead that every one of the m containers holds at most one item. Then the total number of items is at most m times one, which is m. But n items were placed in total, and n is greater than m. So the total is at most m, and also greater than m, which is impossible. So the assumption was false. Some container holds more than one item.

Back to the Hash Table

A Collision Exists - Somewhere

Apply that to the opening scenario. The one hundred fifty records are the items, and the one hundred buckets are the containers. Since one hundred fifty is greater than one hundred, some bucket receives more than one record. That's a hash collision, however the hashing is done. But notice what the principle doesn't say. It guarantees a collision exists somewhere. It says nothing about which bucket. And it says nothing about how many records share that bucket, beyond more than one. The generalized form sharpens exactly that second point.

Theorem - Generalized Form

A Numeric Floor on the Fullest Container

The simple form only promises more than one, which is a weak guarantee once n is much larger than m. The generalized version gives a numeric floor on how full the fullest container must be. It uses the ceiling function. The ceiling of x is the smallest integer greater than or equal to x. So the ceiling of four point one is five, and the ceiling of four is just four. Here's the generalized principle. If n items are placed into m containers, then at least one container holds at least the ceiling of n over m items. Unlike the simple form, that floor grows with how much n exceeds m.

Proof - By Contradiction

Every Container Under the Floor?

The proof is again by contradiction. Suppose every container holds at most the ceiling of n over m, minus one items. The ceiling of any number is less than that number plus one. So the ceiling of n over m, minus one, is less than n over m. Then the total across all m containers is at most m times that, which is less than m times n over m. And that's just n. So the total is strictly less than n. But all n items were placed somewhere, so the total is exactly n. That's a contradiction. So some container must hold at least the ceiling of n over m items.

Worked Example 1

41 Records, 10 Buckets

Here's a worked example. A hash table has ten buckets, and forty-one records are inserted. What's the fewest records the busiest bucket is guaranteed to hold? Apply the generalized form directly. The ceiling of forty-one over ten is the ceiling of four point one, which is five. So at least one bucket is guaranteed to hold at least five records. And that bound is tight. The records can be spread as nine buckets holding four each, and one bucket holding five. So no bucket ever needs to reach six. The picture shows that most even spread. The dashed line marks four per bucket. Ten buckets at four each hold only forty, one short of forty-one. So keeping every bucket at four or below is impossible. The forty-first record, shown in red, forces one bucket up to five.

Checking in Code

The Same Bound, Computed

The same bound can be checked in code, using Python's built-in ceiling function instead of working it out by hand. With m equal to ten and n equal to forty-one, the ceiling of n over m prints five. Then the code confirms the contradiction step. If every bucket held at most four, the most they could hold together is ten times four, which is forty. And forty is less than forty-one, so the check prints true. No such spread exists.

Worked Example 2

Socks in a Dark Drawer

Now a classic. A drawer contains socks in four colors, unsorted. It's too dark to tell the colors apart, except by pulling socks out and comparing them. What's the minimum number of socks that must be pulled, to guarantee at least one matching pair? Treat the four colors as containers, and each sock pulled as an item. Pulling four socks isn't enough to guarantee a match. It's entirely possible to pull exactly one sock of each color, with no repeats at all. But a fifth sock forces a repeat. With five socks and four colors, five is greater than four, so the simple principle guarantees some color is repeated. The answer is five socks.

Shared Birthdays

A Guarantee, Not a Probability

Shared birthdays make a second classic example. It's a guarantee, not a probability. Treat each of the three hundred sixty-six possible birthdays, allowing for February twenty-ninth, as a container. Then a group of three hundred sixty-seven people is guaranteed to contain two people with the same birthday. That's a certainty, probability exactly one. This number is often confused with the famous birthday paradox, which asks a different question. How many people are needed before a shared birthday becomes more likely than not? The answer to that is only about twenty-three. But it comes from a probability computation, covered elsewhere in this chapter, not from the pigeonhole principle. The pigeonhole principle only ever produces certainties, usually at the cost of needing a much larger group. And in cryptography, the birthday attack on hash functions is named for that same probabilistic reasoning. It finds a likely collision far sooner than the pigeonhole certainty would need.

Comparison

Simple Versus Generalized

This table sets the two forms side by side. The simple form says that n greater than m forces some container to hold more than one item. The generalized form says some container holds at least the ceiling of n over m. The simple form guarantees a repeat exists, with no numeric floor beyond that. The generalized form gives a floor that scales with n over m. So the extra strength matters most when n is much larger than m, and a meaningful bound on the busiest container is needed. In this section, five socks and four colors guarantee a pair. And forty-one records in ten buckets guarantee a bucket of at least five.

Takeaways

Counting Forces a Collision

To summarize. The simple pigeonhole principle says n items in m containers, with n greater than m, force some container to hold more than one item. The generalized form sharpens this to a floor, the ceiling of n over m. And that floor is tight. Items can always be spread to avoid exceeding it, but never to stay under it. Both are proved by contradiction. Assume every container stays under the bound, and the total falls short of n. Guaranteed hash collisions and guaranteed shared birthdays are both certainty results. They're distinct from probability thresholds, like the birthday paradox's twenty-three. Here's something to think about. A developer has one hundred buckets and one hundred fifty items. They say pigeonhole guarantees a huge cluster that's slowing down lookups. Using the generalized form, what floor does this scenario actually guarantee? And does the developer's conclusion claim more than the theorem supports?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About The Pigeonhole Principle

What is the pigeonhole principle and how do you prove it?
If n items are placed into m containers and n > m, at least one container holds more than one item. The proof is by contradiction. If every container held at most one item, the total would be at most m, which contradicts having n > m items in total.
How do you use the generalized pigeonhole principle to find the fullest container?
Compute \lceil n/m \rceil. If n items go into m containers, some container holds at least that many items. For example, 41 records in 10 buckets gives \lceil 41/10 \rceil = \lceil 4.1 \rceil = 5. So some bucket holds at least 5 records, and a spread of nine buckets with 4 and one with 5 shows the bound is tight.
How many socks must you pull to guarantee a matching pair from a drawer with four colors?
You must pull five socks. Treat the four colors as containers and the socks as items. Four socks could be one of each color with no match. A fifth sock gives 5 > 4, so the simple pigeonhole principle forces at least one color to repeat.
Is the pigeonhole principle the same as the birthday paradox?
No. The pigeonhole principle gives a certainty, while the birthday paradox is a probability threshold. With 366 possible birthdays, 367 people are guaranteed to include a shared birthday. The paradox asks when a match becomes more likely than not, which happens at about 23 people, and that comes from a probability computation.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →