Why Mathematics Is Hard: Abstraction, Logic, and the Cumulative Wall

0. Key points

• The difficulty of mathematics comes from the structure of the subject, not from the presence or absence of talent. There are three main sources: (1) a high level of abstraction, (2) a demand for strict logic, and (3) the cumulative nature of the material.
• Abstraction is at once the source of the difficulty and the sharpest available weapon. Once “clocks”, “rotations” and “days of the week” can be treated as the same thing, a single computation solves three problems.
• The word “therefore” in mathematics is not the word “therefore” of ordinary speech. In daily life a claim survives a counterexample; in mathematics a single counterexample kills it outright. This asymmetry is what makes the tedious procedure called proof necessary.
• Because the subject is cumulative, the cause of the problem we cannot solve today is usually not on the page we are reading today. Locating the true position of a stumble is a separate skill in the study of mathematics.
• Everyday intuition fails frequently in mathematics. The remedy, however, is not to discard intuition but to grow a new intuition suited to mathematics. The moment we say “I understand” is precisely the moment that new intuition comes into being.

1. Motivation: the experience of failing at mathematics alone

Historical dates can be memorised, vocabulary keeps accumulating, and yet mathematics alone refuses to improve. A great many people have had this experience. The way mathematics collapses also has a peculiar signature: one day it suddenly stops making sense, and from that point on nothing further makes sense either. In a literature course it is rare to hear “I do not understand Chapter 3, so I cannot read Chapter 4 onwards at all”; in mathematics this happens routinely.

Let us dismiss one common explanation at the outset: “you cannot do mathematics because you lack mathematical talent.” As an explanation this is empty. It is the same as answering “why are you a slow runner?” with “because your legs are slow” — nothing new has been said. It is also useless in practice: if talent is the cause, there is nothing to be done.

Instead, this article looks for the sources of difficulty in the structure of mathematics as a subject. If the cause is structural, then a response matched to the structure is possible. Below we decompose the difficulty into three parts and, for each, examine through concrete examples why it is hard and why mathematics accepts that hardness. At the end we turn to the reason people pay this price at all: the moment of understanding, and beauty.

Note

This article is written so that a high-school student can read it, but the examples are the real thing. The proof that $\sqrt{2}$ is irrational and the proof that there are infinitely many primes use exactly the arguments found in textbooks, written out with the gaps filled in.

2. Preliminaries: splitting “hard” into three

The single sentence “mathematics is hard” in fact mixes together three difficulties of different natures. Let us separate them and give them names.

Kind of difficulty	What is happening	Typical symptom
Abstraction	The objects are invisible. One handles “nothings” such as letters, sets and maps	“What actually is $x$?” “What is this good for?”
Strictness of logic	“Roughly correct” is not allowed. Universal and existential quantifiers and negations must be handled exactly	“My answer was right but I lost marks” “I do not know how to write a proof”
Accumulation	If a single prerequisite is missing, everything downstream halts	“It suddenly stopped making sense partway through” “I have read this one page ten times and cannot move on”

The three are mutually independent. Some people are strong on abstraction but sloppy about logic; others are logically precise but have holes in the foundations. Being able to tell which of the three is blocking us makes the response far more concrete. Sections 3 to 5 take them in turn.

3. The first wall: a high level of abstraction

3.1. What abstraction actually does

Abstraction in mathematics is not performed in order to make things difficult. It is the operation of keeping only what several problems have in common and discarding the rest.

Definition 3.1（Abstraction）

Given concrete objects $A_1, A_2, \ldots, A_k$, extract from the properties holding in each of them only those they share, call the resulting condition $P$, and from then on argue only about “things satisfying $P$”. This is called abstraction. The individual properties that held in $A_1, \ldots, A_k$ but are not part of $P$ are deliberately forgotten.

“Deliberately forgotten” is the essential point. The moment they are forgotten, the results proved apply not only to $A_1, \ldots, A_k$ but automatically to objects we do not yet know about. Abstraction is a trade: we give up information and buy range of application.

