8.P — Worked Problems: Discrete Mathematics

Twelve problems: set arguments, logic, three induction proofs, a recurrence solved from scratch, and graphs. Every formula used is derived in the chapter that introduces it.

Problem 1 — Inclusion–exclusion with three sets

In a class of 100 students, 45 study French, 40 study German, 38 study Spanish, 15 study French and German, 12 study German and Spanish, 18 study French and Spanish, and 5 study all three. How many study none?

Solution

Step 1 — write the three-set formula.

|F\cup G\cup S| = |F|+|G|+|S| - |F\cap G|-|G\cap S|-|F\cap S|+|F\cap G\cap S|

Step 2 — substitute.

= 45+40+38-15-12-18+5

Work left to right: 45+40 = 85, +38 = 123, -15 = 108, -12 = 96, -18 = 78, +5 = 83.

|F\cup G\cup S| = 83

Step 3 — subtract from the total.

100 - 83 = 17

Answer: 17 students study none of the three.

Step 4 — check by building the seven regions, which is the reliable verification. Work outwards from the centre:

• all three: 5
• French and German only: 15-5 = 10
• German and Spanish only: 12-5=7
• French and Spanish only: 18-5=13
• French only: 45 - 10 - 13 - 5 = 17
• German only: 40-10-7-5 = 18
• Spanish only: 38-13-7-5 = 13

Total: 5+10+7+13+17+18+13 = 83 ✓ and all seven are non-negative, which is a real check — negative regions would mean the data were inconsistent.

Why the signs alternate. Adding the three singles counts the pairwise overlaps twice and the triple overlap three times. Subtracting the three pairs removes the triple three more times, leaving it counted zero times. Adding it back once fixes it. Every element ends up counted exactly once, which is what the formula is designed to achieve.

Problem 2 — Logic: a statement and its relatives

Take "If a number is divisible by 6, then it is divisible by 3." Write its converse, inverse and contrapositive, and say which are true.

Solution

Step 1 — name the parts. p = "divisible by 6", q = "divisible by 3". The original is p\to q.

Step 2 — write the three relatives.

Name	Form	Statement
Original	p\to q	divisible by 6 ⟹ divisible by 3
Converse	q\to p	divisible by 3 ⟹ divisible by 6
Inverse	\lnot p\to\lnot q	not divisible by 6 ⟹ not divisible by 3
Contrapositive	\lnot q\to\lnot p	not divisible by 3 ⟹ not divisible by 6

Step 3 — decide each.

Original: TRUE. If n = 6k then n = 3(2k), which is a multiple of 3.

Converse: FALSE. Counterexample: 9 is divisible by 3 and not by 6. One counterexample is enough to destroy a universal claim.

Inverse: FALSE. Same counterexample: 9 is not divisible by 6, yet it is divisible by 3.

Contrapositive: TRUE. If n is not a multiple of 3, it cannot be a multiple of 6 — because every multiple of 6 is a multiple of 3, so being one would contradict the assumption.

Answers: original and contrapositive true; converse and inverse false.

The pattern worth carrying away. A statement and its contrapositive always agree, and the converse and inverse always agree with each other (they are contrapositives of one another). So there are really only two distinct claims here, not four. Proving a statement never proves its converse, and the habit of assuming otherwise is what turns "all fraudsters do X" into "anyone who does X is a fraudster".

Problem 3 — Induction on a sum

Prove that 1^2+2^2+\cdots+n^2 = \dfrac{n(n+1)(2n+1)}{6} for every positive whole number n.

Solution

Step 1 — the base case. For n=1:

• Left side: 1^2 = 1
• Right side: \frac{1\times2\times3}{6} = \frac66 = 1 ✓

Step 2 — the inductive hypothesis. Assume it holds for some n=k:

1^2+2^2+\cdots+k^2 = \frac{k(k+1)(2k+1)}{6}

Step 3 — prove it for k+1. We must show

1^2+\cdots+k^2+(k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}

Note where the right side came from: substitute k+1 for n in the formula, so n+1 becomes k+2 and 2n+1 becomes 2k+3. Writing down the target before starting is what stops you drifting.

Step 4 — start from the left and use the hypothesis on the first k terms.

\underbrace{\frac{k(k+1)(2k+1)}{6}}_{\text{by the hypothesis}} + (k+1)^2

Step 5 — put over a common denominator of 6.

