STUDY GUIDE · 3 INTERACTIVE LABS · ABOUT 12 MIN

A shuffled deck is almost certainly an order no one has ever held.

There are 52! ways to arrange a deck: a 68-digit number, far more than the seconds since the Big Bang. Discrete maths deals with things you can count one by one: arrangements, networks, true-or-false statements. It's the maths that computers actually run on.

HOW FAST FACTORIALS GROW
5!120ways to line up 5 people
10!3,628,800ways to order 10 books
13!6,227,020,800more than Earth's population
20!2.43 × 10^18more than grains of sand on all beaches (est.)
52!8.07 × 10^67orderings of a deck of cards

What is discrete mathematics?

Discrete mathematics studies structures made of separate, countable pieces rather than smooth quantities: whole numbers, sets, logical statements, graphs (networks of points and links) and ways of counting arrangements.

Calculus asks how things change smoothly; discrete maths asks how many, which ones, and whether it's even possible. It underpins algorithms, cryptography, databases, network routing and every proof that a program is correct.

Graph theoryNetworks of points and links: maps, social networks, the web.
CombinatoricsCounting arrangements and selections.
LogicTrue/false reasoning, the basis of circuits and proofs.
Number theoryPrimes and remainders: the maths of encryption.
LAB 1 · GRAPH THEORY

Cross every bridge exactly once

Click a land mass to start, then click bridges to cross them. You can't reuse a bridge. In 1736 Euler proved when this is possible: a route exists only if zero or two land masses touch an odd number of bridges.

Ndeg 3Sdeg 3Ideg 5Edeg 3
0 / 7bridges crossed
4land masses with odd degree
YOUR ROUTEClick a land mass to start
This map has 4 land masses with an odd number of bridges. Euler's rule says that's too many. Try anyway!
LAB 2 · COUNTING

Does order matter? It changes everything

Choose k items from n. If the order matters (a podium, a PIN), that's a permutation. If it doesn't (a hand of cards, a committee), it's a combination: divide out the k! orderings of each group.

Gold, silver and bronze from 8 runners: 336 podiums, but only 56 different groups of three medallists.
ORDER MATTERS · nPk336n! / (n − k)!
e.g. picking 3 from A-D:ABCABDACBACDADBADCBACBAD…
ORDER DOESN'T · nCk56n! / (k! (n − k)!)
e.g. picking 3 from A-D:ABCABDACDBCD…
PASCAL'S TRIANGLE, ROW 8 (nCk FOR EVERY k)
LAB 3 · THE PIGEONHOLE PRINCIPLE

More pigeons than holes means someone shares

Put n + 1 items into n boxes and at least one box gets two. It sounds obvious, yet it proves surprising facts. Here, people are sorted by birth month: add a 13th person and a shared month is guaranteed.

Jan
Feb
Mar
Apr
May
Jun
Jul
Aug
Sep
Oct
Nov
Dec
Add people one at a time. Each lands in a random birth month.

Core ideas at a glance

Euler path0 or 2 odd-degree verticesNeeded to traverse every edge once.
Handshake lemmaΣ deg(v) = 2 × edgesSo the number of odd-degree vertices is always even.
PermutationsnPk = n! / (n − k)!Order matters.
CombinationsnCk = n! / (k!(n − k)!)Order doesn't matter.
Pigeonholen + 1 items, n boxes → a box holds 2Guarantees a collision.
Implicationp → q ≡ ¬p ∨ qOnly false when p is true and q is false.
De Morgan¬(p ∧ q) ≡ ¬p ∨ ¬qNegating 'and' gives 'or'.
Treesn vertices → n − 1 edgesConnected with no cycles.

From Euclid to the internet

c. 300 BCEuclid.Proved there are infinitely many primes, and gave the algorithm for greatest common divisors.
1654Pascal and Fermat.Letters about a gambling problem founded probability and systematic counting.
1736Euler's bridges.His Königsberg proof is regarded as the first theorem of graph theory.
1854Boolean algebra.George Boole turned logic into algebra; 80 years later, Shannon used it to design circuits.
1959Dijkstra's algorithm.Shortest paths in a graph, now used in maps and network routing.
1976Four colour theorem.Proved with a computer checking nearly 2,000 cases.

Further reading

Discrete Mathematics and Its ApplicationsKenneth Rosen · the standard university textbook
Mathematics for Computer ScienceLehman, Leighton & Meyer · free MIT text
Concrete MathematicsGraham, Knuth & Patashnik · the deep-dive classic
Test yourself: 20 discrete maths questionsAlgorithms guide

Puzzles like Euler's are pure reasoning. Measure yours.

Our full IQ test covers logical, numerical, verbal and spatial reasoning: 60 questions, about 30 minutes.

Take the full IQ test