And this very act of forgetting is the true source of the difficulty. The human mind is built to handle concrete things. “Three apples” is easy; the moment we hear ”$x$ apples”, every foothold vanishes. Mathematics demands that we keep walking with logic alone once the footholds are gone.

3.2. A concrete example: clocks, rotations and weekdays are the same thing

Definition 3.2（Congruence (clock arithmetic)）

For integers $a, b$ and a positive integer $n$, if $a - b$ is divisible by $n$, we say that $a$ and $b$ are congruent modulo $n$ and write

$$a \equiv b \pmod{n}$$

Example 3.3（Three problems become one）

Consider the following three problems.

1. It is now 9 o’clock. What time will it be 20 hours from now?
2. A hand points straight up. After 17 clockwise turns of $30°$ each, which way does it point?
3. Today is Wednesday. What day of the week is it 100 days from now?

At first sight these are a problem about time, a problem about angles and a problem about weekdays — three separate things. But if we keep only the single feature “after one full cycle we are back where we started” and forget everything else, all three become the same computation.

For 1, $9 + 20 = 29 \equiv 5 \pmod{12}$, so it is 5 o’clock; indeed $29 - 5 = 24$ is divisible by $12$. For 2, $30° \times 17 = 510°$, and since $510 = 360 + 150$ we get $510 \equiv 150 \pmod{360}$, that is, the direction $150°$ clockwise from straight up. For 3, $100 = 7 \times 14 + 2$ gives $100 \equiv 2 \pmod 7$, so it is two days after Wednesday, namely Friday.

All three look only at the remainder after division. Once Definition 3.2 has been set up, problems of this shape are settled for a lifetime in one stroke.

3.3. An example where abstraction kills a concrete problem

Abstraction is not “useless generality”. Abstracted appropriately, a problem that brute force would never finish is over in an instant.

Proposition 3.4

Remove from an $8 \times 8$ chessboard the two diagonally opposite corner squares (say, the top left and the bottom right). The remaining 62 squares cannot be tiled by 31 dominoes of size $1 \times 2$ without overlaps or gaps.

Proof（Proposition 3.4）

A chessboard is coloured alternately black and white, and an $8 \times 8$ board has 32 white and 32 black squares.

First, two diagonally opposite corners have the same colour. Writing the position of a square as $(i, j)$ (with $i, j$ from $1$ to $8$), the colour is determined by whether $i + j$ is even or odd. The top left is $(1,1)$ with $i + j = 2$ and the bottom right is $(8,8)$ with $i + j = 16$; both are even, so the two squares have the same colour. Suppose this colour is black. Then after the removal the board retains 32 white squares and $32 - 2 = 30$ black ones.

Next, however a $1 \times 2$ domino is placed on the board, it covers two squares adjacent vertically or horizontally. Adjacent squares always have $i + j$ of opposite parity, so each single domino covers exactly one white and one black square.

Consequently 31 dominoes cover 31 white and 31 black squares. But only 30 black squares remain on the board. Placing 31 dominoes would require covering 31 black squares, which is impossible. Hence no tiling exists.

∎

This proof counts neither the shape of the board nor the number of ways to place the dominoes. That is because we kept a single quantity, the colour, and forgot everything else. Had we refused to forget and tried brute force, the number of ways to place $1 \times 2$ dominoes on 62 squares is enormous and the calculation would never finish by hand.

Remark 3.5

The difficulty of abstraction lies in the fact that what to keep and what to forget differs from problem to problem, and nobody tells us in advance. Noticing “look at the colours” in Proposition 3.4 is close to impossible on a first encounter. This is why, in studying mathematics, it pays to practise restating in one sentence what a proof discarded, after reading it. Remembering the name of the discarded thing lets us retrieve it when a similar shape appears next time.

4. The second wall: strict logic is demanded

4.1. “Therefore” in daily life and “therefore” in mathematics

Everyday reasoning is astonishingly robust against counterexamples. If someone replies to “summers are hot” with “there was a cool day last August”, nobody withdraws “summers are hot”. Everyday claims silently contain “roughly” and “usually”.

Mathematics abandoned this tolerance.

Definition 4.1（Proof）

