Fill every category in the most unhelpful legal way. Once even that arrangement cannot avoid the target, the next object proves the guarantee.
Do not begin with the successful arrangement. Ask:
That value is the failure ceiling. If the available supplies make the target possible, one more object forces success. Otherwise no draw can guarantee an impossible target.
Keep every drawer just below its target.
Seven drawers can hold 4 each: 28 objects without five together. The 29th forces five in a drawer. In general the threshold is k(r−1)+1.
Draw without replacement from a54-card deck:13ordinary ranks with4cards each, plus two different jokers. Take one card per ordinary rank and both jokers to avoid an ordinary-rank pair.
The repeated property concerns the 13 ordinary ranks. The two jokers are one-time escape cards: both can be drawn without repeating an ordinary rank.
The suits do not create separate drawers because the desired match is a repeated rank, not a repeated exact card.
Keep the two jokers separate from the ordinary ranks.
One of each of 13 ordinary ranks plus the two jokers makes a safe draw of 15. A 16th card must repeat an ordinary rank.
There are10balls labeled0,11labeled1,…,19labeled9. Draw without replacement. You may select any four drawn balls and reorder them to read2009; draw order does not matter.
To avoid the complete target, at least one required label must still be short. The most dangerous failure mode is the one with the greatest possible draw.
Compare all ways the required digit collection can fail.
With 145 balls, at most one zero permits 136 draws, no 2 permits 133, and no 9 permits 126. The greatest failure is 136, so 137 guarantees 2009.
Eighteen nonempty boxes contain 64 balls, and every box holds at most 6. The possible occupancies are 1 through 6.
A 64-ball arrangement with largest frequency 4 proves the strengthened guarantee is tight.
An occupancy is the number of balls in a box.
There are six possible occupancies. At most three of each would force exactly three of each in 18 boxes, totaling 63 balls. The actual 64 balls force four boxes with the same occupancy.
Draw without replacement from4red,7yellow,and8black balls. To avoid six of one color, a color may contribute at most 5 balls—but red can contribute only 4.
A category cannot supply more balls than it has.
To avoid six of one color, capacities 4,7,8 permit only 4+5+5=14 safe draws. The 15th forces six. If every capacity is below the target, success is impossible even after drawing all balls.
Each student has cards1,2,3, chooses two different cards and arranges them as a two-digit number. Cards are available again for the next student.
6 outcomes, so 7 students force two equal numbers.
Each person chooses two balls, then replaces both before the next choice; at least two of each type are available. When two balls are considered together, red–blue and blue–red are the same outcome, and same-color pairs are allowed.
Test 23 gives:
Decide whether changing order creates a new outcome.
Two different digits from 1,2,3 make six ordered numbers, so seven choices force a duplicate. Two balls from five colors have 5 same-color and 10 mixed types: 15 unordered outcomes, so 16 force a duplicate.
There are four sock colors with enough of each available. Draw without replacement; a pair is any two socks of the same color, and no sock can belong to two pairs. Left/right sock labels are irrelevant. To avoid ten pairs, keep only nine completed pairs, then add one unpaired sock of each color.
Each of 126 boxes contains an integer number of apples from 120 through 144.
A color may have one leftover sock after its completed pairs.
Nine pairs use 18 socks; four colors allow four additional singles. Thus 22 may still have only nine pairs, while 23 force ten. For apple counts 120–144 there are 25 values, so 126 boxes force six with the same count.
Choose the initial occupied seats so that every remaining empty seat has an occupied seat immediately to its left or right. The27seats form one row, not a circle. What is the fewest initial occupants? One seated person can cover at most a block of three seats: left neighbor, own seat, right neighbor.
Every student has a positive number of books. If all 30 counts were different, the smallest possible total would be:
But the actual total is only 450, so at least two students must have the same number of books.
A seated person covers at most three positions.
Twenty-seven positions need at least nine people; seats 2,5,8,…,26 attain it. Thirty distinct positive book counts total at least 1+…+30=465, so a total of 450 forces a repeated count.
A bag has 3 red, 8 blue, and 9 green balls. What is the least number of blind draws without replacement that guarantees five balls of one color?
This fresh problem has its own checkpoint. Your written explanation is saved for comparison and is not automatically graded.
The greatest failing draw is 3 red + 4 blue + 4 green = 11. Draw 12 forces five blue or five green. Red can never supply five.
Revisit the mission connected to each question.
For each threshold, identify the largest possible failure. Cards:15;digit bag:136;colored balls:14;socks:22. Add one only when success is possible. For the book argument, the least distinct positive total is465;for seat coverage,9occupants suffice.
This certifies that
can build a greatest unsuccessful arrangement, count finite category capacities, and prove that the next object forces a match.
Lesson 23.6 · The Pigeonhole Principle
Solve each item without using the answer shown in an earlier example.
Answers:21;16;137;23;6. Four unlimited categories can hold5each without6together;20+1=21. The card, digit and sock failure ceilings are15,136,22. For126boxes in25occupancy categories, five per category cover only125.