Appendix D List of Examples and Exercises
Chapter 1 Review of MAT102
Section 1.1 Sets and Functions
Checkpoint 1.1.2 Prove Set Inclusion
Checkpoint 1.1.6 Injective, surjective, bijective, or none?
Checkpoint 1.1.9 Prove Theorem 1.1.8
Checkpoint 1.1.11 There are as many natural numbers as odd integers
Checkpoint 1.1.13 Cardinality of a Power Set
Section 1.2 Logic and Proof Techniques
Activity 1.2.1 Review of Proofs
Checkpoint 1.2.2 Practice Induction
Checkpoint 1.2.3 Fibonacci Sequence
Checkpoint 1.2.4 Tiling
Section 1.3 Integers and Divisibility
Checkpoint 1.3.3 Verify Theorem 1.3.2
Checkpoint 1.3.5 Compute the GCDs
Checkpoint 1.3.6 Property of GCDs
Checkpoint 1.3.8 Find all Integer Solutions
Checkpoint 1.3.9 No Integer Solutions
Checkpoint 1.3.10 \(ax + by = d\) has Integer Solutions \(\Leftrightarrow \gcd(a,b) \mid d\)
Checkpoint 1.3.12 Prove Lemma 1.3.11
Checkpoint 1.3.13 Another Divisibility Property
Chapter 2 Counting Techniques
Section 2.1 The Basic Counting Principles
Example 2.1.1 First Counting Example
Checkpoint 2.1.2 Concert Seating
Example 2.1.3 Dog Adoption
Checkpoint 2.1.4 Socks!
Checkpoint 2.1.5 Exam Counts
Checkpoint 2.1.8 Twitter Followers
Checkpoint 2.1.10 Counting Outfits
Checkpoint 2.1.11 Proof of the Product Rule
Example 2.1.12 Multiple Choice Exam
Checkpoint 2.1.13 Concert Seating with \(n\) people
Example 2.1.16 Dog Adoption, again
Checkpoint 2.1.17 Trip Planning
Section 2.2 Permutations and Combinations
Example 2.2.3 Counting Bijections
Checkpoint 2.2.4 EQUATION
Example 2.2.7 Student Council Representatives
Checkpoint 2.2.8 ZAHLEN
Example 2.2.9 Repeated Letters
Checkpoint 2.2.11 MISSISSAUGA
Checkpoint 2.2.12 MATHEMATICS
Checkpoint 2.2.13 Esports Tournament
Example 2.2.14 Picking Bridesmaids
Example 2.2.17 Counting Cards
Checkpoint 2.2.18 Esports Tournament, again
Checkpoint 2.2.19 Two Ways of Counting
Exploration 2.2.1 Early Combinatorics
Section 2.3 Binomial Coefficients
Exploration 2.3.1 The Meru Prastaara (The Holy Mountain)
Checkpoint 2.3.4 Continue the Triangle
Checkpoint 2.3.6 Coefficient of \(x^4y^7\) in \((x+y)^{11}\)
Checkpoint 2.3.7 Coefficient of \(a^2b^3\)
Checkpoint 2.3.8 Prove that \(\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n\)
Example 2.3.9 Lattice Paths
Checkpoint 2.3.10 Lattice Paths to \((a,b)\)
Checkpoint 2.3.11 Lattice Paths, specific numbers
Checkpoint 2.3.12 Lattice Paths and Pascal's Formula
Section 2.4 The Balls in Bins Formula
Example 2.4.1 Multiple Choice, again
Example 2.4.3 Rice Advice
Checkpoint 2.4.4 Rice Advice Exercise
Checkpoint 2.4.7 Apples to Students
Exploration 2.4.1 Nonnegative integer solutions
Checkpoint 2.4.9 Apply Proposition 2.4.8
Checkpoint 2.4.10 Nonnegative integer solutions with additional constraints
Section 2.5 Combinatorial Arguments
Checkpoint 2.5.1 Pascal's Formula, again
Checkpoint 2.5.3 Chairperson by Algebra
Example 2.5.4 Chairperson by Combinatorial Proof
Checkpoint 2.5.5 Prove \(n^2 = 2\binom{n}{2} + n\)
Checkpoint 2.5.6 Another proof of Checkpoint 2.3.8
Exercise 2.7.6 Fall 2022 Final Exam
Exercise 2.7.9 Fall 2022 Term Test
Exercise 2.7.19 Winter 2021 Term Test
Exercise 2.7.21 Fall 2019 Term Test
Exercise 2.7.32 Winter 2021 Term Test
Exercise 2.7.34 Winter 2023 Term Test
Chapter 3 Pigeonhole and Inclusion-Exclusion
Section 3.1 The Pigeonhole Principle
Example 3.1.1 Splitting a Pizza
Example 3.1.2 Quiz Scores
Checkpoint 3.1.4 Prove the PHP
Checkpoint 3.1.6 Same Last Digit
Checkpoint 3.1.7 Difference Divisible by 10
Example 3.1.8 Sum to 8
Checkpoint 3.1.9 Sum to \(2n\)
Example 3.1.10 Sum or Difference Divisible by 8
Checkpoint 3.1.11 Six is Best Possible
Checkpoint 3.1.12 Sum or Difference Divisible by \(2n\)
Example 3.1.13 Number of Friends
Checkpoint 3.1.14 One Divides Another
Checkpoint 3.1.15 Tracking Showers
Section 3.2 Principle of Inclusion-Exclusion
Example 3.2.1 Not Divisible by 3
Example 3.2.2 Not Divisible by 3 or 4
Checkpoint 3.2.4 Not Divisible by 7 or 11
Checkpoint 3.2.5 Not Divisible by 3, 7, or 11
Checkpoint 3.2.7 PIE for Four Sets
Example 3.2.8 Word Rearragements
Checkpoint 3.2.9 Relatively Prime Numbers
Exploration 3.2.1 Euler's Totient Function
Checkpoint 3.2.10 Compute \(\phi(100)\) and \(\phi(135)\)
Checkpoint 3.2.11 One Card of Each Suit
Checkpoint 3.2.12 Nonnegative Integer Solutions
Section 3.3 Application: Derangements
Example 3.3.2 Derangements of 3- and 4-sets
Exploration 3.3.1 Deriving \(D_n\)
Checkpoint 3.3.5 Compute \(D_4\)
Checkpoint 3.3.6 The Ratio \(D_n/n!\)
Exercise 3.4.4 Fall 2019 Term Test
Exercise 3.4.9 Fall 2021 Final
Exercise 3.4.10 Winter 2022 Term Test
Exercise 3.4.19 Winter 2022 Final
Chapter 4 Congruence Modulo \(n\)
Section 4.1 Equivalence Relations
Example 4.1.2 A Simple Relation
Checkpoint 4.1.3 Counting Relations
Checkpoint 4.1.4 Counting Relations and Functions
Checkpoint 4.1.6 Equivalence Relation or Not?
Checkpoint 4.1.8 List the Equivalence Classes
Checkpoint 4.1.11 Prove Theorem 4.1.10 (a)
Checkpoint 4.1.12 Prove Theorem 4.1.10 (b)
Checkpoint 4.1.13 Describe the Classes I
Checkpoint 4.1.14 Describe the Classes II
Checkpoint 4.1.15 Give Examples
Example 4.1.17 Multiple Possible Representatives
Checkpoint 4.1.18 Objects in the Same Class are Equivalent
Section 4.2 Congruences and their Properties
Example 4.2.2 Simple Example
Checkpoint 4.2.3 Congruent iff Same Remainder
Example 4.2.4 Days of the Week
Checkpoint 4.2.5 New Relationship
Example 4.2.7 Modulo 5
Checkpoint 4.2.9 Prove Proposition 4.2.8
Example 4.2.10 Substituting Congruent Numbers
Checkpoint 4.2.11 Modulo 9
Checkpoint 4.2.13 Compute Remainders
Example 4.2.14 Division is not as Nice
Checkpoint 4.2.16 Justify It
Section 4.3 Solving Congruences
Example 4.3.1 Solving for \(x\)
Example 4.3.2 Solve for \(x\)
Checkpoint 4.3.3 Solve Each Congruence
Checkpoint 4.3.4 Solve Another One
Checkpoint 4.3.6 Checkpoint 4.3.4 Again
Checkpoint 4.3.7 When does \(a\) have an Inverse Modulo \(n\text{?}\)
Checkpoint 4.3.9 The Multiplicative Inverse is Unique
Checkpoint 4.3.10 Uniqueness of Solutions
Checkpoint 4.3.11 Solve These Congruences
Checkpoint 4.3.12 How Many Solutions?
Section 4.4 Euler's Theorem
Example 4.4.2 \(\phi(1)\) and \(\phi(8)\)
Checkpoint 4.4.3 \(\phi(n)\) for small \(n\)
Checkpoint 4.4.6 Converse of Proposition 4.4.5
Checkpoint 4.4.7 \(\phi(p^k)\)
Checkpoint 4.4.8 \(\phi(pq)\)
Example 4.4.11 Example of Theorem 4.4.9
Example 4.4.12 Compute the Remainder
Checkpoint 4.4.13 Compute the Remainder
Example 4.4.14 Why Theorem 4.4.9 holds, for \(a = 4\) and \(n = 9\)
Checkpoint 4.4.15 Repeat the Argument
Exploration 4.4.1 Primality Testing
Section 4.5 The Chinese Remainder Theorem
Exploration 4.5.1 Sun Zi's Problem
Checkpoint 4.5.1 Two Congruences
Checkpoint 4.5.3 Two Congruences, again
Checkpoint 4.5.4 Theorem 4.5.2, existence
Checkpoint 4.5.5 Theorem 4.5.2, uniqueness
Checkpoint 4.5.7 Sun Zi's System
Checkpoint 4.5.8 Practice
Example 4.5.9 From \(\mathbb{Z}_{10}\) to \(\mathbb{Z}_2 \times \mathbb{Z}_5\)
Checkpoint 4.5.10 Computing large powers
Exercise 4.6.8 Winter 2018 Final
Chapter 5 Graph Theory
Section 5.1 Modeling with Graphs
Example 5.1.1 The Five-Room Problem
Example 5.1.2 Find a Trail on a Graph
Checkpoint 5.1.3 Small Wedding Reception
Checkpoint 5.1.4 Medicine Delivery
Checkpoint 5.1.5 Counting Collaborators
Section 5.2 Basic Definitions
Example 5.2.3 First Graph
Checkpoint 5.2.4 Draw These Graphs
Checkpoint 5.2.5 List Vertices and Edges
Example 5.2.7 Degree sequence
Checkpoint 5.2.8 Write the Degree Sequence
Checkpoint 5.2.9 Zero Degrees
Checkpoint 5.2.12 Verify Theorem 5.2.10
Checkpoint 5.2.13 Even Number of Odd Degree Vertices
Checkpoint 5.2.14 Handshakes at a [Pre-pandemic] Party
Example 5.2.16 Counting Collaborators
Checkpoint 5.2.17 Degree Sequence 3, 2, 1, 0
Checkpoint 5.2.18 Degree Sequence with 0 and \(n-1\)
Checkpoint 5.2.19 Maximum Degree Sum
Section 5.3 Eulerian Graphs
Example 5.3.2 A Trail
Example 5.3.4 Eulerian and non-Eulerian Graphs
Example 5.3.7 A Disconnected Graph
Example 5.3.9 Solution to the Five-Room Problem
Example 5.3.10 Disconnected, so not Eulerian
Checkpoint 5.3.11 Find Eulerian Trails
Example 5.3.14 Examples
Checkpoint 5.3.15 Compute \(|E(K_n)|\)
Checkpoint 5.3.16 Are \(C_n\) and \(K_n\) Eulerian?
Checkpoint 5.3.17 Find Eulerian Trails on \(K_5\) and \(K_7\)
Section 5.4 Isomorphisms and Subgraphs
Example 5.4.1 Are These the Same Graphs?
Checkpoint 5.4.4 Verify and Construct Isomorphisms
Checkpoint 5.4.5 Which Pairs are Isomorphic?
Checkpoint 5.4.7 Isomorphic Graphs have the Same Degree Sequence
Checkpoint 5.4.8 Check Degree Sequences
Checkpoint 5.4.9 Same Degree Sequence does not imply Isomorphism
Example 5.4.11 Subgraph Example
Example 5.4.12 Subgraphs for Non-isomorphism
Example 5.4.13 Prove Graph Isomorphism
Checkpoint 5.4.14 Prove Graph Isomorphism
Example 5.4.16 A Graph and its Complement
Checkpoint 5.4.18 Verify Proposition 5.4.17
Checkpoint 5.4.19 Prove Proposition 5.4.17
Section 5.5 Connectedness and Trees
Example 5.5.2 \(P_6\text{,}\) or the Path on Six Vertices
Checkpoint 5.5.4 \(P_6\) is connected
Example 5.5.5 Connected and Disconnected
Checkpoint 5.5.6 Which Graphs are Connected?
Checkpoint 5.5.7 Connectedness is Invariant under Isomorphism
Example 5.5.9 Trees and Forests and Actual Trees
Checkpoint 5.5.10 Find all Trees
Exploration 5.5.1 Proving Lemma 5.5.13
Checkpoint 5.5.14 Maximal Paths in Graphs
Checkpoint 5.5.15 Verify Lemma 5.5.13
Checkpoint 5.5.16 Maximum Leaves
Checkpoint 5.5.17 Leaves in a Forest
Checkpoint 5.5.21 Connectedness is Required
Section 5.6 Bipartite Graphs
Example 5.6.2 \(P_6\) is Bipartite
Checkpoint 5.6.3 Which Graphs are Bipartite?
Checkpoint 5.6.4 Small Wedding Reception
Checkpoint 5.6.6 Theorem 5.6.5, Only If
Checkpoint 5.6.7 Trees are Bipartite
Example 5.6.9 \(K_{2,4}\)
Checkpoint 5.6.10 Draw these Graphs
Checkpoint 5.6.11 Which \(K_{m,n}\) are Trees?
Section 5.7 Hamiltonian Graphs
Example 5.7.2 A Hamiltonian Graph
Checkpoint 5.7.3 Hamilton's Puzzle
Exploration 5.7.1 Knight's Tours
Example 5.7.4 A Non-Hamiltonian Graph
Checkpoint 5.7.5 Least Cost Hamiltonian Cycle
Checkpoint 5.7.6 Medicine Delivery
Checkpoint 5.7.8 Verify Theorem 5.7.7
Checkpoint 5.7.9 Theorem 5.7.7 is Not Necessary
Exercise 5.8.7 Winter 2016 Final
Exercise 5.8.11 Winter 2017 Final
Exercise 5.8.27 Fall 2016 Final
Exercise 5.8.28 Fall 2020 Final
Section A.1 Introduction to LaTeX
Example A.1.1 LaTeX example
Section A.2 Reading Mathematics
Example A.2.1 Short Proof Example
Checkpoint A.2.2 Questions about Example A.2.1
Checkpoint A.2.4 Reading Proposition A.2.5
Checkpoint A.2.6 Extra Practice
Section A.3 Writing Mathematics, Part I
Example A.3.2 Prove this identity
Checkpoint A.3.4 Grade and Reflect
Example A.3.5 Counting Problem
Section A.4 Writing Mathematics, Part II
Activity A.4.1 Complete sentence or not?
Example A.4.1 A Simple Inequality