A proof of a statement $P$ is a finite sequence of steps that starts only from things already accepted as correct — definitions, axioms, and previously proved theorems — and reaches $P$ using only the rules of logic. No step of the form “this usually holds” or “this is probably fine” may occur along the way.

The price of this definition is high. Proofs become long and tedious, and beginners cannot see why anyone would go to such lengths. But there is a return. A proved statement can never be overturned, whatever examples the future produces. The conclusions of experimental science are updated by new observations; that $\sqrt{2}$ is irrational has not been updated once in 2500 years.

4.2. An example showing that “I checked 1000 cases” is not enough

Example 4.2（A formula that hits 40 times and misses on the 41st）

For an integer $n \ge 0$, set $f(n) = n^2 + n + 41$ and compute some values.

$f(0) = 41$, $f(1) = 43$, $f(2) = 47$, $f(3) = 53$, $f(4) = 61$, $f(5) = 71$.

All are prime. Continuing further, $f(10) = 151$, $f(20) = 461$, $f(39) = 1601$: every value up to $n = 39$ is prime. With 40 consecutive hits one is tempted to declare that $f(n)$ is always prime.

But at $n = 40$,

$$f(40) = 40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41 \times 41$$

which is not prime. Indeed $f(41) = 41^2 + 41 + 41 = 41 \times (41 + 1 + 1) = 41 \times 43$ is not prime either; in the case $n = 41$ the factor $41$ can be read off directly from the expression.

Forty instances are more than sufficient evidence by everyday standards. By mathematical standards they are worthless as evidence. This gap is what “strictness” means, and it is where many people first stumble. Nothing changes if the number of instances is astronomical rather than forty. The Collatz conjecture has been verified by computer over an enormous range, but verification is not proof, so it remains open to this day (Remark 7.3［The Collatz Conjecture］).

4.3. Reading one proof with the gaps filled in

Proposition 4.3

$\sqrt{2}$ is irrational. That is, there exist no integer $a$ and non-zero integer $b$ with $\sqrt{2} = a/b$.

Proof（Proposition 4.3）

Assume such a representation exists and derive a contradiction (proof by contradiction).

Step 1. Suppose $\sqrt{2} = a/b$. Since we may cancel the greatest common divisor of $a$ and $b$, we may assume from the start that $a$ and $b$ are coprime (they have no common divisor other than $1$). Also $\sqrt{2} > 0$, so we may take $a$ and $b$ both positive.

Step 2. Squaring both sides gives $2 = a^2 / b^2$, that is,

$$a^2 = 2 b^2 .$$

The right-hand side is a multiple of $2$, so $a^2$ is even.

Step 3 (not to be skipped). We show that if $a^2$ is even then $a$ is even. It suffices to verify the contrapositive: if $a$ is odd then $a^2$ is odd. If $a$ is odd then $a = 2k + 1$ for some integer $k$, and

$$a^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$

so $a^2$ is odd. Hence the contrapositive holds and $a$ is even.

Step 4. So we may write $a = 2c$. Substituting into the equation of Step 2 gives $(2c)^2 = 2b^2$, that is, $4c^2 = 2b^2$; dividing both sides by $2$ yields

$$b^2 = 2c^2 .$$

Hence $b^2$ is even, and by the same argument as in Step 3 (if $b$ is odd then $b^2$ is odd) $b$ is even as well.

Step 5. Both $a$ and $b$ are even, so $2$ is a common divisor. This contradicts the assumption of Step 1 that they are coprime. Therefore the assumption was false, and $\sqrt{2}$ cannot be written as a fraction.

∎

Many textbooks dispose of Step 3 with “clearly $a$ is even”. But it is not clear: an operation, taking the contrapositive, is involved. Gaps hide in places like this. When something makes us ask “why does that follow?”, it is often not a deficiency in our understanding but a proof the author genuinely omitted.

4.4. Another famous proof

Theorem 4.4（Euclid's theorem）

There are infinitely many primes. That is, for any finite collection of primes there exists a prime not contained in it.

Proof（Theorem 4.4）

Assume there are only finitely many primes and list them all as $p_1, p_2, \ldots, p_n$. Put