= \frac{k(k+1)(2k+1)+6(k+1)^2}{6}

Step 6 — factor out (k+1), which is present in both terms:

= \frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}

Step 7 — expand and simplify the bracket.

k(2k+1)+6(k+1) = 2k^2+k+6k+6 = 2k^2+7k+6

Step 8 — factorise it. Two numbers multiplying to 2\times6=12 and adding to 7 are 3 and 4:

2k^2+3k+4k+6 = k(2k+3)+2(2k+3) = (k+2)(2k+3)

Step 9 — put it together.

= \frac{(k+1)(k+2)(2k+3)}{6}

which is exactly the target from Step 3. \blacksquare

Conclusion. True for n=1, and true for k+1 whenever true for k. Therefore true for every positive whole number.

A numerical check at n=4: left side 1+4+9+16 = 30; right side \frac{4\times5\times9}{6} = \frac{180}{6} = 30 ✓

Where the difficulty always lies. Step 8. The algebra of an induction proof usually comes down to factorising the expression you land on so that it matches the target, and if it will not factorise you should suspect the formula rather than your algebra.

Problem 4 — Induction on divisibility

Prove that n^3-n is divisible by 6 for every positive whole number n.

Solution

Step 1 — the base case. n=1: 1-1 = 0, and 0 is divisible by 6 ✓

Step 2 — assume k^3-k = 6m for some whole number m.

Step 3 — examine the next case.

(k+1)^3-(k+1) = k^3+3k^2+3k+1-k-1 = k^3+3k^2+2k

Step 4 — pull out the part we already know about.

= \left(k^3-k\right) + 3k^2+3k = 6m + 3k(k+1)

Step 5 — show the leftover is also divisible by 6. We need 3k(k+1) to be a multiple of 6, which means k(k+1) must be even. And it is: k and k+1 are consecutive whole numbers, so exactly one of them is even, and a product with an even factor is even.

So k(k+1) = 2t for some whole t, and

3k(k+1) = 6t

Step 6 — conclude.

(k+1)^3-(k+1) = 6m+6t = 6(m+t)

which is divisible by 6. \blacksquare

Check at n=4: 64-4 = 60 = 6\times10 ✓ At n=5: 125-5 = 120 = 6\times20 ✓

The proof without induction, which is shorter and more illuminating. Factorise:

n^3-n = n(n^2-1) = (n-1)n(n+1)

That is the product of three consecutive whole numbers. Among any three consecutive numbers, at least one is even and exactly one is a multiple of 3. So the product is divisible by 2 and by 3, hence by 6.

Both proofs are correct, and the second explains why. When a result has a structural reason, it is worth finding it — induction verifies, but it rarely enlightens.

Problem 5 — The pigeonhole principle

Prove that in any group of 6 people, either 3 of them all know each other, or 3 of them are all mutual strangers.

Solution

This is the smallest case of Ramsey's theorem, and the proof is short but needs care.

Step 1 — set it up as a graph. Six vertices for six people. Colour each of the \binom62 = 15 edges red if the pair know each other, blue if they do not. Every edge gets exactly one colour. We must show there is a triangle of one colour.

Step 2 — pick one person, call them A. A has 5 edges leaving them, each red or blue.

Step 3 — apply pigeonhole. Five edges into two colour classes: by the pigeonhole principle, at least one colour is used at least \left\lceil\frac52\right\rceil = 3 times.

Say without loss of generality that colour is red, and A knows B, C and D. (If it were blue, the whole argument runs with the colours swapped.)

Step 4 — now look at the triangle B, C, D. There are two possibilities.

Case 1: at least one of the edges BC, CD, BD is red. Say BC is red. Then A–B, A–C and B–C are all red, so A, B, C is a red triangle — three mutual acquaintances. Done.

Case 2: none of BC, CD, BD is red. Then all three are blue, so B, C, D is a blue triangle — three mutual strangers. Done.

Both cases produce a monochromatic triangle, and there are no other cases. \blacksquare

Answer: proved.

Why 6 and not 5. With five people it can fail. Arrange them in a circle, colour the five circle edges red and the five diagonals blue: the red edges form a 5-cycle with no triangle, and so do the blue ones. Six is exactly the threshold, which is why this number is written R(3,3) = 6.

