EntCSExplore. Visualise. Understand.

Everything on the site.

Big-O notationAlgorithms · Count the steps in real loops, then compare n, n log n, n² and 2ⁿ on a live chart.RecursionAlgorithms · Watch frames push and pop on the call stack for factorial and Fibonacci.BFS vs DFSAlgorithms · A queue against a stack: draw a graph and see which order each search visits it in.Sorting algorithmsAlgorithms · Seven sorts on the same input, with comparison, swap and write counts side by side.Binary searchAlgorithms · Halve the range, probe the middle, repeat: with lo, mid and hi drawn on the array.Sets, relations and functionsDiscrete maths · Shade any set expression on a Venn diagram and test a relation for its properties.Proof by inductionDiscrete maths · Four worked proofs revealed one step at a time, and a broken one to diagnose.CombinatoricsDiscrete maths · An exact nPr and nCr calculator, and a Pascal’s triangle that shows its own addition rule.Boolean algebraDiscrete maths · The laws, De Morgan, and normal forms, with a truth-table generator built in.Finite-state machinesTheory · Build a DFA in a table, see it drawn, and run strings through it one symbol at a time.Domain theoryTheory · Why recursion needs least fixed points, and how CPOs, Scott continuity and powerdomains supply them.Truth table generatorTools · Expression in, truth table out: with DNF, CNF, a minimal form and LaTeX.Graph traversal visualiserTools · Draw a graph, then animate BFS, DFS and Dijkstra with the frontier shown.Recursion tree visualiserTools · Paste a recursive function or a recurrence and see its call tree and call count.Gradient descentML maths · Drag the starting point, set the learning rate, and watch it converge or blow up.Vectors and embeddingsML maths · Bend the plane with a 2×2 matrix and measure how close toy word vectors are.Softmax and cross-entropyML maths · Edit the logits and watch the probabilities, the loss and the gradient update live.Attention mechanismML maths · Q, K and V for three tokens, a live score heatmap, and the weighted sum of values.Formatting a CS paper in LaTeXLaTeX · Page limits, \documentclass, front matter, theorem environments and the bibliography.Camera-ready checklistLaTeX · Fonts embedded, PDF/A, copyright form, source bundle, and why final versions get rejected.LaTeX templatesLaTeX · Where the official classes live, plus a minimal article template you can copy.Boolean algebra calculatorTools · A Boolean expression simplifier that names the law used at every step.K-map solverTools · Fill in a Karnaugh map and see the groups, the minimal SOP and POS, and the essential terms.Logic gate simulatorTools · Wire up gates, flip the switches, and get the truth table and expression of your circuit.Regex to NFA converterTools · Type a regular expression and watch Thompson’s construction build its NFA, fragment by fragment.NFA to DFA converterTools · Enter an NFA or a regex and step through the subset construction, then minimise the DFA.DFA simulatorTools · Edit a DFA, run strings through it step by step, batch-test them and share the machine as a link.Regular expressions to automataTheory · Regex to NFA to DFA to minimal DFA, worked through on one example with every set shown.The halting problemTheory · Why no program can tell whether every program halts, with the paradox program played out.Pigeonhole principleDiscrete maths · n pigeons, k holes: why some hole gets ⌈n/k⌉, and the surprising things that follows from it.Dijkstra’s algorithmAlgorithms · Shortest paths with a priority queue: a worked table, a proof, and a graph you can redraw.Hash functionsAlgorithms · Keys in, buckets out: hash a word four ways, then watch chaining and probing handle collisions.Sorting algorithm visualizerTools · Up to seven sorts race on the same data, then step through any one of them line by line.LaTeX table generatorTools · Type or paste a table, merge cells, pick booktabs, and copy clean tabular code.Combination calculatorTools · Exact nCr with the cancelling shown, combinations with repetition, and a full list for small n.Permutation calculatorTools · nPr, nʳ, anagrams like MISSISSIPPI and round-table seatings, with exact working.AlgorithmsSection · Step-through visualisations of sorting, searching, recursion, graph traversal, Dijkstra’s algorithm, hash functions and Big-O growth, with pseudocode that follows along.Discrete mathsSection · Sets, relations and functions, proof by induction, counting, the pigeonhole principle and Boolean algebra, explained with worked examples and interactive checkers.TheorySection · Finite-state machines, regular expressions and automata, the halting problem, and the mathematical semantics of programming languages, explained from first principles.ML mathsSection · Gradient descent, vectors and embeddings, softmax and cross-entropy, and attention, each with a formula, a worked numeric example and a live version.ToolsSection · Free browser tools: truth tables, Boolean simplification, K-maps, logic gates, nCr and nPr, regex to NFA to DFA, sorting and graph visualisers, and LaTeX tables.LaTeXSection · How to format a CS conference or workshop paper in LaTeX, a camera-ready checklist, and a minimal template you can adapt.
Discrete maths