$$N = p_1 p_2 \cdots p_n + 1 .$$

$N$ has a prime factor. Since $p_1 \ge 2$ we have $N \ge 2 + 1 = 3 > 1$. Every integer greater than $1$ has a prime factor: the set of divisors of $N$ exceeding $1$ is a non-empty finite set, so it has a least element $q$, and if $q$ were composite it would have a divisor greater than $1$ and smaller than $q$, contradicting minimality; hence $q$ is prime. Take this prime factor $q$.

$q$ differs from every one of $p_1, \ldots, p_n$. Suppose $q = p_i$. Then $q$ divides the product $p_1 p_2 \cdots p_n$, and by assumption $q$ also divides $N$. Hence $q$ divides their difference

$$N - p_1 p_2 \cdots p_n = 1 .$$

But $q$ is prime, so $q \ge 2$, and no integer at least $2$ divides $1$. Contradiction.

Therefore $q$ is a prime not on the list $p_1, \ldots, p_n$, contradicting the assumption that the list contained all primes. Hence there are infinitely many primes.

∎

Remark 4.5

Some people remember this proof as showing that $N$ itself is a new prime, but that is wrong. Indeed $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$, so $N$ can be composite. What the proof asserts is only that a prime factor of $N$ is new. That mistaking a single detail turns a statement false is itself part of the severity of mathematics.

5. The third wall: mathematics is cumulative

5.1. Mathematics as a dependency graph

The content of mathematics is not a collection of independent items but a graph of dependencies. Understanding a concept requires the concepts before it to be already usable.

flowchart TD
A["Fractions and decimals"] --> B["Algebraic expressions"]
B --> C["Linear equations"]
B --> F["Expansion and factorisation"]
C --> D["Functions and graphs"]
F --> G["Quadratic equations"]
G --> D
D --> E["Differential and integral calculus"]
D --> I["Trigonometric, exponential and logarithmic functions"]
I --> E
E --> H["Physics, statistics, machine learning"]

Part of the dependency structure of school mathematics. An arrow means 'without this, one cannot proceed'

This graph has two important consequences.

Consequence 1: the place where we are stuck and the place of the cause are different. Most people who “do not understand quadratic equations” are stuck not on solving quadratics but on the earlier topic of expansion and factorisation, or earlier still on distributing a minus sign in an algebraic expression. Reading the page in front of us ten times does not help because the cause is not on that page. In studying mathematics, finding the true position of the stumble is a skill separate from understanding the content.

Consequence 2: a lag does not resolve itself. With vocabulary, failing to learn today’s words does not prevent learning tomorrow’s. Mathematics is different. Proceeding with a prerequisite missing causes everything depending on it to collapse, so the lag grows over time. Conversely, filling one hole can restore all the items that depended on it at once. Most experiences of “suddenly it all made sense” are of this kind.

5.2. Accumulation happens at the level of the discipline too

The same holds for the history of mathematics as a discipline. Theorem 4.4 appears in the Elements of around 300 BC and is still used in the same form. As a rule mathematics does not discard past results. Physics discarded geocentrism and chemistry discarded phlogiston; hardly any other field has 2000-year-old theorems still in active service.

This is a strength, but from the learner’s side it is also the demand: “now climb the 2000 years that have piled up.” It is why mathematics textbooks never get thinner.

Tip

For a stumble caused by accumulation there is no cure other than going back. The distance to go back, however, is usually shorter than feared. Someone stuck on quadratic functions almost never needs to return to primary-school fractions; the culprit is usually one or two levels back. As with “what did this proof discard?” in Remark 3.5, knowing how to search is itself a form of strength.

6. Everyday intuition and mathematical intuition

6.1. Everyday intuition fails

Besides the three walls there is one more nuisance: the intuition trained by daily life fails systematically in mathematics. And it fails with a characteristic bias.

Example 6.1（Fold a sheet of paper 42 times and reach the Moon）

Folding a sheet of paper $0.1$ millimetres thick in half doubles its thickness. Let us find the thickness after $42$ folds.

$$0.1\,\text{mm} \times 2^{42} = 0.1 \times 4{,}398{,}046{,}511{,}104\ \text{mm}$$