Why this is famous. The next case, R(5,5), is unknown — it is somewhere between 43 and 48, and nobody can pin it down. Erdős said that if aliens demanded R(5,5) or they would destroy Earth, we should put every mathematician and computer on it; but if they demanded R(6,6), we should attack the aliens instead.

Problem 6 — Solving a recurrence

Solve a_n = 5a_{n-1}-6a_{n-2} with a_0 = 3 and a_1 = 8.

Solution

Step 1 — write the characteristic equation. Substitute a_n = r^n and divide by r^{n-2}:

r^2 = 5r-6 \quad \Rightarrow \quad r^2-5r+6 = 0

Step 2 — solve it.

(r-2)(r-3) = 0 \quad \Rightarrow \quad r = 2,\ 3

Step 3 — write the general solution. Distinct roots, so

a_n = A(2^n)+B(3^n)

Step 4 — use the starting values.

From a_0 = 3: \;A+B = 3

From a_1 = 8: \;2A+3B = 8

Step 5 — solve the pair. From the first, A = 3-B. Substitute:

2(3-B)+3B = 8 \quad \Rightarrow \quad 6-2B+3B = 8 \quad \Rightarrow \quad B = 2, \quad A = 1

Answer: a_n = 2^n + 2\cdot3^n.

Check by generating the sequence both ways.

From the recurrence: a_0=3, a_1=8, a_2 = 5(8)-6(3) = 22, a_3 = 5(22)-6(8) = 62, a_4 = 5(62)-6(22) = 178.

From the formula: a_2 = 4+18 = 22 ✓, a_3 = 8+54 = 62 ✓, a_4 = 16+162 = 178 ✓

What to notice. For large n the 3^n term swamps the 2^n term, so the sequence eventually grows by a factor of almost exactly 3 each step. The largest root controls the long-run growth rate — the same principle as the dominant eigenvalue in 4.P and the slowest-decaying term in 6.P. Three different-looking subjects, one idea.

Problem 7 — The Fibonacci ratio

Using Binet's formula, show that the ratio \frac{F_{n+1}}{F_n} approaches the golden ratio, and find F_{20} without listing the sequence.

Solution

Step 1 — write Binet's formula.

F_n = \frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi = 1.6180340, \quad \psi = -0.6180340

Step 2 — form the ratio.

\frac{F_{n+1}}{F_n} = \frac{\varphi^{n+1}-\psi^{n+1}}{\varphi^n-\psi^n}

Step 3 — divide top and bottom by \varphi^n, which is the standard move for finding the limit of a ratio of exponentials:

= \frac{\varphi - \psi\left(\frac{\psi}{\varphi}\right)^{n}}{1 - \left(\frac\psi\varphi\right)^n}

Step 4 — take the limit. Since \left|\frac\psi\varphi\right| = \frac{0.618}{1.618} = 0.382 < 1, that quantity raised to the power n shrinks to zero. So

\lim_{n\to\infty}\frac{F_{n+1}}{F_n} = \frac{\varphi - 0}{1-0} = \varphi = 1.618034 \quad \blacksquare

Step 5 — how fast? The error shrinks by a factor of 0.382 each step, so the ratio gains about half a decimal place per term.

n	F_{n+1}/F_n
5	8/5 = 1.600
8	34/21 = 1.6190
12	233/144 = 1.618056
16	1597/987 = 1.6180344

Step 6 — compute F_{20}. Since |\psi^{20}| is tiny, use the rounding form:

\varphi^{20} = e^{20\ln 1.618034} = e^{20\times0.4812118} = e^{9.624237} = 15126.99

F_{20} \approx \frac{15126.99}{2.2360680} = 6765.0

Answer: F_{20} = 6765, and \psi^{20} = 0.0000661, so the correction is far below 0.5 and rounding is safe.

Where this matters practically. Computing F_{1000} by the recurrence takes a thousand additions; by the formula it takes one exponentiation — although for exact large values, computers use repeated squaring of the matrix \begin{pmatrix}1&1\\1&0\end{pmatrix}, which gives F_n exactly in about \log_2 n multiplications and avoids all the rounding trouble.

Problem 8 — Counting with the handshake lemma

A graph has 12 vertices, each of degree 3. How many edges does it have? Can a graph have 5 vertices with degrees 4, 3, 3, 2, 1?

Solution

Part 1.

\sum\deg(v) = 12\times3 = 36 = 2m \quad \Rightarrow \quad m = 18