The pigeonhole principle, with proofs and worked examples

If more pigeons than pigeonholes fly home, some hole gets at least two pigeons. That is the whole pigeonhole principle, and it is almost too obvious to state. Yet it proves that two Londoners have exactly the same number of hairs, that every hash function has collisions, and that every long enough sequence hides a long increasing or decreasing run.

Interactive: Pigeon-dropping simulator and monotone-subsequence finderUpdated

The statement

Pigeonhole principle

If nn objects are placed in kk boxes and n>kn > k, then at least one box contains at least two objects.

Generalised form. If nn objects are placed in kk boxes, then some box contains at least ⌈n/k⌉\lceil n/k \rceil objects.

In the language of functions: if ∣A∣>∣B∣|A| > |B|, no function f:A→Bf : A \to B is one-to-one. Some two different elements a≠a′a \ne a' have f(a)=f(a′)f(a) = f(a').

The principle tells you that a crowded box exists, but not which one. That makes it a typical non-constructive argument: it proves existence without exhibiting the example.

Why it is true

Suppose every box held at most ⌈n/k⌉−1\lceil n/k \rceil - 1 objects. Then the total would be at most

k(⌈nk⌉−1)<k⋅nk=n,k\left(\left\lceil \tfrac{n}{k} \right\rceil - 1\right) < k \cdot \tfrac{n}{k} = n,

because ⌈n/k⌉<n/k+1\lceil n/k \rceil < n/k + 1. That is fewer than the nn objects we placed, a contradiction. The bound is the best possible: dealing the objects round-robin, one per box in turn, puts at most ⌈n/k⌉\lceil n/k \rceil in any box. Try both ways below.

Drop pigeons into holes

The art: choosing pigeons and holes

Every pigeonhole proof comes down to one decision: what are the pigeons, and what are the holes? The objects are usually the things you are given; the boxes are the possible values of some property you choose. Once you have more objects than possible values, two objects share a value, and the trick is to pick a property for which sharing a value gives you what you want.

Socks in the dark

A drawer holds black and white socks. How many must you take, without looking, to be sure of a matching pair? Pigeons: the socks you take. Holes: the 2 colours. With 3 socks, two share a colour. With 2 you might be unlucky. With cc colours you need c+1c + 1 socks.

Shared birthdays

Among 367 people, two share a birthday (366 possible dates, including 29 February). That is certain. The famous birthday paradox is the probabilistic cousin: with only 23 people, the chance of a shared birthday is already about 50.7%, because there are (232)=253\binom{23}{2} = 253 pairs that could match.

Two people with the same number of hairs

A human head has at most about 150,000 hairs, so there are at most 150,001 possible hair counts (counting zero). London has about 9 million people, far more than 150,001, so two Londoners have exactly the same number of hairs. The generalised form says more: some hair count is shared by at least ⌈9,000,000/150,001⌉\lceil 9{,}000{,}000 / 150{,}001 \rceil = 60 people.

A card trick bound

From any 13 cards, at least ⌈13/4⌉\lceil 13/4 \rceil = 4 are of the same suit. From any 5 cards, two share a suit, which is the starting point of a well-known two-person card trick.

Classic proofs

Subset sums: some block of consecutive terms is divisible by n

Claim. Among any nn integers a1,…,ana_1, \dots, a_n, some non-empty block of consecutive terms ai+1+⋯+aja_{i+1} + \dots + a_j has a sum divisible by nn.

  1. Form the prefix sums s0=0,s1=a1,s2=a1+a2,…,sn=a1+⋯+ans_0 = 0, s_1 = a_1, s_2 = a_1 + a_2, \dots, s_n = a_1 + \dots + a_n. That is n+1n + 1 numbers: the pigeons.
  2. Look at each sj mod ns_j \bmod n. There are only nn possible remainders, 0,1,…,n−10, 1, \dots, n-1: the holes.
  3. n+1n + 1 pigeons in nn holes: two prefix sums sis_i and sjs_j with i<ji < j leave the same remainder.
  4. Then sj−si=ai+1+⋯+ajs_j - s_i = a_{i+1} + \dots + a_j is divisible by nn. It is non-empty because i<ji < j. ■\blacksquare

Five points in a square: two are close