Since $2^{10} = 1024 \approx 10^3$, the estimate $2^{42} = 2^2 \times (2^{10})^4 \approx 4 \times 10^{12}$ already suffices; exactly, $2^{42} = 4{,}398{,}046{,}511{,}104$. Multiplying by $0.1$ and converting from millimetres to kilometres, with $1\ \text{km} = 10^6\ \text{mm}$, gives

$$\frac{0.1 \times 4.398 \times 10^{12}}{10^{6}}\ \text{km} = 4.398 \times 10^{5}\ \text{km} \approx 439{,}800\ \text{km}$$

The mean distance from the Earth to the Moon is about $384{,}400$ kilometres, so $42$ folds overshoot the Moon. For comparison, $41$ folds give about $219{,}900$ kilometres, which does not reach. That the last single fold adds $220{,}000$ kilometres is the frightening part of exponential growth.

(Physically a sheet of paper can only be folded about 10 times; what we are looking at here is the growth of $2^{n}$.)

Everyday experience consists of additive changes. Walk, and we advance by the distance walked; save, and the balance grows by the amount deposited. So no intuition is stocked for multiplicative change. The repeated errors people make about the spread of epidemics or about compound interest have the same cause.

6.2. How intuition fails in probability

Proposition 6.2（The birthday problem）

Take a year to have $365$ days, and suppose each person’s birthday is distributed uniformly over these $365$ days, independently across people. Then when $23$ people gather, the probability that at least one pair shares a birthday exceeds $0.5$.

Proof（Proposition 6.2）

The complement of “at least one coinciding pair” is “all birthdays distinct”. Let $q_n$ be the probability that all $n$ people have distinct birthdays. The first person is unconstrained, the second has $364$ choices differing from the first, the third has $363$, and so on, so

$$q_n = \frac{365}{365} \cdot \frac{364}{365} \cdots \frac{365 - n + 1}{365} = \prod_{k=1}^{n-1}\left(1 - \frac{k}{365}\right)$$

Let us compute $n = 23$. Taking logarithms,

$$\ln q_{23} = \sum_{k=1}^{22} \ln\!\left(1 - \frac{k}{365}\right)$$

and for small $|x|$ we use $\ln(1-x) \approx -x - x^2/2$. Since $\sum_{k=1}^{22} k = \frac{22 \cdot 23}{2} = 253$ and $\sum_{k=1}^{22} k^2 = \frac{22 \cdot 23 \cdot 45}{6} = 3795$,

$$\ln q_{23} \approx -\frac{253}{365} - \frac{3795}{2 \cdot 365^2} = -0.6932 - 0.0142 = -0.7074$$

so $q_{23} \approx e^{-0.7074} \approx 0.493$. An exact computation gives $q_{23} = 0.4927\ldots$. Hence the probability that at least one pair coincides is $1 - 0.4927 = 0.5073\ldots$, which exceeds $0.5$.

∎

That $23$ people suffice for even odds among $365$ days runs strongly against intuition. What intuition fails to pick up is that the quantity to compare against is not the number of people, $23$, but the number of pairs, $\binom{23}{2} = 253$. That $253/365 \approx 0.693$ comes out close to $\ln 2$ in the computation above is a coincidence, but that $253$ is exactly the number of pairs is not.

Betrayals of the same kind occur elsewhere. In the Monty Hall problem, where one picks one of three doors, the host opens a losing door, and one is asked whether to switch, intuition screams "$1/2$" while the correct answer is ”$2/3$ if you switch” (Theorem 3.2［The Monty Hall Problem］). Once infinity is involved the effect is stronger still: the fact that $0.999\ldots$ equals $1$ (Theorem 3.7［Is 1 Equal to 0.999…? Fixing the Meaning of an Infinite Decimal First］), treated in the prerequisite article Is 1 equal to 0.999…?, meets resistance from most people’s intuition to the very end.

6.3. Intuition is rebuilt, not discarded

The important point here is that “in mathematics, discard intuition and proceed by logic alone” is wrong. Professional mathematicians have the strongest intuitions of all. Theirs, however, is not everyday intuition but an intuition about mathematical objects, rebuilt over many years.

