Day 16 — Types Analogy & Pigeonhole Principle

Day 16 — Types Analogy & Pigeonhole Principle

Day 44 — Types/sets analogy

Stage IV · concept day
Goal: Treat types as sets of values (working analogy); connect product and sum types to \(\times\) and \(\sqcup\); model option/maybe; view predicates as subsets; separate specification from implementation—no coding labs.

Why this matters

Type systems are the industry face of sets, products, unions, and functions \(A\to B\). Thinking “what values inhabit this type?” prevents whole classes of bugs. Option types are “set plus a missing tag”; records are products; enums with data are disjoint unions. This day is conceptual glue between Stage IV math and programming languages—not a tutorial in any one language.

Theory

Types as sets of values (working model)

A type \(T\) determines a set of inhabiting values \([\![T]\!]\) (denotation).
Examples (idealized):

Type idea	Set of values
Bool	\(\{\mathsf{true},\mathsf{false}\}\)
Unit / ()	\(\{ \ast \}\) one point
Void / Never	\(\emptyset\)
Nat	\(\mathbb{N}\)
Byte	\(\{0,\ldots,255\}\)

Caveats: real languages have nontermination, mutability, subtyping, and infinite values (streams). The set model is a map, not the full semantics. Still invaluable.

Product types

A product type \(A \times B\) (struct with fields of types \(A\) and \(B\); tuple) has values that are pairs:
\[[\![A \times B]\!] = [\![A]\!] \times [\![B]\!].\]
\(n\)-ary records ≈ \(n\)-fold products.
Pattern match / field access ≈ projections \(\pi_i\).

Sum types (disjoint union)

A sum type \(A + B\) (enum / variant / tagged union):
\[[\![A + B]\!] = [\![A]\!] \sqcup [\![B]\!] = (\{0\}\times[\![A]\!]) \cup (\{1\}\times[\![B]\!]).\]
Values are either left \(A\) or right \(B\), tagged so the cases do not smash when \([\![A]\!]\cap[\![B]\!]\neq\emptyset\).

Examples: enum Result { Ok(T), Err(E) }; Left/Right; JSON oneOf.

Function types

\([\![A \to B]\!]\) idealized as the set of all functions \([\![A]\!]\to[\![B]\!]\), size \(|B|^{|A|}\) when finite.
In total functional languages, closer to math functions; in general languages, includes partial/nonterminating “functions.”

Option / Maybe

\[\mathsf{Option}(A) \cong A + 1\]
where \(1\) is unit type (“None”).
Values: \(\mathsf{Some}(a)\) for \(a\in[\![A]\!]\), or \(\mathsf{None}\).

Models missing data without null conflation: \([\![A]\!]\cup\{\mathsf{null}\}\) is a sum if null ∉ \(A\), but historically untagged null was unsafe.

Predicates as subsets

A predicate \(P\) on \(A\) defines \(\{ x\in [\![A]\!] : P(x) \}\)—a refinement / subset type idea.
Examples: { n: Nat | n > 0 }, sorted arrays as subset of arrays.
Dependent/refinement type systems make this static; in ordinary languages, it lives in docs and runtime checks.

Specs vs implementation

• Specification: mathematical relation/predicate on inputs-outputs (e.g. \(\forall x,\; f(x)^2 = x\) on nonnegatives for sqrt).
  
• Implementation: particular algorithm/function inhabiting a type \(A\to B\) claimed to satisfy the spec.

Multiple implementations may share a type and even a spec (quicksort vs mergesort: both \(List\to List\) sorted permutation).
Type correctness ≠ full functional correctness—types are coarse specs.

Subtyping (awareness)

\(S\) subtype of \(T\) suggests \([\![S]\!]\subseteq[\![T]\!]\) (simplified).
Variance rules for \(A\to B\) are subtle (contravariance in \(A\))—awareness only.

Algebra of types (arithmetic analogy)

Rough finite counts:

• \(|A\times B| = |A|\cdot|B|\)
  
• \(|A+B| = |A|+|B|\)
  
• \(|A\to B| = |B|^{|A|}\)
  
