Discrete Math Practice

GitHub Changelog - Last modified Aug 24, 2026

Suggest edit

0 of 27 completed

Create worksheet

Title

Selected problems

No problems selected.

Difficulty

Direct

1.1Negate a Universal Implication

Exam I | Problem 1.1 |

Write the negation of the statement:

\forall n \in \mathbb{Z},\ n \text{ prime } \to n \text{ odd}

Solution

The negation of $\forall n\, P(n)$ is $\exists n\, \neg P(n)$.

Here $P(n)$ is the implication "if $n$ is prime, then $n$ is odd." The negation of an implication is:

p \to q \equiv \neg p \lor q

so its negation is:

p \land \neg q

Therefore the negation is:

\exists n \in \mathbb{Z},\ n \text{ is prime and } n \text{ is not odd}

Equivalently, there exists an integer $n$ that is prime and even.

1.2Write the Contrapositive

Exam I | Problem 1.2 |

Write the contrapositive of the statement:

\text{If } n \text{ is divisible by } 4,\text{ then } n \text{ is even.}

Solution

For a statement $p \to q$, the contrapositive is $\neg q \to \neg p$.

Here:

$p$: $n$ is divisible by $4$
$q$: $n$ is even

So the contrapositive is:

\text{If } n \text{ is not even, then } n \text{ is not divisible by } 4.

Since integers are either even or odd, this can also be written as:

\text{If } n \text{ is odd, then } n \text{ is not divisible by } 4.

1.3Use De Morgan's Law

Exam I | Problem 1.3 |

Simplify the negation:

\neg (p \lor q)

Solution

By De Morgan's law,

\neg (p \lor q) \equiv \neg p \land \neg q

So the simplified form is:

\neg p \land \neg q

1.4Compute a Set Union and Intersection

Exam I | Problem 1.4 |

Let

A = \{1,2,3,5\} \quad \text{and} \quad B = \{3,4,5,6\}.

Find $A \cap B$ and $A \cup B$.

Solution

The elements common to both sets are $3$ and $5$, so:

A \cap B = \{3,5\}

The union contains every element that appears in either set:

A \cup B = \{1,2,3,4,5,6\}

1.5Count the Subsets of a Set

Exam I | Problem 1.5 |

If a set $A$ has $4$ elements, how many subsets does $A$ have?

Solution

A set with $n$ elements has $2^n$ subsets.

Here $n=4$, so the number of subsets is

$$ 2^4 = 16 $$

1.6Classify a Function

Exam I | Problem 1.6 |

Let $f : \{1,2,3\} \to \{a,b\}$ be defined by

f(1)=a,\quad f(2)=b,\quad f(3)=a.

Is $f$ injective, surjective, both, or neither?

Solution

The function is not injective because different inputs can give the same output:

f(1)=a \quad \text{and} \quad f(3)=a

The function is surjective because both elements of the codomain are hit:

a \text{ is hit by } 1 \text{ and } 3,\quad b \text{ is hit by } 2

So $f$ is surjective but not injective.

1.7Find the Size of a Cartesian Product

Exam I | Problem 1.7 |

If $|A| = 3$ and $|B| = 7$, how many ordered pairs are in $A \times B$?

Solution

For finite sets,

|A \times B| = |A||B|

|A \times B| = 3 \cdot 7 = 21

1.8Check a Partial Order

Exam I | Problem 1.8 |

Let

R = \{(1,1),(2,2),(3,3),(1,2),(1,3),(2,3)\}

be a relation on $\{1,2,3\}$. Is $R$ a partial order?

Solution

Check the three conditions:

Reflexive: $(1,1)$, $(2,2)$, and $(3,3)$ are all in $R$.
Antisymmetric: there is no pair $(a,b)$ and $(b,a)$ with $a \neq b$.
Transitive: $(1,2)$ and $(2,3)$ imply $(1,3)$, and the other required transitive cases are also present.

So $R$ is a partial order.

1.9Solve a Congruence Modulo 5

Exam I | Problem 1.9 |

Solve for $x$:

2x \equiv 1 \pmod 5

Solution

We need the multiplicative inverse of $2$ modulo $5$.

Since

2 \cdot 3 = 6 \equiv 1 \pmod 5,

the inverse of $2$ mod $5$ is $3$. Multiply both sides by $3$:

x \equiv 3 \pmod 5

1.10Count the Edges in a Tree

Exam I | Problem 1.10 |

A tree has $14$ vertices. How many edges does it have?

Solution

For a tree with $n$ vertices, the number of edges is