Learning roughly passes through three stages.

1. The naive-intuition stage. Symbols are read for their meaning. There is no rigour, but the hand keeps moving.
2. The rigour stage. Naive intuition is checked against definitions and proofs, and the places where it fails are eliminated one by one. This stage is painful and the hand tends to stop.
3. The rebuilt-intuition stage. With rigorous argument now in the backbone, one can again see one’s way through by intuition — except that this intuition can be expanded into a proof on demand.

Most people come to dislike mathematics at stage 2. The enjoyment of stage 1 has been lost and the return of stage 3 has not yet arrived. Concluding at this point that “I am not cut out for this” is, I think, the most regrettable misreading of all.

7. Why people do mathematics nonetheless

7.1. What “I understand” really is

Understanding in mathematics has a quality no other subject has. It is not the sensation of having completed a memorisation but the sensation that things that were scattered have come into view as a single structure.

Example 7.1（Gauss's addition）

Let us find the sum of the integers from $1$ to $100$. Adding them straightforwardly requires 99 additions. But pairing them from the two ends gives

$$(1 + 100) + (2 + 99) + (3 + 98) + \cdots + (50 + 51)$$

and every pair sums to $101$. There are $50$ pairs, so the sum is $101 \times 50 = 5050$.

In general the sum from $1$ to $n$ is $\dfrac{n(n+1)}{2}$ by the same argument. (When $n$ is odd the middle term is left over, but if we write $1 + 2 + \cdots + n$ twice, the second time in reverse order, and add, we obtain $n$ pairs each summing to $n+1$, for a total of $n(n+1)$ regardless of parity; halving gives the same formula.)

This story is famous not because the computation is fast. It is famous because, where there had been nothing but the procedure “add them in order”, a structure — symmetry — became visible. The moment it became visible, 99 operations turned into one multiplication. This is what understanding means in mathematics.

7.2. What beauty is

Here is one more example, this time visible in a picture.

Proposition 7.2

For every positive integer $n$, the sum of the first $n$ odd numbers equals $n^2$; that is,

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2 .$$

The case $n = 4$. Cutting the square into L-shaped layers gives 1, 3, 5, 7 points in the successive outer layers

Proof（Proposition 7.2）

We argue by mathematical induction.

The case $n = 1$. The left-hand side is $1$ and the right-hand side is $1^2 = 1$; they agree.

Assume the statement for $n = k$, that is, $1 + 3 + \cdots + (2k-1) = k^2$. Then the left-hand side for $n = k+1$ becomes, using the hypothesis,

$$\bigl(1 + 3 + \cdots + (2k-1)\bigr) + \bigl(2(k+1) - 1\bigr) = k^2 + (2k + 1)$$

and since $k^2 + 2k + 1 = (k+1)^2$, the statement holds for $n = k+1$ as well.

Hence it holds for every positive integer $n$. The figure above is a picture of the inductive step: adding $2k+1$ points in an L shape to a $k^2$ square produces a $(k+1)^2$ square.

∎

The same fact has two entrances, a symbolic proof and a pictorial one. Moreover the two are not unrelated: the L shape in the picture corresponds exactly to one step of the induction. When mathematicians call something beautiful, they usually mean a situation of this kind. Organised, the criteria for beauty are roughly these three.

• Brevity. The argument ends along a single line without long case distinctions (the colouring argument of Proposition 3.4 is of this kind).
• Unexpected connection. Things that looked separate turn out to have the same structure (the clocks, angles and weekdays of Example 3.3).
• Universality. Prove it once and it applies to objects not yet known (the outcome of the trade described in Definition 3.1).

7.3. “Hard” is another name for “takes time”

Finally, a word of fairness about the difficulty of mathematics. It contains a great many problems that are simple to state and that nobody can solve.