Answer: 18 edges.

Part 2. Sum the proposed degrees:

4+3+3+2+1 = 13

That is odd. But the handshake lemma says the degree sum is always 2m, which is even. No such graph exists.

Answer: impossible.

A second check that agrees. Count the vertices of odd degree in the proposed list: 3, 3 and 1 — three of them. The lemma's corollary says the number of odd-degree vertices must be even, and three is not ✓ the same contradiction, spotted a different way.

A harder case worth doing. What about degrees 4, 4, 3, 2, 1? The sum is 14, which is even, so the lemma is satisfied and there would be 7 edges. But it is still impossible, for a different reason: a vertex of degree 4 in a 5-vertex simple graph must join every other vertex, so every other vertex has degree at least 1 — fine so far — but with two such vertices, each of the remaining three is joined to both of them, so none can have degree below 2. The proposed degree 1 is impossible.

The lesson. The handshake lemma is a necessary condition, not a sufficient one. Passing it does not mean a graph exists; failing it proves one does not. Knowing which direction a test runs in is half of using it correctly.

Problem 9 — Euler's formula in use

A connected planar graph has 10 vertices and every vertex has degree 3. How many edges and faces does it have?

Solution

Step 1 — edges, by the handshake lemma.

2m = 10\times3 = 30 \quad \Rightarrow \quad m = 15

Step 2 — faces, by Euler's formula.

V - E + F = 2 \quad \Rightarrow \quad 10 - 15 + F = 2 \quad \Rightarrow \quad F = 7

Answer: 15 edges and 7 faces, one of which is the unbounded outside region.

Step 3 — check planarity is even possible. A simple planar graph needs m\le 3n-6:

3(10)-6 = 24 \ge 15 \; ✓

so nothing is contradicted.

Step 4 — what shape is it? Ten vertices, fifteen edges, all degrees 3. Count the edges around the faces: each edge borders exactly two faces, so if every face had k sides we would need kF = 2E, giving 7k = 30 — not a whole number, so the faces cannot all be the same size. In fact this describes the Petersen graph's planar relatives and several other shapes, including a pentagonal prism: two pentagons joined by five edges has 10 vertices, 5+5+5 = 15 edges, and faces of 2 pentagons plus 5 squares plus the outside — which is 7 if you count the outer region as one of the pentagons' faces. ✓

Why Euler's formula is so powerful. It relates three quantities with no reference to the shape at all. Squash, stretch or redraw the graph however you like, and V-E+F stays at 2. That invariance is the beginning of topology, and the same argument gives the five Platonic solids and no more.

Problem 10 — Equivalence classes

Define a\sim b on the whole numbers to mean a-b is divisible by 4. Prove it is an equivalence relation and describe its classes.

Solution

Step 1 — reflexive. Is a\sim a? That needs a-a = 0 to be divisible by 4. And 0 = 4\times0 ✓

Step 2 — symmetric. If a\sim b then a-b = 4k for some whole k. Then

b-a = -(a-b) = -4k = 4(-k)

which is divisible by 4, so b\sim a ✓

Step 3 — transitive. If a\sim b and b\sim c, then a-b = 4k and b-c=4l. Add them:

(a-b)+(b-c) = a-c = 4k+4l = 4(k+l)

divisible by 4, so a\sim c ✓

All three hold, so it is an equivalence relation. \blacksquare

Step 4 — the classes. Two numbers are related exactly when they leave the same remainder on division by 4. The possible remainders are 0, 1, 2, 3, so there are four classes:

[0] = \{\ldots,-8,-4,0,4,8,\ldots\}

[1] = \{\ldots,-7,-3,1,5,9,\ldots\}

[2] = \{\ldots,-6,-2,2,6,10,\ldots\}

[3] = \{\ldots,-5,-1,3,7,11,\ldots\}

Check the defining property of a partition: every whole number is in exactly one class, and no two classes overlap ✓

Why this matters. These four classes are the number system \mathbb{Z}_4 used in 1.6. The equivalence relation is what makes it legal to do arithmetic on classes rather than numbers: because the relation respects addition and multiplication, [2]+[3] = [1] is a well-defined statement, not depending on which representative you picked. Every quotient structure in mathematics — modular arithmetic, fractions, vector spaces modulo a subspace — is an equivalence relation being used this way.