• \(|\mathsf{Option}(A)| = |A|+1\)

This is why people write type algebra \(A\cdot B\), \(A+B\), \(B^A\).

Recursive types (awareness)

List(A) ≅ 1 + A × List(A) — least fixed point; matches structural induction Day 32.

Worked examples

Example 1 — Bool

Two values; not: Bool → Bool is a function on a \(2\)-set; \(2^2=4\) possible truth functions.

Example 2 — Pair

(Int, Bool) has values like (3, true); projections.

Example 3 — Either

Result<String, ErrorCode>: success string or error—not both, not neither.

Example 4 — Option

Option<User>: logged-in user or absent—force case analysis.

Example 5 — Predicate subset

Even integers \(\subset \mathbb{Z}\); type Even as refinement.

Example 6 — Spec vs type

Type of sort: List[int] → List[int]. Spec: output sorted multiset-equal to input. Type alone allows reverse or constant list.

Example 7 — Void

No values; a function Void → A is unique (empty function) if allowed—logical ex falso vibe.

Example 8 — Unit

One value; A → Unit has one total function (ignore input)—void returning unit.

Example 9 — Counting

Byte → Bool has \(2^{256}\) mathematical functions—not all written as programs.

Example 10 — Sum not union

Untagged Int ∪ Bool if both encode as bits can confuse; tags disambiguate.

Example 11 — Product of options

Option(A)×Option(B) vs Option(A×B): different—\((None, Some(b))\) vs missing pair.

Example 12 — JSON schema

object with required fields ≈ product; enum ≈ sum of units; optional field ≈ option.

Example 13 — List recursion

[] or cons(h,t) matches \(1 + A\times L\).

Example 14 — Pipeline types

\(f:A\to B\), \(g:B\to C\) compose when types match—Day 42 with type-checker enforcement.

Exercises

1. Give \([\![Bool]\!]\), \([\![Unit]\!]\), idealized \([\![Byte]\!]\).
   
2. Explain why \(A+A \not\cong A\) in general as types/sets.
   
3. Write \(\mathsf{Option}(A)\) as a sum.
   
4. How many values does Bool × Bool have? Bool + Bool?
   
5. How many mathematical functions Bool → Bool?
   
6. Why is null dangerous as untagged inhabitant of every type?
   
7. Distinguish type of sort from its full spec.
   
8. Model a coin-flip outcome as a sum type.
   
9. Model a 2D point as a product.
   
10. Option(Option(A)) vs Option(A)—different? Give values.
    
11. Translate: “function that may fail” as \(A\to (B+E)\).
    
12. List recursive equation for binary trees.
    
13. If \(|A|=2\), \(|B|=3\), compute \(|A\times B|\), \(|A+B|\), \(|A\to B|\).
    
14. Spec: f is inverse of g—write with composition.
    
15. Subset type: positive integers as \(\{n\in\mathbb{Z}: n>0\}\).
    
16. Why \(|A\to B| = |B|^{|A|}\) matches function counting Day 41?
    
17. Explain product vs sum for “name and age” vs “name or age.”
    
18. Is every element of \(A\to B\) (math) a possible program? Why not (countability)?
    
19. Model HTTP method as a finite sum of units (GET+POST+…).
    
20. Result type: show map as a function \((A\to B)\to (A+E)\to(B+E)\) conceptually.
    
21. Compare \(A\times(B+C)\) and \((A\times B)+(A\times C)\)—isomorphic?
    
22. Spec vs impl: two different algorithms inhabiting same type and spec.
    
23. What set is the denotation of an empty enum?
    
24. Explain tagging: why \(\{0\}\times A \cup \{1\}\times B\) not just \(A\cup B\).
    
25. One paragraph: how Stage IV sets/products/sums appear in the type system you use most.

CS connection

• Static types catch \(\in\) errors before runtime.
  
• Algebraic data types = products + sums + recursion.
  
• Null safety / option types = explicit sums.
  
• API design: product request bodies; sum error codes.
  
• Formal verification strengthens types toward full specs.
  
• Generics ≈ families of sets indexed by types (parametricity awareness).

