Pigeonhole principle

1. Give the contrapositive of “If L is handled by finite memory then L has property X.”
   Stuck? Peek at 0.2.3 Proof techniques

   • P ⇒ Q false only when P true, Q false. Contrapositive ¬Q ⇒ ¬P ≡ original. Converse/inverse are NOT.
   • Contradiction: assume ¬S, derive the impossible. Used for “no machine can…” proofs.
   • Induction: base S(n₀) + step S(k) ⇒ S(k+1). Strong induction assumes all S(≤k).
   • One counterexample kills a “for all”. Examples never prove it.

   Read lesson 0.2.3

2. How many functions from a 2-element set to a 3-element set?
   Stuck? Peek at 0.2.2 Functions, relations and equivalence classes

   • Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
   • #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
   • Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
   • Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.

   Read lesson 0.2.2

3. Is “same last letter” on non-empty words an equivalence relation?
   Stuck? Peek at 0.2.2 Functions, relations and equivalence classes

   • Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
   • #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
   • Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
   • Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.

   Read lesson 0.2.2

Your machine has 5 modes. It reads an input of 6 symbols. Before reading and after each symbol, it is in some mode — that’s 7 moments, but only 5 possible modes. Without knowing anything else about the machine, you can be certain it was in the same mode at two different moments. That certainty is the pigeonhole principle, and it is the engine behind proving that finite-memory machines cannot count forever.

How many people must be in a room to guarantee that two share a birth month?

Prediction check

Answer: 13. With 12 people, each could have a different month. With 13, the 12 months are “boxes” and 13 people can’t all be in different boxes.

The principle

It tells you a collision exists, not where. That’s exactly how it is used: “some mode repeats” — we don’t know which, and we don’t need to.

Generalized pigeonhole

If N objects go into k boxes, some box holds at least ⌈N/k⌉ objects (⌈x⌉ = round up). 100 students in 7 sections ⇒ some section has ≥ ⌈100/7⌉ = 15. To guarantee m objects in some box you need (m−1)·k + 1 objects.

The machine version

A machine with n modes reads an input of length m ≥ n. It passes through m + 1 moments (start, after symbol 1, …, after symbol m). Since m + 1 > n, some mode appears twice. Between those two moments the machine read a stretch of input that took it from a mode back to the same mode — a loop. Repeat that stretch and the machine can’t tell the difference: it returns to the same mode again. This is the seed of the “pumping” idea in Phase 2.

How to use it in a proof

1. Identify the objects (moments, numbers, people).
2. Identify the boxes (modes, remainders, months).
3. Show objects > boxes.
4. Conclude two objects share a box, and exploit that.

Putting it together

• n + 1 objects in n boxes force a shared box; N objects in k boxes put at least ⌈N/k⌉ in one.
• An n-mode machine reading at least n symbols must repeat a mode.
• A repeated mode means the input between the repeats is a loop that can be repeated — the seed of the pumping lemma.

Machine with 3 modes {A,B,C} reading "x y z w" (4 symbols → 5 moments)

 moment:   0     1     2     3     4
 mode:     A ─x→ B ─y→ C ─z→ B ─w→ A
                 ▲           ▲
                 └── same mode B at moments 1 and 3
 the stretch "y z" took B back to B  →  a loop:
 reading "x (y z)(y z)(y z) w" passes B, B, B, B ... and ends exactly as before.

We’ve been drawing machines as dots (modes) with arrows (moves). That picture is a directed graph. Next: the vocabulary of graphs — paths, cycles, and which nodes you can reach — which is exactly how we’ll read machine diagrams.

1. NAT

   Minimum number of integers needed to guarantee two have the same remainder mod 10?

   Write your answer before opening the key.

2. NAT

   50 letters are sorted into 8 mailboxes. At least how many letters must some mailbox hold?

   Write your answer before opening the key.

3. MCQ

   A machine with n modes reads an input of length m. A repeated mode is guaranteed whenever:

   1. m ≥ n − 1
   2. m ≥ n
   3. m ≥ n + 1
   4. m ≥ 2n
4. MSQ

   Which conclusions does pigeonhole justify?

   1. Among 367 people two share a birthday (ignoring leap issues beyond 366 days)
   2. Among 3 integers two have the same parity (even/odd)
   3. Among 10 people two were born on the same weekday
   4. Among 7 people two were born on the same weekday

• pigeonhole principle
• generalized pigeonhole ⌈N/k⌉
• moments of a run (m symbols ⇒ m+1 moments)
• repeated mode ⇒ loop

1. Pigeonhole principle?
   Reveal answer

   n+1 objects in n boxes ⇒ some box has at least 2.
2. Generalized pigeonhole: N objects, k boxes?
   Reveal answer

   Some box has at least ⌈N/k⌉.
3. When must an n-mode machine repeat a mode on an input of length m?
   Reveal answer

   When m ≥ n (m+1 moments > n modes).