For instance the Collatz conjecture — “halve an even number, triple an odd number and add one; repeating this always reaches 1” (Definition 2.1［The Collatz Conjecture］) — is a statement a primary-school pupil can read, yet it has been open for more than 80 years. The four colour theorem, the assertion that every map can be coloured with 4 colours (Theorem 5.1［The Four Color Theorem］), was settled in 1976, but its proof required an enormous computer-assisted case analysis. What people such as Ramanujan and Euler were seeing is discussed in Famous mathematicians (Theorem 6.2［Euler and Ramanujan］ is one instance). And the naive question “why can we not divide by $0$?” leads directly to the question of what a definition is, as we see in Why we cannot divide by zero (Theorem 4.1［Why You Cannot Divide by Zero］).

That professionals have failed for 80 years on some problems means that failing to solve something in 30 minutes is business as usual. Much of the difficulty of mathematics is a matter of time, not talent. All three walls — abstraction, logic, accumulation — are of the kind that certainly get lower with time. Abstraction becomes familiar as examples accumulate. Logic has standard templates for writing. Accumulation is filled in by going back.

8. Exercises

Exercise 8.1Easy

Colour a $6 \times 6$ grid alternately black and white. Show that if two squares of the same colour are removed (anywhere at all), the rest cannot be tiled by $1 \times 2$ dominoes.

Solution

Of the $6 \times 6 = 36$ squares, $18$ are white and $18$ are black. Removing two squares of the same colour leaves $16$ of one colour and $18$ of the other, a total of $34$ squares, so a tiling would need $34 \div 2 = 17$ dominoes.

As in the proof of Proposition 3.4, adjacent squares have different colours, so each domino covers one white and one black square. Thus 17 dominoes would cover 17 white and 17 black squares, whereas the board has only $16$ squares of one colour. Since $17 > 16$, this is impossible.

(Note that if the two removed squares have different colours, 17 white and 17 black remain and this argument does not rule out a tiling. In fact a tiling is known always to exist in that case.)

Exercise 8.2Standard

Prove that $\sqrt{3}$ is irrational. In following the proof of Proposition 4.3, write out the part “if $a^2$ is a multiple of $3$ then $a$ is a multiple of $3$” without omission.

Solution

Assume $\sqrt{3} = a/b$ with $a, b$ positive coprime integers. Squaring gives $3 = a^2/b^2$, that is, $a^2 = 3b^2$. Hence $a^2$ is a multiple of $3$.

The lemma. We show that if $a^2$ is a multiple of $3$ then so is $a$, by verifying the contrapositive: if $a$ is not a multiple of $3$ then neither is $a^2$. The remainder of $a$ on division by $3$ is $1$ or $2$.

• If the remainder is $1$, then $a = 3k+1$ and $a^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$, so $a^2$ leaves remainder $1$ on division by $3$.
• If the remainder is $2$, then $a = 3k+2$ and $a^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$, so again the remainder is $1$.

In both cases $a^2$ is not a multiple of $3$. The contrapositive is proved, so $a$ is a multiple of $3$.

Continuation. Put $a = 3c$; then $9c^2 = 3b^2$, and dividing both sides by $3$ gives $b^2 = 3c^2$. So $b^2$ is a multiple of $3$, and by the same lemma $b$ is a multiple of $3$. Then $a$ and $b$ have the common divisor $3$, contradicting coprimality. Therefore $\sqrt{3}$ is irrational.

Exercise 8.3Standard

Today is Wednesday. What day of the week is it $10^{100}$ days from now? Use Definition 3.2.

Solution

Days of the week have period 7, so it suffices to find the remainder of $10^{100}$ on division by $7$.

First, $10 = 7 + 3$ gives $10 \equiv 3 \pmod 7$, so $10^{100} \equiv 3^{100} \pmod 7$.

Next, look at the remainders of the powers of $3$ modulo $7$ in turn: $3^1 \equiv 3$, $3^2 = 9 \equiv 2$, $3^3 = 27 \equiv 6$, $3^4 = 81 \equiv 4$, $3^5 = 243 \equiv 5$, $3^6 = 729 = 7 \times 104 + 1 \equiv 1 \pmod 7$. The sixth power returns to $1$.

Since $100 = 6 \times 16 + 4$,

$$3^{100} = (3^{6})^{16} \cdot 3^{4} \equiv 1^{16} \cdot 4 = 4 \pmod 7 .$$