Common pitfalls

Pitfall	What to do instead
Types = full specs	Types are coarse invariants
Union vs tagged sum	Prefer tagged for safety
Option(A×B) vs product of options	Different shapes
Ignoring nontermination	Set model is partial truth
Counting programs as all functions	Only countable programs
Forcing one language’s syntax	Keep conceptual

Checkpoint

• Types as sets: examples
  
• Product ↔︎ \(\times\), sum ↔︎ \(\sqcup\)
  
• Option as \(A+1\)
  
• Predicate as subset
  
• Spec vs type vs implementation
  
• Type arithmetic for finite sizes
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — ADT equations as set equations

Solving \(L = 1 + A\times L\) in finite sets only for free when infinite structures allowed—lists are the least fixed point of \(F(X)=1+A\times X\) in domain theory/set theory with infinity. Finite approximations: lists of length \(\le n\).

Homomorphisms (awareness)

A function \(h: List(A)\to B\) is determined by \(h(\mathrm{nil})\) and a step \(A\times B\to B\) (fold). Structural recursion = unique map out of an initial algebra—vocabulary for later PL theory.

Specs layered

Layer	Example
Type	int → int
Refinement	maps nonneg to nonneg
Full contract	\(f(n)=n(n+1)/2\) for \(n\ge 0\)
Complexity	\(O(1)\) arithmetic ops

Types catch layer 1; tests approximate lower layers; proofs cover contracts.

More worked examples

Example 15 — Either count
\(|A+B|=|A|+|B|\) with tags; if untagged union and \(A,B\) overlap, count less.

Example 16 — Callback type
\((A\to B)\to C\) as nested function type—set of functionals.

Example 17 — Maybe map
\(\mathrm{map}: (A\to B)\to (A+1)\to(B+1)\).

Example 18 — Void absurd
No closed term of type Void in total languages—empty set.

Additional exercises

26. Count values of Bool → Option(Bool).
    
27. Isomorphism sketch: \(A\times(B+C)\cong (A\times B)+(A\times C)\).
    
28. Spec for max: List[int]→int including empty-list behavior as Option.
    
29. Explain subtyping Cat ⊆ Animal vs function variance one sentence.
    
30. Write denotations for a tiny enum enum Color { R, G, B }.

Extended practice workshop

Denotation drills

1. \([\![Bool]\!]\), \([\![Unit]\!]\), \([\![Void]\!]\)
   
2. \([\![Bool\times Bool]\!]\) count
   
3. \([\![Bool+Bool]\!]\) count
   
4. \([\![Bool\to Bool]\!]\) count
   
5. \([\![Option(Byte)]\!]\) count idealized

Modeling drills

6. Product type for {x: int, y: int}.
   
7. Sum type for success/error.
   
8. Option for missing user.
   
9. Result[T,E] as sum.
   
10. Recursive list equation.

Spec vs type

11. Type of sort vs full sort contract.
    
12. Type of sqrt vs domain restriction.
    
13. Two algorithms same type and contract.
    
14. Type-correct but wrong program example (English).

Algebra

15. \(|A\times(B+C)|\) vs \(|(A\times B)+(A\times C)|\)
    
16. \(|A\to B\times C|\) vs \(|(A\to B)\times(A\to C)|\)
    
17. \(Option(A\times B)\) vs \(Option(A)\times Option(B)\)—compare

CS design

18. Why tagged unions beat untagged null.
    
19. JSON schema object ≈ product; oneOf ≈ sum.
    
20. API: product request body; sum error codes.

Layer cake

full proof of contract
        ↑
   tests / property tests
        ↑
 refinement types (optional)
        ↑
    static types  ← you are here often
        ↑
      raw bits

Synthesis

Types are sets of values with operations, and type constructors are set constructions: product \(\times\), sum \(+\), function space \(A\to B\), option \(A+1\). Static types catch a slice of bugs; full contracts (sortedness, bounds) are predicates—subsets of the typed value space. This day is conceptual glue between Stage IV sets and real programming languages—not a coding lab.

Denotation dictionary

