[Beginner → Intermediate] · Worked answers to note 09. Write yours first.
Proofs are given in the form you should be writing — prose with the logical skeleton visible, not symbol soup.
Part A — Logic
1. Negate carefully
(a) “Every student passed at least one exam” is . Negation: — “Some student failed every exam.”
(b) . Negation: — “For every number there is one at least as large.”
(c) “It rained and the match went ahead.”
(c) is the one that matters. — the negation of an implication is not an implication. To refute “if it rains the match is cancelled” you need a day that rained and the match happened. Not “if it rains the match happens.”
This is the most common logical error in engineering discussion. “We said if load exceeds X we’d scale” is not refuted by “load was low and we didn’t scale.”
2.
The truth table matches on all four rows. The only row where is false is true, false — exactly where is false.
“If 2+2=5 then I am the Pope” is true because the antecedent is false, so is true, so the disjunction holds. This is vacuous truth, and it isn’t a defect: it’s what makes “all elements of the empty set are prime” true and makes universally quantified statements behave correctly over empty domains. Every for loop over an empty list “satisfies” its postcondition for the same reason.
3. Contrapositive vs converse
Original: even even. True.
- Converse: even even. True here, but not because of the original
- Inverse: odd odd. True, and equivalent to the converse
- Contrapositive: odd odd. True, and always logically equivalent to the original
Proof via contrapositive: let be odd, . Then , odd. ∎
Only the contrapositive is guaranteed equivalent. Confusing a statement with its converse is the single most common informal-reasoning error — “all fraud has these signals” does not give you “all these signals are fraud”, and that mistake has shipped in real classifiers.
Part B — Proof techniques
4. Sum of two odds
Let , . Then , which is even by definition. ∎
The whole technique in a line: unfold the definitions, do algebra, fold back into the target definition.
5. irrational — and where it breaks for
Suppose in lowest terms. Then , so is even, so is even (by exercise 3’s contrapositive). Write : , so , so is even too. But then was not in lowest terms — contradiction. ∎
is the same argument with “divisible by 3”, relying on: if then .
For the argument breaks at exactly one step: ” divisible by 4 divisible by 4” is false — take , . That implication holds when the divisor is prime (by Euclid’s lemma) and fails otherwise.
That step is doing all the work, and noticing it is the exercise. The general theorem: is irrational unless is a perfect square.
6. Contrapositive again
Direct attack: assume odd, try to derive odd — you get stuck immediately, because you can’t factor information out of easily.
Contrapositive: assume even, , so — even. ∎
Two lines instead of an impasse. The heuristic worth keeping: when the hypothesis is about a squared/composed quantity and the conclusion about the base, try the contrapositive.
7. Pigeonhole
(a) 13 people, 12 months. . ∎
(b) Cut the unit square into four quarters of side . Five points, four quarters ⇒ some quarter holds two. The diagonal of a quarter is , so those two are at most that far apart. ∎
The construction is the whole difficulty — the pigeonhole step is trivial once you decide what the holes are.
(c) Erdős–Szekeres. For each element, record a pair (length of longest increasing subsequence ending here, length of longest decreasing). If no monotonic subsequence of length exists, both coordinates lie in — only possible pairs for elements, so two elements share a pair. But any two distinct elements must differ in at least one coordinate (whichever way they compare). Contradiction. ∎
8. Counterexamples
“Every odd ≥ 3 is prime”: 9 = 3×3.
” is always prime”: gives .
And you can see it without searching: at , every term has a factor of 41, so . Working backwards, also fails. Euler’s polynomial is prime for — forty confirming cases, then failure.
That’s the lesson. No number of verified cases proves a universal claim. This is the difference between testing and proof, and it’s why tests show the presence of bugs, not their absence.
Part C — Induction
9. The classics
(a) Base : ✓. Step: assume . Then
which is the formula at . ∎
(c) for . Base : ✓. Step: assume . Then , and , true for . ∎
Note the base case is 5, not 1 — it fails at . Choosing the right base is part of the proof, and stating a bound “for ” without checking is a common slip.
10. Strong induction
Every has a prime factorisation. If is prime, done. Otherwise with . Both and are smaller than but neither is necessarily — so we need the hypothesis for all smaller values, which is strong induction. Apply it to and , concatenate. ∎
Ordinary induction is awkward because the factors aren’t the predecessor. Whenever a recursive structure splits into arbitrary smaller pieces — mergesort, quicksort, divide-and-conquer generally — strong induction is the natural tool → recursion.
11. All horses
The step fails at .
For horses, removing one horse and then a different one leaves two overlapping sets of size , and the shared horse forces both sets to the same colour. For , the two sets are and — they share nothing, so no colour is transmitted between them.
Most people say the base case is wrong. It isn’t — one horse genuinely is one colour. The inductive step is invalid for exactly one value of , and a chain that breaks at its first link never reaches anything.
The general lesson: an inductive step that relies on an implicit non-emptiness or overlap must be checked at the smallest case. The same bug appears in real proofs about intervals, intersections and graph connectivity.
12. Loop invariant on binary search
Invariant: if the target is in the array, its index lies in .
Initialisation: , covers the whole array. ✓
Maintenance: the array is sorted. If a[mid] < target, everything at index is target, so discarding them cannot discard the target; symmetric for . ✓
Termination: strictly decreases each iteration, so the loop ends; when the range is empty, and by the invariant the target is absent. ∎
while lo <= hi:
assert not (target in arr) or lo <= arr.index(target) <= hi # the invariant, checkedRun it on 1000 random arrays. This is the exercise that makes the course pay: an invariant is a precise statement about a loop that you can both prove and assert. The overflow bug in mid = (lo + hi) // 2 that lived in the JDK for nine years was an invariant violation nobody had stated → DSA.
Part D — Counting, graphs, number theory
13. Count four ways
| Answer | Order? | Reasoning | |
|---|---|---|---|
| (a) Committee of 5 | No | Unordered selection | |
| (b) Pres/Sec/Treas | Yes | Distinct roles | |
| (c) Committee + chair | Partly | Choose, then designate | |
| (d) Groups of 5,4,3 | No, within groups | Multinomial |
(c) has a second route: — pick the chair first, then four others. Two different-looking computations agreeing is a genuine check on a counting argument, and it’s the habit worth building.
14. Handshake lemma
Each edge has two endpoints and contributes exactly 1 to the degree of each. Summing degrees counts every edge exactly twice: . ∎
Corollary: is even, so the degree sum is even. Split it into odd-degree and even-degree vertices; the even-degree part is even, so the odd-degree part must be even too. A sum of odd numbers is even only if there are an even number of them. ∎
“Double counting” — count the same thing two ways and equate — is one of the most powerful proof techniques in combinatorics, and this is its cleanest example.
15. Euler paths
Rule: a connected graph has an Euler circuit iff every vertex has even degree; an Euler path (not circuit) iff exactly two vertices have odd degree.
| Graph | Degrees | Verdict |
|---|---|---|
| all 3 (four odd) | Neither | |
| all 4 (even) | Euler circuit | |
| all 3 (six odd) | Neither | |
| Königsberg | 3,3,3,5 (four odd) | Neither |
Königsberg is the origin of graph theory, and Euler’s insight was precisely that the geography is irrelevant — only the degree parity matters. Four odd vertices, so no walk crosses every bridge once. A negative result, proved by counting.
16. RSA by hand
, ⇒ , .
; ✓. Extended Euclid gives (check: ✓).
Encrypt: .
Decrypt: ✓
The infeasible step at 300 digits is computing , which requires factoring . Everything else — modular exponentiation by squaring, the extended Euclidean algorithm — is fast at any size.
RSA’s security is exactly the gap between multiplying (easy) and factoring (believed hard). Note “believed”: there is no proof factoring is hard, and Shor’s algorithm factors in polynomial time on a quantum computer → beyond P vs NP · cryptography.
Related
Source: [reference] — RSA and counterexample arithmetic verified computationally, August 2026.
Software engineering
Infrastructure & security
Computer science
Hardware & engineering