Waste less time on Facebook — follow Brilliant.
Back to all chapters

Pigeonhole Principle

If you have 12 pigeons and there are only 11 roosts, then at least one roost will be quite cozy.

Pigeonhole Principle - Problem Solving


In Melinda's messy dresser drawer, there is a jumble of 5 red socks, 7 blue socks, 7 green socks, and 4 yellow socks. If Melinda grabs a big handful of socks without looking at what she's taking, what is the minimum number of socks Melinda has to grab in order to guarantee that she has at least 4 socks of the same color?

A family of \(121\) crows move into a new neighbourhood which has \(12\) identical birdhouses. What is the minimum number of crows that each birdhouse must be able to hold, in order for all the birds to fit?

There are \(22\) people in a party. Calvin, one of the participants of the party, shakes hands with \(18\) friends forgetting about the other three, goes to the washroom to wash his hands, and returns to the party. Then he again shakes hands with \(18\) friends, goes to the washroom, and returns to the party. He repeats this same pattern over and over.

Calvin sits down with some punch immediately after a final round of \(18\) handshakes in which Calvin shakes hands with one final friend who he's randomly managed to neglect all the rest of the evening. Sipping his punch, Calvin realizes that the numbers of handshakes with each of the \(21\) friends are all different. What is the minimum number of times he must return to the party, assuming that he always shakes hands with \(18\) friends after every return?

A theater is inviting \(2670\) total students from various schools to see a movie. Each individual school invited is only allowed to bring at most \(38\) students. If the theater has \(193\) seats in each row, how many rows do they need to set aside for schools in order to guarantee that all students from the same school can be seated in the same row?

Alice, Bob, Candice and David run for school president. There are \(201\) students in the school and each student can vote for only one candidate. The person with the largest number of votes is the winner. If every student votes, what is the minimum number of votes needed for it to be at least possible to win the election?

Details and assumptions

Ties for the winner are not allowed in this election.


Problem Loading...

Note Loading...

Set Loading...