Type idea	Set-theoretic denotation (idealized)
Bool	\(\{0,1\}\) or \(\{\mathsf{tt},\mathsf{ff}\}\)
Unit	\(1=\{\ast\}\)
Void / never	\(0=\emptyset\)
\(A\times B\)	cartesian product
\(A+B\)	disjoint union \(A\sqcup B\)
\(A\to B\)	set of functions
Option(A)	\(A+1\)
List(A)	\(\bigcup_n A^n\) (or initial algebra awareness)

More worked examples

Example — Counts.
\(|Bool\times Bool|=4\), \(|Bool+Bool|=4\), \(|Bool\to Bool|=4\). Same cardinality, different structure (pairing vs tagging vs maps).

Example — Option vs nullable.
Option(A) forces a tag: \(\mathsf{None}\) or \(\mathsf{Some}(a)\). Untagged null confuses “no value” with a value that happens to be null-ish—sum types beat untagged bottoms.

Example — Spec finer than type.
Type of sort: List[Int] → List[Int]. Contract: output permutation of input and nondecreasing. Many type-correct functions violate the contract.

Example — Distributivity iso.
\(A\times(B+C)\cong (A\times B)+(A\times C)\): a pair of an \(A\) and a tagged \(B\) or \(C\) is a tagged pair. Counts match: \(|A|(|B|+|C|)=|A||B|+|A||C|\).

Example — Function into product.
\(A\to(B\times C)\cong (A\to B)\times(A\to C)\): giving both components separately. Curry: \(A\times B\to C \cong A\to(B\to C)\) (exponential).

Extra exercises (synthesis)

31. Idealized count: \(|Byte\to Bool|\) if \(|Byte|=256\).
    
32. Write denotation of Result[T,E] as a sum.
    
33. Why \(Option(A\times B)\not\cong Option(A)\times Option(B)\) (counterexample elements).
    
34. Spec: div: Int × Int → Option(Int) for division by zero—type vs total function on pairs with nonzero second.
    
35. Explain subtyping \(A\subseteq B\) for values vs variance of \(A\to C\) (contravariance awareness in one sentence).
    
36. JSON: object fields ≈ product; oneOf ≈ sum—give a tiny schema example in English.

Spec vs type checklist

Layer	Catches
Type \(f:A\to B\)	Wrong shape of data
Predicate subset \(P\subseteq A\)	Domain restrictions
Full Hoare contract	Pre/post relationships
Tests	Some counterexamples to \(\forall\)

Types are not proofs of full correctness—but they are set-level invariants the compiler checks. Tomorrow: forcing collisions and crowded holes with the pigeonhole principle.

Tomorrow

Day 45 — Pigeonhole principle. Basic + generalized; Dirichlet; collisions, birthday bound, hair/friends, Erdős–Szekeres statement, modular pigeon.

---

Day 45 — Pigeonhole principle

Stage IV · concept day
Goal: State and apply the basic and generalized pigeonhole principles; use Dirichlet’s form; prove collision, birthday-bound, and modular consequences; know Erdős–Szekeres as a statement; connect to hashing and resource contention.

Why this matters

If more keys than slots, collisions must exist—not “might if unlucky.” Pigeonhole is the finite counting engine behind hash collisions, compression limits, duplicate detection, and many existence proofs without construction. It is elementary and extremely reusable.

Theory

Basic pigeonhole principle (PHP)

If \(n+1\) pigeons are placed into \(n\) holes, then at least one hole contains at least two pigeons.

Set form. Any function \(f: A\to B\) with \(A,B\) finite and \(|A| > |B|\) is not injective: \(\exists a_1\neq a_2\) with \(f(a_1)=f(a_2)\).

Generalized PHP

If \(n\) pigeons go into \(k\) holes, then some hole has at least \(\bigl\lceil n/k \bigr\rceil\) pigeons.

Proof. If every hole had at most \(\lceil n/k\rceil - 1\) pigeons, total
\[\le k\bigl(\lceil n/k\rceil - 1\bigr) < n\]
(standard ceiling argument). Contradiction. \(\square\)