Hence $10^{100}$ days from now is four days after Wednesday, namely Sunday. A number far larger than the age of the universe was handled in three lines by looking only at remainders. This is the “profit of forgetting” described in Definition 3.1.

Exercise 8.4Standard

In the setting of Proposition 6.2, estimate the probability that among $30$ people some pair shares a birthday, using the approximation $\ln(1-x) \approx -x - x^2/2$ from the proof.

Solution

The logarithm of the probability $q_{30}$ that all birthdays are distinct is

$$\ln q_{30} = \sum_{k=1}^{29} \ln\!\left(1 - \frac{k}{365}\right) \approx -\frac{1}{365}\sum_{k=1}^{29} k - \frac{1}{2 \cdot 365^2}\sum_{k=1}^{29} k^2 .$$

Since $\sum_{k=1}^{29} k = \frac{29 \cdot 30}{2} = 435$ and $\sum_{k=1}^{29} k^2 = \frac{29 \cdot 30 \cdot 59}{6} = 8555$,

$$\ln q_{30} \approx -\frac{435}{365} - \frac{8555}{266450} = -1.1918 - 0.0321 = -1.2239$$

so $q_{30} \approx e^{-1.2239} \approx 0.294$. The required probability is therefore about $1 - 0.294 = 0.706$, roughly $71\%$. (The exact value is $0.7063\ldots$, so the approximation is good.)

For $40$ people it is about $89\%$, and for $50$ people about $97\%$. In a single classroom there is almost certainly a pair sharing a birthday.

References

• Hiraku Toyama, Sugaku Nyumon (in Japanese), Iwanami Shinsho, 1959–1960 — a classic that builds up the motivation for extending number systems and for abstraction, starting from everyday language.
• G. Pólya, How to Solve It (Japanese translation by Kenshin Kakiuchi, Maruzen) — a book that puts into explicit procedure what to try when a problem will not yield. The topic-by-topic dictionary at the end is especially practical.
• G. H. Hardy, A Mathematician’s Apology, Cambridge University Press, 1940 — the most famous essay on the “beauty” of mathematics. The criteria of brevity, unexpectedness and universality given in §7.2 derive from its discussion.
• Euclid, Euclid’s Elements (Japanese translation by Kōshirō Nakamura et al.), Kyoritsu Shuppan, 1971 — the proof that there are infinitely many primes is in Book IX. It is the prototype of Theorem 4.4.
• Terence Tao, “There’s more to mathematics than rigour and proofs” — the source of the three-stage account “naive intuition → rigour → rebuilt intuition” described in §6.3.

Appendix: A prescription for getting stuck

Diagnose the cause from the symptom. The threefold classification of the main text can be used directly as a diagnosis. “I can manipulate the formulas but do not know what I am doing” is a problem of abstraction; the cure is to bring definitions back to concrete examples, that is, to substitute actual numbers for $x$. “I get the answer but cannot write the proof” is a problem of logic; copying out three or so short instances of the standard templates (contradiction, contrapositive, induction), such as Proposition 4.3 and Proposition 7.2, until they can be recited stops the paralysis at the opening line. “I have read this one page of the textbook ten times and cannot move on” is a problem of accumulation; stop reading, write out one by one the prerequisites the page is using, and go back to look for the ones that could not be written out.

Restate “I don’t understand” more finely. “I do not understand this section” is not a diagnosis. Sharpened to “I do not understand why line 3 concludes from $a^2 = 2b^2$ that $a$ is even”, it has become a question, and questions can be answered. Step 3 of Proposition 4.3 was written out separately precisely because that is where many people get stuck. Once the incomprehensible spot has been narrowed to a single line, the problem is already half solved.

Change the time estimate. One page of mathematics cannot be read in the time one page of another subject takes. Spending an hour on a single textbook page is not abnormal but standard. Without this estimate we misdiagnose ourselves as slow while progressing at the standard rate. A misdiagnosis erodes motivation, and eroded motivation halts the accumulation. The failure most to be avoided in studying mathematics is, I think, not failing to understand, but mistaking standard difficulty for a personal defect and quitting.