Problem 11 — Counting paths with a matrix

For the graph with vertices \{1,2,3\} and edges \{1\text{–}2, 2\text{–}3, 1\text{–}3\}, use the adjacency matrix to count walks of length 3 from vertex 1 back to vertex 1.

Solution

Step 1 — write the adjacency matrix. Every pair is joined, so

A = \begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}

The diagonal is zero because there are no loops.

Step 2 — compute A^2.

Entry (1,1): row 1 dotted with column 1 = (0)(0)+(1)(1)+(1)(1) = 2 Entry (1,2): (0)(1)+(1)(0)+(1)(1) = 1

By symmetry the whole matrix is

A^2 = \begin{pmatrix}2&1&1\\1&2&1\\1&1&2\end{pmatrix}

Read it: there are 2 walks of length 2 from a vertex back to itself (out to either neighbour and back), and 1 walk of length 2 between two different vertices (via the third).

Step 3 — compute A^3 = A^2\cdot A.

Entry (1,1): row 1 of A^2 dotted with column 1 of A:

(2)(0)+(1)(1)+(1)(1) = 2

Entry (1,2): row 1 of A^2 with column 2 of A:

(2)(1)+(1)(0)+(1)(1) = 3

A^3 = \begin{pmatrix}2&3&3\\3&2&3\\3&3&2\end{pmatrix}

Answer: 2 walks of length 3 from vertex 1 back to itself.

Step 4 — list them by hand to confirm. Starting and ending at 1, three steps:

1\to2\to3\to1 \qquad\text{and}\qquad 1\to3\to2\to1

Exactly two ✓ — the triangle traversed in each direction.

What the off-diagonal 3 means. There are 3 walks of length 3 from vertex 1 to vertex 2: 1\to2\to1\to2, 1\to3\to1\to2, and 1\to2\to3\to2. Walks may repeat vertices and edges; the matrix counts walks, not paths, and confusing the two is the usual error.

Where this is used. The trace of A^3 divided by 6 counts the triangles in a graph — here \frac{2+2+2}{6} = 1, correctly one triangle. Social networks compute exactly this to measure how tightly knit a community is.

Problem 12 — Everything at once: a tournament

Eight teams play a knockout tournament. (a) How many matches in total? (b) How many possible brackets, if the initial seeding is fixed? (c) Show that in any group of the 8 teams' captains, if every pair either has or has not met before, some 3 have all met or some 3 have never met — or explain why 8 is more than enough.

Solution

(a) The number of matches. The clever argument beats the arithmetic here.

Every match eliminates exactly one team. The tournament ends with 1 champion and 7 eliminated teams. So there must be exactly 7 matches.

Check by rounds: 4+2+1 = 7 ✓ And the argument generalises instantly — a knockout with n teams needs n-1 matches, whatever the bracket shape, even with byes.

(b) The number of possible outcomes. With the bracket fixed, each of the 7 matches has 2 possible winners, and the choices are independent:

2^7 = 128

Answer: 128 possible complete tournament outcomes.

For a 64-team tournament that becomes 2^{63} \approx 9.2\times10^{18}, which is why nobody has ever filled in a perfect bracket and why the odds quoted for doing so are astronomical even after accounting for the fact that some teams are much better than others.

(c) The Ramsey question. Problem 5 proved that 6 people suffice to force three mutual acquaintances or three mutual strangers. Eight is more than six, so the conclusion holds for eight as well — and with room to spare.

Why "more is easier" is worth stating explicitly. If a property is forced in any group of 6, it is forced in any group of 8: pick any 6 of the 8 and apply the earlier result. The monochromatic triangle you find among those 6 is still a monochromatic triangle in the group of 8. A Ramsey-type result, once proved at its threshold, holds for everything above it, which is exactly why finding the threshold is the whole difficulty.

Answers: (a) 7 matches; (b) 128 outcomes; (c) yes, since 8 exceeds the threshold of 6 established in Problem 5.

What links the three parts. Part (a) is a counting argument that avoids counting. Part (b) is the multiplication principle. Part (c) is pigeonhole plus case analysis. Those three tools — count cleverly, multiply independent choices, and force a case by counting boxes — cover most of what discrete mathematics does, and all three appeared in one tournament.

Next: Part 9 — Transforms & Signals, where the sums of this Part become infinite and turn any signal into a set of frequencies.