Contrapositive / dual

If each hole has at most \(m\) pigeons, then number of pigeons \(\le k m\).
If you need to avoid \(m+1\) in one hole, you can place at most \(k m\) pigeons.

Dirichlet’s principle

Often the same as PHP; historically used for approximation: among \(N+1\) reals, two are close, etc.
Dirichlet approximation awareness: for real \(\alpha\) and integer \(Q\), exist integers \(p,q\) with \(1\le q\le Q\) and \(|q\alpha - p| \le 1/Q\).

Proof pattern

1. Identify pigeons (objects).
   
2. Identify holes (classes / buckets / residues / pigeonholes).
   
3. Apply \(|A|>|B|\) or generalized count.
   
4. Conclude existence of a crowded hole—translate back to the claim.

Applications catalog

Domain	Pigeons	Holes	Conclusion
Hashing	keys inserted	buckets	collision if more keys than buckets
Birthdays	people	\(365\) days	\(\ge 2\) share if \(366\) people
Hair	people in city	hair counts \(0..M\)	two same count if people \(> M+1\)
Friends	people at party	friend-count \(0..n-1\)	careful: \(0\) and \(n-1\) exclusive
Sequences	…	…	mono subsequence (Erdős–Szekeres)
Modular	\(n+1\) integers	residues mod \(n\)	two congruent mod \(n\)
Socks	socks drawn	colors	guarantee a pair

Birthday bound (collision probability lite)

PHP is worst-case guarantee (\(366\) people).
Probabilistic birthday: among \(k\) random people, \(P(\text{collision})\approx 1 - e^{-k(k-1)/(2\cdot 365)}\).
\(k \approx \sqrt{2\cdot 365\ln 2}\approx 23\) for \(\sim 50\%\) chance.
Hashing: collisions likely when \(k \sim \sqrt{n}\) for \(n\) buckets—not only at \(k=n+1\).
Today: know the bound/statement; deep probability Stage VIII.

Erdős–Szekeres (statement)

Any sequence of more than \((a-1)(b-1)\) distinct numbers has either an increasing subsequence of length \(a\) or a decreasing subsequence of length \(b\).
Proof idea (awareness): map each position to (length of longest inc ending here, longest dec ending here); pigeons into \((a-1)\times(b-1)\) grid if both bounds violated—injection.
Apply PHP on pairs.

Modular pigeon

Among \(n+1\) integers, two have difference divisible by \(n\) (same residue mod \(n\)).
Among any \(n\) integers, either one divisible by \(n\) or two with difference divisible by \(n\)—related.

Non-constructive existence

PHP proves existence of a collision/class without naming which hole—typical non-constructive pattern (Day 30).

Worked examples

Example 1 — Classic

\(367\) people: two share a birthday (ignore leap for \(365\), or use \(366\) holes).

Example 2 — Generalized

\(100\) pigeons, \(9\) holes: some hole \(\ge \lceil 100/9\rceil = 12\).

Example 3 — Hash

\(17\) keys, \(16\) buckets: collision exists.

Example 4 — Socks

\(3\) colors; to guarantee a pair, draw \(4\) (worst \(3\) different +1).

Example 5 — Mod \(n\)

\(11\) integers: two congruent mod \(10\).

Example 6 — Difference

Those two differ by multiple of \(10\).

Example 7 — Hair

If hair count \(\le 200000\), then in a city of \(200001\) people without bald edge cases… two same number.

Example 8 — Friends graph

At a party of \(n\ge 2\) people, two have the same number of friends at the party (graph degree PHP with care that degrees in \(\{0,\ldots,n-1\}\) cannot use both \(0\) and \(n-1\)).

Example 9 — Compression

More than \(2^n\) files of length \(>n\) mapping into \(n\)-bit hashes: collision (actually any map from larger set). Lossless maps cannot shrink all strings (Day 41).

Example 10 — Sequence

Among \(5\) numbers, either increasing subseq of length \(3\) or decreasing of length \(3\) (ES with \(a=b=3\), \((2)(2)=4\), need \(5\)).

Example 11 — Hands