$$ n - 1 $$

So with $n=14$,

$$ |E| = 14 - 1 = 13 $$

Difficulty

Integrated

2.1Negate a Quantified Statement

Exam II | Problem 2.1 |

Write the negation of:

\forall n \in \mathbb{Z},\ n \text{ even } \to n^2 \text{ even}

Solution

The negation of $\forall n\, P(n)$ is $\exists n\, \neg P(n)$.

The negation of $p \to q$ is $p \land \neg q$.

So the negation is:

\exists n \in \mathbb{Z},\ n \text{ is even and } n^2 \text{ is not even}

2.2Use Congruence Modulo 4

Exam II | Problem 2.2 |

Consider the relation on integers defined by

a \sim b \iff a \equiv b \pmod 4.

Explain why this is an equivalence relation, and describe the equivalence class of $7$.

Solution

Congruence modulo $4$ is:

Reflexive, because $a \equiv a \pmod 4$
Symmetric, because if $a \equiv b \pmod 4$, then $b \equiv a \pmod 4$
Transitive, because if $a \equiv b \pmod 4$ and $b \equiv c \pmod 4$, then $a \equiv c \pmod 4$

So it is an equivalence relation.

The class of $7$ is all integers congruent to $7$ mod $4$, which is the same as all integers congruent to $3$ mod $4$:

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

2.3Prove a Divisibility Claim by Contrapositive

Exam II | Problem 2.3 |

Prove that if $n^2$ is even, then $n$ is even.

Solution

Use the contrapositive: prove that if $n$ is odd, then $n^2$ is odd.

If $n$ is odd, then $n = 2k+1$ for some integer $k$. Then

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

which is odd.

So the contrapositive is true, and therefore the original statement is true.

2.4Prove a Summation Formula by Induction

Exam II | Problem 2.4 |

Use mathematical induction to prove that

1 + 2 + \cdots + n = \frac{n(n+1)}{2}

for all $n \ge 1$.

Solution

Base case $n=1$:

1 = \frac{1 \cdot 2}{2}

so the formula holds.

Inductive step: assume the formula holds for $n=k$:

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

Then

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

Factor out $(k+1)$:

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

This is exactly the formula with $n=k+1$. Therefore the statement holds for all $n \ge 1$.

2.5Count Committees with a Required Member

Exam II | Problem 2.5 |

From a group of $8$ students, how many $3$-person committees can be formed if one specific student must be included?

Solution

If one student must be included, choose the other $2$ committee members from the remaining $7$ students.

The number of ways is

\binom{7}{2} = 21

2.6Compute a Conditional Probability

Exam II | Problem 2.6 |

In a club of $12$ students, $7$ are in math club and $4$ are in both math club and robotics club.

If a student is known to be in math club, what is the probability that the student is also in robotics club?

Solution

Use conditional probability:

P(R \mid M) = \frac{P(R \cap M)}{P(M)}

In counting form, this is

\frac{4}{7}

So the probability is $\frac{4}{7}$.

2.7Apply the Euclidean Algorithm

Exam II | Problem 2.7 |

Find $\gcd(252,198)$.

Solution

Use the Euclidean algorithm:

$$ 252 = 198 + 54 $$

198 = 3\cdot 54 + 36

54 = 1\cdot 36 + 18

36 = 2\cdot 18 + 0

The last nonzero remainder is

$$ 18 $$

\gcd(252,198) = 18

2.8Compare Two Growth Rates

Exam II | Problem 2.8 |

Which grows faster as $n$ becomes large: $n \log n$ or $n^2$?

Solution

Compare the ratio:

\frac{n^2}{n \log n} = \frac{n}{\log n}

This ratio grows without bound as $n$ increases, so $n^2$ grows faster.

Equivalently,

n \log n = O(n^2)

but $n^2$ is not $O(n \log n)$.

Difficulty

Applied

3.1Count Committees with a Restriction

Final | Problem 3.1 |

A school needs a $4$-person committee from $10$ students. Two students are the team captains, and the committee must include at least one captain.

How many committees are possible?

Solution

Count all committees, then subtract those with no captains.

Total committees:

\binom{10}{4} = 210

Committees with no captains are chosen from the other $8$ students:

\binom{8}{4} = 70

So the number with at least one captain is

$$ 210 - 70 = 140 $$

3.2Apply the Pigeonhole Principle

Final | Problem 3.2 |

What is the smallest number of students needed to guarantee that at least $3$ students were born in the same month?

Solution

There are $12$ months, so there are $12$ boxes.

