[Beginner → Intermediate] · Sixteen problems, mostly with paper. Discrete maths is learned by doing proofs, and this course showed you worked ones without ever making you write one.
That’s this course’s own diagnosis: “reading a proof is to writing one what reading code is to writing it — you follow along, it all seems reasonable, and then a blank page defeats you.”
Rules of engagement:
- Paper first. Typing a proof and writing one are different activities
- A proof is finished when someone else could follow it, not when you’re convinced
- Get stuck for at least ten minutes before looking. The stuck part is the exercise
- Solutions in note 10
Optional but strongly recommended: work through Lean’s Natural Number Game alongside these. It will not let you skip a step, which is exactly the discipline a blank page doesn’t enforce.
Part A — Logic (note 02)
1. Negate carefully.
Write the negation of each, in plain English, with no leading “it is not the case that”:
(a) Every student passed at least one exam.
(b) There is a number larger than all others.
(c) If it rains, the match is cancelled.
Done when: (c) is not an if-then statement, and you can say why → note 02.
2. Show two statements are the same.
Prove with a truth table, then explain in one sentence why “if” behaving this way makes “if 2+2=5 then I am the Pope” true.
3. Contrapositive vs converse.
For “if is even then is even”: write the converse, the inverse and the contrapositive. Determine which are true.
Done when: you can state which one is always logically equivalent to the original, and have proved the original using it.
Part B — Proof techniques (note 03)
4. Direct proof. Prove: the sum of two odd integers is even.
5. Contradiction. Prove is irrational. Do this without looking. Then prove is irrational, and identify precisely where the argument would break for .
Done when: you can point at the exact step that fails for a perfect square — that’s the step doing the real work → note 03.
6. Contrapositive. Prove: if is odd then is odd. Try it directly first, get stuck, then switch. The getting-stuck is deliberate.
7. Pigeonhole.
(a) In any group of 13 people, two share a birth month.
(b) Any 5 points in a unit square include two within of each other.
(c) In any sequence of distinct reals there is a monotonic subsequence of length . (hard)
8. Counterexample. Disprove: “every odd number ≥ 3 is prime”, and ” is prime for all ”.
Done when: you found the second counterexample by reasoning about the expression, not by brute force.
Part C — Induction (note 05)
9. The classics. Prove by induction:
(a)
(b)
(c) for
(d) for
10. Strong induction. Prove every integer has a prime factorisation. Then explain why ordinary induction is awkward here.
11. Find the bug.
Here is a “proof” that all horses are the same colour. Base case : trivially true. Inductive step: given any horses, remove one — the remaining are the same colour by hypothesis; remove a different one — those are too; so all match.
Done when: you can name the exact value of at which the step fails, and why. Most people find the flaw in the wrong place → note 05.
12. Loop invariant on real code.
Take binary search as you would actually write it. State the invariant, prove initialisation, maintenance and termination. Then instrument the code with an assertion checking it and run it on 1000 random inputs.
Done when: the assertion holds — or you’ve found a real bug. This is the exercise that connects the whole course to code you ship.
Part D — Counting, graphs, number theory (notes 06–08)
13. Count four ways. From a class of 12: (a) how many ways to pick a committee of 5? (b) a president, secretary and treasurer? (c) a committee of 5 with a designated chair? (d) split into groups of 5, 4 and 3?
Done when: you can say for each whether order matters and whether repetition is allowed, before computing → note 06.
14. Prove the handshake lemma. . Then use it to prove the number of odd-degree vertices is always even → note 07.
15. Euler paths. Determine which of these have an Euler circuit, an Euler path, or neither, and state the rule you used: , , , and the Königsberg bridge graph.
16. RSA by hand. With , : compute , , choose , find with the extended Euclidean algorithm. Encrypt and decrypt it back.
Done when: you recover 9, and can say which step would be infeasible if and were 300 digits → note 08.
Where to go next
Project Euler for number theory and combinatorics — the answers are checkable, which is the property paper proofs lack. Velleman’s How to Prove It is the book that actually teaches proof technique rather than assuming it.
Related
- Solutions
- the course
- ToC exercises — proofs, applied to computation
Source: [reference] — built from this course’s own “what would close the gap” list.
Software engineering
Infrastructure & security
Computer science
Hardware & engineering