\(13\) people, \(12\) months: two same birth month. Generalized: \(25\) people ⇒ some month has \(\ge 3\) (\(\lceil 25/12\rceil=3\)).

Example 12 — Functions

\(f:\{1,\ldots,m\}\to\{1,\ldots,n\}\), \(m>n\): not injective.

Example 13 — Subset sums (classic)

Among \(n+1\) subsets? Different: any \(n+1\) integers from \(\{1,\ldots,2n\}\) includes two with one dividing the other—or standard subset-sum PHP on prefixes mod \(n\).
Prefix sums \(s_k = a_1+\cdots+a_k\); if some \(s_k\equiv 0\pmod n\) done; else \(n\) prefixes into \(n-1\) nonzero residues ⇒ two equal mod \(n\) ⇒ difference (subarray) \(0\bmod n\).

Example 14 — Birthday probability order

\(k=23\) vs PHP \(k=366\): different questions (likely vs certain).

Exercises

1. State basic and generalized PHP.
   
2. Prove generalized PHP by contradiction.
   
3. Show among any \(11\) integers two have same last digit.
   
4. How many socks to guarantee \(3\) of the same color among \(4\) colors?
   
5. \(50\) students, grades \(0..100\): two same grade?
   
6. Minimum students to guarantee some grade earned by \(\ge 3\)?
   
7. Hash table size \(1024\); how many keys force a collision?
   
8. Explain birthday paradox vs PHP in two sentences.
   
9. Prove: among any \(n+1\) integers two differ by multiple of \(n\).
   
10. Prefix sum argument: any sequence of \(n\) integers has nonempty consecutive subseq sum divisible by \(n\) (Example 13).
    
11. Party of \(6\) people: show two have same number of friends at party (degrees).
    
12. ES: verify that \(5\) distinct reals have mono subseq of length \(3\). Find a sequence of \(4\) without inc or dec length \(3\).
    
13. Prove no injective \(f:\{0,1\}^8 \to \{0,1\}^7\).
    
14. City of \(1\) million; max hair \(200\)k—conclude.
    
15. Generalized: \(n\) holes, want some hole \(\ge r\); how many pigeons needed?
    
16. If \(9\) holes each \(\le 5\) pigeons, max pigeons?
    
17. CS: why are hash collisions inevitable at large load without perfect hashing?
    
18. Cards: how many to guarantee \(2\) aces? (Not pure PHP—hypergeometric; skip or pure: guarantee \(2\) of same suit from \(4\) suits.)
    
19. Guarantee \(5\) of one suit: compute.
    
20. Show any set of \(5\) points in a unit square has two at distance \(\le \sqrt{2}/2\) (divide into \(4\) squares)—classic geometry PHP.
    
21. Dirichlet approx: state the theorem.
    
22. Prove: among any \(6\) people, \(3\) mutual friends or \(3\) mutual strangers is Ramsey \(R(3,3)=6\)—harder; state only if curious.
    
23. Infinite PHP awareness: infinite pigeons finite holes ⇒ some hole infinite.
    
24. Constructive vs not: PHP finds existence of collision—does it give an algorithm to find it? (Scan.)
    
25. Design a PHP proof for: any graph with more edges than… invent a simple claim.

CS connection

• Hash tables: load factor; birthday-bound collisions.
  
• Checksums: small digest ⇒ collisions exist among enough messages.
  
• Load balancing: \(n\) tasks \(k\) servers—some server \(\ge\lceil n/k\rceil\).
  
• Time/space: pigeon on states in cycles (Floyd cycle—related).
  
• Compression: cannot map more messages injectively into fewer bits.
  
• Resource pools: more requests than workers ⇒ queueing.

Common pitfalls

Pitfall	What to do instead
Using birthday \(23\) as certainty	Certainty needs \(n+1\)
Wrong hole count	Define holes precisely
Degrees \(0\) and \(n-1\) both	Graph handshaking subtlety
Ceiling arithmetic slips	Check small numbers
Claiming construction	PHP is existence
Infinite sets without care	Use infinite PHP variant carefully