To avoid having $3$ students in any one month, you can place at most $2$ students in each month:

12 \cdot 2 = 24

One more student forces some month to contain at least $3$ students.

So the smallest number is

$$ 25 $$

3.3Find the Expected Value of a Simple Game

Final | Problem 3.3 |

A fair die is rolled. You win \$5 if the result is even and lose \$2 if the result is odd. What is the expected value of the game?

Solution

The probability of rolling an even number is $\frac{1}{2}$, and the probability of rolling an odd number is $\frac{1}{2}$.

So the expected value is

\mathbb{E}[X] = \frac{1}{2}(5) + \frac{1}{2}(-2)

\mathbb{E}[X] = \frac{3}{2}

So the expected value is \$1.50.

3.4Use Modular Arithmetic on a Calendar

Final | Problem 3.4 |

Today is Wednesday. What day of the week will it be $100$ days from now?

Solution

Days of the week repeat every $7$ days, so compute

100 \bmod 7 = 2

So $100$ days from Wednesday is $2$ days later:

Thursday.

3.5Solve a Geometric Recurrence

Final | Problem 3.5 |

A bacteria culture starts with $2$ bacteria and triples each hour.

If $a_n$ is the number of bacteria after $n$ hours, find a formula for $a_n$ and compute $a_4$.

Solution

The recurrence is

a_0 = 2,\quad a_n = 3a_{n-1}

This is a geometric recurrence, so the explicit formula is

a_n = 2 \cdot 3^n

Now evaluate at $n=4$:

a_4 = 2 \cdot 3^4 = 2 \cdot 81 = 162

Difficulty

Challenge

4.1Prove Prime Factorization by Strong Induction

Final | Problem 4.1 |

Prove that every integer $n \ge 2$ can be written as a product of primes.

Solution

We use strong induction.

Base case: $n=2$. The number $2$ is prime, so it is already a product of primes.

Inductive step: assume every integer from $2$ through $k$ can be written as a product of primes. We prove the claim for $k+1$.

If $k+1$ is prime, then it is already a product of primes.
If $k+1$ is composite, then

$$ k+1 = ab $$

for some integers $a,b$ with

2 \le a \le k,\quad 2 \le b \le k

By the strong inductive hypothesis, both $a$ and $b$ can be written as products of primes. Multiplying those factorizations gives a product of primes for $k+1$.

Therefore every integer $n \ge 2$ can be written as a product of primes.

4.2Count Multiples with Inclusion-Exclusion

Final | Problem 4.2 |

How many integers from $1$ to $100$ are divisible by $2$, $3$, or $5$?

Solution

Use inclusion-exclusion.

Counts of multiples:

\left\lfloor \frac{100}{2} \right\rfloor = 50,\quad \left\lfloor \frac{100}{3} \right\rfloor = 33,\quad \left\lfloor \frac{100}{5} \right\rfloor = 20

Subtract overlaps:

\left\lfloor \frac{100}{6} \right\rfloor = 16,\quad \left\lfloor \frac{100}{10} \right\rfloor = 10,\quad \left\lfloor \frac{100}{15} \right\rfloor = 6

Add back the triple overlap:

\left\lfloor \frac{100}{30} \right\rfloor = 3

So the total is

$$ 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74 $$

4.3Use Degrees to Test a Tree

Final | Problem 4.3 |

A connected graph has $6$ vertices with degree sequence

$$ 3,3,2,2,1,1. $$

Use the handshaking lemma to find the number of edges, then decide whether the graph can be a tree.

Solution

First add the degrees:

$$ 3+3+2+2+1+1 = 12 $$

By the handshaking lemma,

$$ 2|E| = 12 $$

$$ |E| = 6 $$

A tree with $6$ vertices must have

$$ 6 - 1 = 5 $$

edges. Since this graph has $6$ edges, it cannot be a tree.

4.4Verify a Loop Invariant

Final | Problem 4.4 |

Consider the algorithm:

total = 0
for k from 1 to n:
    total = total + k

State a loop invariant and use it to explain why the algorithm returns

1 + 2 + \cdots + n.

Solution

A good loop invariant is:

After the loop has processed the numbers $1,2,\dots,k$, the variable total equals $1+2+\cdots+k$.

Why it works:

Before the loop starts, total = 0, which matches the sum of no terms.
Each iteration adds the next integer, so if the invariant is true before an iteration, it remains true after that iteration.
When the loop finishes, $k=n$, so total equals

1 + 2 + \cdots + n

Therefore the algorithm is correct.