Parity and pigeonhole

Idea: Plan for the worst case

A guarantee is the number that works against the unluckiest order, not the likely one.

• $n$ items in $k$ boxes with $n>k$: some box holds $2$
• To force $m$ in one box, beat $m-1$ in every box
• The bad spread must be possible

Formula: Pigeonhole

$k(m-1)+1$

Items that force m into one of k boxes: fill every box to m − 1, then take 1 more.

Example: Ties in the dark

A drawer holds $8$ blue, $6$ black and $5$ grey ties, lights off. How many guarantee $2$ of one colour?

1. Worst grab without a pair: one tie of each colour
2. That is $3$ ties, so $3+1=4$

Quick check: When a colour runs short

A bag has $2$ red and $9$ white balls. How many draws guarantee $5$ of one colour?

Common mistake: Answering with the likely case

"Usually $3$ draws are enough" is not a guarantee.

Instead Give the number that beats the unluckiest order, and check every box in the bad spread can really fill.

Idea: Parity rules things out

Odd or even rarely gives the answer, but it rules out half the candidates at once.

• A knight changes square colour on every move
• Each handshake adds $1$ to $2$ counts, so the total is even
• $9$ guests cannot each shake $3$ hands: $9\times 3=27$ is odd

Example: The locker puzzle

$100$ closed lockers. For each $k$ from $1$ to $100$, a student toggles every multiple of $k$. How many end open?

1. Locker $n$ is toggled once per divisor of $n$
2. Divisors pair up as $d$ and $\frac{n}{d}$: an odd count only for squares
3. Squares up to $100$, since $10\times 10=100$: $10$ open

Quick check: 3 cards in 2 suits

How many cards from a $52$ card deck guarantee $3$ cards in each of $2$ different suits?

Idea: Build the worst case aloud

Say "I can take this many without succeeding", then add $1$.

• Check each box in the bad spread has enough items
• Watch the worst case change shape when the target changes
• For parity, name the quantity whose oddness is fixed