Exercise 3: Proving 5 People Share a Birthday Day-of-Week in a Room of 32 — Possible Solution ==================================================================== SETTING UP THE PIGEONHOLE ARGUMENT ------------------------------ Per this chapter, the generalized pigeonhole principle states: "if n items go into m containers, at least one container holds at least ⌈n/m⌉ items." Here, the "items" are the 32 people, and the "containers" are the 7 possible days of the week their birthday could fall on - n = 32, m = 7. COMPUTING THE GUARANTEED MINIMUM ------------------------------ n / m = 32 / 7 = 4.571... Rounding up (the ceiling function, per this chapter's own notation): ceil(32/7) = ceil(4.571...) = 5 So the generalized pigeonhole principle guarantees that at least one day-of-the-week "container" must hold at least 5 people. WHY ROUNDING UP, SPECIFICALLY, IS THE CORRECT OPERATION HERE ------------------------------ If every one of the 7 days held at most 4 people, the maximum total number of people that could be accounted for would be 7 x 4 = 28 - fewer than the 32 people actually in the room. Since 28 < 32, it's impossible for every day to hold 4 or fewer people; at least one day must hold a 5th person (or more) to account for the remaining people. This is exactly what taking the ceiling of 32/7 captures: 4 people per container isn't enough capacity for all 32, so at least one container needs at least one more. WHY THIS IS A GENUINE PROOF, NOT JUST A LIKELY OUTCOME ------------------------------ This isn't a probabilistic claim about what's likely to happen with random birthdays - it's a guaranteed mathematical consequence of 32 people existing and only 7 possible days for them to be distributed across. No matter how the 32 birthdays happen to be arranged among the 7 days, there is no possible distribution that avoids at least one day having 5 or more people - the pigeonhole principle guarantees this for every possible case, not just probable ones. WHY THIS WORKS AS AN ANSWER ------------------------------ It identifies the items and containers correctly, applies the generalized pigeonhole formula to compute the guaranteed minimum, and explains concretely (via the 7 x 4 = 28 capacity argument) why the result is a genuine guarantee for every possible arrangement, not merely a likely outcome.