Checkpoint

• Basic + generalized PHP
  
• Prove one modular consequence
  
• Hash collision necessity
  
• Birthday: certainty vs likelihood
  
• ES statement
  
• Prefix sums divisible by \(n\)
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — quantitative PHP forms

Form A. \(n\) pigeons, \(k\) holes ⇒ some hole \(\ge \lceil n/k\rceil\).

Form B. To ensure some hole \(\ge r\), need \(n \ge k(r-1)+1\) pigeons.

Form C (infinite). Infinitely many pigeons, finitely many holes ⇒ some hole infinite.

Probabilistic vs adversarial

Question	Tool
Must collision exist?	PHP
Is collision likely?	Birthday / probability
Expected max load	Balls and bins (later)

Erdős–Szekeres proof sketch (more detail)

Assign to each index \(i\) the pair \((a_i,b_i)\) = (longest increasing subseq ending at \(i\), longest decreasing ending at \(i\)). If no inc of length \(a\) and no dec of length \(b\), then \(a_i\le a-1\), \(b_i\le b-1\). Pairs lie in a grid of size \((a-1)(b-1)\). If sequence longer, two indices share a pair—leads to contradiction with maximality of \(a_i\) or \(b_i\) when comparing values. (Fill details from a textbook if desired.)

Subarray sum divisible by \(n\) (full write-up)

Let \(s_0=0\), \(s_k=a_1+\cdots+a_k\) for \(k=1..n\). Consider \(s_0,\ldots,s_n\) — \(n+1\) prefix sums. Their residues mod \(n\) lie in \(\{0,\ldots,n-1\}\) (\(n\) holes). Two prefixes \(s_i,s_j\) (\(i<j\)) share a residue ⇒ \(s_j-s_i\equiv 0\pmod n\) ⇒ \(a_{i+1}+\cdots+a_j\) divisible by \(n\). If some \(s_k\equiv 0\), the prefix itself works. \(\square\)

More worked examples

Example 15 — Form B
\(k=5\) holes, want \(\ge 4\) in some hole: need \(5\cdot 3+1=16\) pigeons.

Example 16 — Months
\(40\) people: some month has \(\ge \lceil 40/12\rceil=4\) birthdays.

Example 17 — Bits
Any \(9\) distinct numbers in \(\{1,\ldots,16\}\): two differ by at most … (pigeon on gaps—variant).

Example 18 — Graph
Simple graph on \(n\) verts max edges without … (Turán later); PHP on degrees for same-degree pair.

Additional exercises

26. Prove Form B from Form A.
    
27. Minimum people so that \(4\) share a birth week (52 weeks).
    
28. Show any sequence of \(n^2+1\) distinct reals has mono subseq length \(n+1\) (ES special case \(a=b=n+1\)).
    
29. Hash: \(m\) buckets, \(m+1\) keys—prove collision and describe an algorithm to find one.
    
30. Infinite PHP: among infinitely many naturals, infinitely many share a residue mod \(10\).

Extended practice workshop

Numerical PHP

1. \(100\) pigeons \(7\) holes—min max load.
   
2. To force \(\ge 5\) in some of \(6\) holes—how many pigeons?
   
3. \(n\) buckets, force collision—how many keys?
   
4. Socks: \(k\) colors, force \(r\) of one color.
   
5. Months: force \(3\) in some month—min people.

Modular / number

6. Among \(n+1\) ints, two congruent mod \(n\).
   
7. Subarray sum divisible by \(n\)—full proof rewrite.
   
8. Two of \(11\) ints differ by multiple of \(10\).

Sequences / ES

9. State Erdős–Szekeres.
   
10. Sequence of \(5\) distinct reals has mono subseq length \(3\).
    
11. Find sequence of \(4\) without inc/dec length \(3\).

CS

12. Hash collision necessity at load \(>1\).
    
13. Birthday \(\sim\sqrt{n}\) vs PHP \(n+1\).
    
14. Compression impossibility via injection.
    
15. Load balance max load lower bound \(\lceil n/k\rceil\).

Proof discipline

16. Identify pigeons and holes in a claim you invent.
    