Claim. Among any 5 points in a 2×22 \times 2 square, two are at distance at most 2\sqrt 2.

  1. Cut the square into four 1×11 \times 1 squares by joining the midpoints of opposite sides. These are the holes; the 5 points are the pigeons.
  2. 5 points, 4 small squares: two points lie in the same small square (a point on a cut line can go in either).
  3. The farthest apart two points in a 1×11 \times 1 square can be is the diagonal, 12+12=2\sqrt{1^2 + 1^2} = \sqrt 2. ■\blacksquare

Friends at a party

Claim. At any party of n≥2n \ge 2 people, two people have the same number of friends at the party (friendship is mutual).

  1. Each person has between 00 and n−1n - 1 friends: nn possible values for nn people. That is not yet enough pigeons.
  2. But 0 and n−1n - 1 cannot both occur: someone with n−1n - 1 friends is friends with everyone, so nobody has 0.
  3. So the counts take at most n−1n - 1 different values, and nn people means two share a count. ■\blacksquare

Erdős–Szekeres: order in any sequence

Any sequence of n2+1n^2 + 1 distinct numbers contains an increasing subsequence of length n+1n + 1 or a decreasing one of length n+1n + 1. Ten numbers, for instance, always contain a monotone run of four, not necessarily adjacent.

The proof labels each term xtx_t with a pair (it,dt)(i_t, d_t): the length of the longest increasing and longest decreasing subsequence ending at xtx_t. Two different terms never get the same pair. If s<ts < t and xs<xtx_s < x_t, then xtx_t extends every increasing run ending at xsx_s, so it>isi_t > i_s; if xs>xtx_s > x_t, likewise dt>dsd_t > d_s. If every run had length at most nn, there would be only n2n^2 possible pairs for n2+1n^2 + 1 terms: pigeonhole, contradiction. Check the labels yourself:

Monotone subsequence finder

Type distinct numbers. Each term gets a label (i, d): the longest increasing and longest decreasing subsequence ending at it.

Pigeonholes in computer science

  • Hash collisions are unavoidable. A hash function maps a huge (often infinite) set of inputs to a fixed number of outputs, such as 22562^{256}, so many inputs share each output. Security rests on collisions being hard to find, never on their not existing.
  • No lossless compressor shrinks every file. There are 2n2^n files of nn bits but only 2n−12^n - 1 shorter files. A compressor that made every nn-bit file shorter would send two files to the same output, and could not decompress both.
  • Finite automata cannot count. A DFA with kk states reading 00,01,…,0k0^0, 0^1, \dots, 0^k visits some state twice, so it cannot tell those prefixes apart. That is the heart of the proof on the finite-state machines page that {0n1n}\{0^n1^n\} is not regular, and of the pumping lemma.
  • Loops in a finite state space. A deterministic process with kk possible states must repeat a state within k+1k + 1 steps, and then cycles forever. Floyd’s tortoise-and-hare cycle detection and the analysis of pseudo-random generators both start here.

Exercises

Exercise 1: numbers that divide each other

Choose any 51 numbers from {1,2,…,100}\{1, 2, \dots, 100\}. Show that one of them divides another.

  1. Write each number as 2a⋅m2^a \cdot m with mm odd. The odd part mm is one of the 50 odd numbers 1,3,…,991, 3, \dots, 99: the holes.
  2. 51 numbers, 50 odd parts: two chosen numbers share an odd part, say 2am2^a m and 2bm2^b m with a<ba < b.
  3. Then the first divides the second. With 50 numbers it can fail: 51,52,…,10051, 52, \dots, 100 has no such pair. ■\blacksquare

Exercise 2: equal differences

Show that among any 6 integers, two have a difference divisible by 5.

  1. Holes: the 5 remainders mod 5. Pigeons: the 6 integers.
  2. Two integers xx and yy leave the same remainder, so x−y≡0(mod5)x - y \equiv 0 \pmod 5. ■\blacksquare

Exercise 3: how many to guarantee three?

How many people must be in a room to be sure that at least three were born in the same month?

  1. We want ⌈n/12⌉≥3\lceil n/12 \rceil \ge 3, that is n>24n > 24.
  2. So 25 people suffice. 24 do not: two born in each month is possible. Answer: 25.
A checklist for pigeonhole proofs Name the pigeons and the holes explicitly. Check that there are more pigeons than holes (or count ⌈n/k⌉\lceil n/k \rceil). Then say what “two pigeons in one hole” gives you, and why it is the conclusion you wanted. If the counts come out equal, look for a value that cannot occur, as in the party proof.

References

  1. P. Erdős and G. Szekeres, “A combinatorial problem in geometry”, Compositio Mathematica 2, 1935.
  2. K. H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019. Section 6.2.
  3. “Pigeonhole principle”, Wikipedia.