17. Is your PHP proof constructive? How to find the crowded hole?
    
18. Infinite PHP: infinitely many naturals with same last digit—prove.

Mixed

19. Same degree pair at a party of \(n\ge 2\) (with \(0\)/\(n-1\) care).
    
20. Geometry PHP: \(5\) points in unit square—two within \(\sqrt{2}/2\).

PHP pocket card

Ensure	Need
some hole \(\ge 2\)	\(k+1\) pigeons for \(k\) holes
some hole \(\ge r\)	\(k(r-1)+1\) pigeons
likely collision	\(\sim\sqrt{\pi n/2}\) (birthday; probabilistic)

Synthesis

The pigeonhole principle is a forced collision theorem: maps from a larger finite set to a smaller one cannot be injective. Generalized form controls how crowded the busiest hole is (\(\lceil n/k\rceil\)). Number theory, hashing, and extremal combinatorics (Erdős–Szekeres) all reuse the same pattern: name pigeons, name holes, compute the threshold.

Forms to recite

1. Basic. \(n+1\) pigeons, \(n\) holes ⇒ some hole has \(\ge 2\).
   
2. Generalized. \(n\) pigeons, \(k\) holes ⇒ some hole has \(\ge \lceil n/k\rceil\).
   
3. To force \(\ge r\) in some hole: need \(k(r-1)+1\) pigeons.
   
4. Functional. \(|A|>|B|\) finite ⇒ no injection \(A\to B\).
   
5. Infinite awareness. Infinitely many pigeons, finitely many holes ⇒ some hole infinite.

More worked examples

Example — Residues.
Among \(n+1\) integers, two are congruent mod \(n\): holes = residues \(0,\ldots,n-1\).

Example — Subarray sum divisible by \(n\).
Prefix sums \(s_0=0,s_1,\ldots,s_n\) give \(n+1\) values mod \(n\) ⇒ two equal mod \(n\) ⇒ difference (subarray sum) \(\equiv 0\pmod n\).

Example — Socks.
\(k\) colors, want \(r\) of one color: buy \(k(r-1)+1\) socks.

Example — Hashing.
\(m\) slots, \(m+1\) keys ⇒ collision. Birthday bound: \(\sim\sqrt{\pi m/2}\) keys for likely collision—probabilistic, not PHP worst-case.

Example — Erdős–Szekeres (statement).
Any sequence of more than \(ab\) distinct numbers has increasing subsequence length \(a+1\) or decreasing length \(b+1\). PHP on pair-labels \((i,d)\) of longest inc/dec ending at each position.

Extra exercises (synthesis)

31. Prove: among any \(6\) people, at least \(3\) born on the same day of the week? (Compute threshold for \(r=3\), \(k=7\)—actually need \(15\) for \(\ge 3\); so for \(6\) only \(\lceil 6/7\rceil=1\)—correct the claim and state a true PHP fact about \(6\) people.)
    
32. Force at least \(4\) of \(12\) months: how many people?
    
33. Show that any set of \(n+1\) distinct integers in \(\{1,\ldots,2n\}\) contains two with one dividing the other? (Optional harder—or prove a simpler: two differ by at most \(n\)?)
    
34. Load balance: \(n\) jobs \(k\) machines, min possible max load lower bound.
    
35. Prove infinite PHP: among \(\mathbb{N}\), infinitely many share last decimal digit.
    
36. Compression: why injective map \(\{0,1\}^n\to\{0,1\}^{n-1}\) is impossible.

Discipline checklist

Step	Question
1	What are the pigeons?
2	What are the holes?
3	How many of each?
4	Which form (basic / ceiling / force \(r\))?
5	Is the conclusion existential only? (yes—PHP)

PHP proofs often non-constructive until you scan; algorithms that find the crowded hole are separate. Gate IV will mix PHP with sets, relations, and functions—identify pigeons cleanly under time pressure.

Tomorrow

Day 46 — Gate IV. Sets, power set counts, relation properties, equivalence classes, injection/surjection, pigeonhole, one composition—Stage IV portfolio check.