Sample Problems and Solutions

The Proof's Pursuit: A Mathematical Tale

In lands of logic, sharp and keen,
Where numbers dance and minds are seen,
A theorem stood, so bold, so grand—
Yet proofless still, like castles of sand.

But first came tables, rows aligned,
With truth laid bare for any mind.
Each case displayed, both false and true,
No hidden paths to misconstrue.

With chalk in hand, the wizards came,
Each hoping they could stake their claim.
A contradiction! A bijection!
A proof by cases—pure perfection!

Then came Induction, noble and proud,
"I'll prove for one, then for the crowd!
If $n$ is true, and $n+1$,
The proof is done! Oh, what fun!"

Then Recursion stepped in with grace,
"A problem small sets up the case.
Solve the base, then build anew,
Each step defined by those we knew."

Then came Contradiction’s art,
A devious play, a cunning start.
"Assume I'm wrong, let chaos reign,
Oh dear! The logic breaks in twain!"

Contraposition took its turn,
With logic crisp and truth to burn.
"If not B, then not A too,
The proof holds firm, the claim is true!"

Next, Direct Proof took the stage,
With elegance upon the page.
"A to B, so crisp and clean,
No tricks, no traps—just what is seen."

Proof by Cases made its stand,
With many paths already planned.
"If A is this, or A is that,
We check them all—now that's a fact!"

Then Counterexample, swift and sly,
Declared, "One case can make it die!
A single flaw, a fatal seam,
Unravels all—no need to dream."

Reduction came, so sly and slick,
"Transform it here—just one neat trick!
A hard old proof made easy now,
Who needs brute force? Just take a bow!"

Then came Elements, calm and clear,
"Take one object—bring it near.
If it belongs, we plainly show,
Through sets it travels, to and fro."

Then One-to-One, so sharp and bright,
Mapped all things left to right.
"A bijection, neat and true,
Two sets the same—just look, you'll see too!"

Equivalence rose with structured grace,
"Relations bind in classes’ space.
Reflexive, symmetric, transitive too,
We group the world in partitions true."

The audience gasped, the scribes took note,
The theorem stood, as if it wrote,
"I stand, I stand! I am complete!"
The mathematicians rose to their feet.

Yet lurking still in shadow's guise,
A figure grinned with knowing eyes.
From Gödel’s lips, a whisper grew:
"Not all theorems can be proved!"

And so they sighed, both sad and wise,
For proofs may shine, but truth still hides.
Yet undeterred, they took their quills,
For math rewards the steadfast wills.

So let us strive, with joy and glee,
For proofs are puzzles, wild and free!
Through logic’s maze, we twist and wind—
Who knows what wonders we may find?

Solution

1. $p \land \sim q$
2. $p \land \sim q$
3. $p \oplus q$
   (alternate answer) $(p \land \sim q) \lor (\sim p \land q)$
4. $q \land \sim p$
5. $p \land \sim q$
6. $(q \land \sim p) \lor (\sim p \lor q)$
7. $(\sim q \lor p) \lor (p \land \sim q)$
8. $p \oplus q$
   (alternate answer) $(q \land \sim p) \lor (p \land \sim q)$
9. $(\sim q \lor p) \lor (\sim p \lor q) \equiv \mathbf{t}$

Solution

$\fbox{The deduction rule is invalid.}$

Solution

$\fbox{The deduction rule is valid.}$

Solution

$\fbox{The deduction rule is valid (vacuous truth).}$

Solution

1. False ($p \land \sim p \equiv \textbf{c}$)
2. True
3. False ($p \oplus q \equiv (\sim p \land q) \lor (\sim q \land p)$)
4. False (Implication is not associative)
5. True

Solution

$\fbox{7 truth assignments.}$

Solution

Solution

Solution

1. $\exists x \in \mathbb{R}, P(x) \land \sim Q(x)$
2. $\forall x \in \mathbb{R}, \sim P(x) \lor \sim Q(x)$
3. $\exists x \in \mathbb{R}, \forall y \in \mathbb{R}, x^2 + y^2 \neq 1$
4. $\exists x, y \in \mathbb{Z}, (x \neq y) \land (\sim P(x) \lor \sim P(y))$
5. $\forall x \in \mathbb{N}, \sim P(x) \land \sim Q(x)$

Solution

1. $\forall S,\; C(S) \rightarrow M(S)$
2. $\exists S,\; C(S) \land M(S)$
3. $\forall S,\; \sim C(S) \rightarrow M(S)$
4. $\forall S_1,S_2,\; (C(S_1) \land M(S_1) \land C(S_2) \land \sim M(S_2)) \rightarrow G(S_1,S_2)$

Solution

1. $\forall A,\; C(A) \rightarrow \sim H(A)$
2. $\exists A,\; C(A) \land H(A)$
3. $\forall A,\; \sim C(A) \rightarrow (H(A) \lor F(A))$
4. $\forall A_1,A_2,\; (C(A_1) \land F(A_1) \land H(A_2) \land \sim F(A_2)) \rightarrow L(A_1,A_2)$

Solution

1. True. Integers are closed under multiplication.
2. True. There always exists a smaller integer.
3. False. Suppose $y=0$.
4. False. $\sqrt{2} + (-\sqrt{2}) = 0$.
5. True. This is the triangle inequality.

Solution

Proof by division into cases

Case 1: Both integers are even.
Let $a$ and $b$ be two even integers. Then

Case 2: Both integers are odd.
Let $a$ and $b$ be two odd integers. Then

Solution

Proof by contrapositive.

Contrapositive: If $n$ is even, then $n^{100}$ is even.

Proof: Assume $n$ is even. Then $n = 2k$ for some integer $k$. Now, consider $n^{100}$:

Since $2^{100}$ is a power of 2, it is clearly divisible by 2, so $n^{100}$ is even.
Thus, by contrapositive, if $n^{100}$ is odd, then $n$ must be odd. This completes the proof.

Solution

Let $p_1$ and $p_2$ be prime numbers greater than 2. Then

Solution

Proof 1: Contrapositive
Contrapositive: If at least one integer is even, their product is even.

Assume at least one integer is even. Let $a = 2k$ for some integer $k$.

Thus, if at least one integer is even, their product is even.
By contrapositive, if $a \times b$ is odd, both integers are odd.

Proof 2: Contradiction
Negation: The product of two integers is odd and one of the two integers is even.
Let $a$ and $b$ be two integers.
Assume $a \times b$ is odd, but one integer is even.
Let $a = 2k$ for some integer $k$. Then

Contradiction. Thus, both integers must be odd.

Solution

Direct proof

Given $a \mid b$ and $b \mid c$, there exist integers $k_1$ and $k_2$ such that:

Substitute $b = a \times k_1$ into $c = b \times k_2$ to get:

Therefore, $a \mid c$.

Solution

Direct proof.

Proof by contradiction.

Solution

1. False.
   Consider $\sqrt{2} \cdot \sqrt{2} = 2$.
   $\sqrt{2}$ is irrational but the product $2$ is rational.
2. False.
   Consider $\sqrt{2} + (2 - \sqrt{2}) = 2$.
   $\sqrt{2}$ and $2 - \sqrt{2}$ are positive irrational numbers but their sum $2$ is rational

Solution

Let $P(n): \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$.

Base case: For $n=1$,

$P(1): \sum_{i=1}^{1} i^2 = 1 = \frac{1 \times 2 \times 3}{6}$

Thus, the base case holds.

Inductive step: Assume $P(k)$ is true for some $k \ge 1$. We need to prove $P(k+1)$:

LHS of $P(k+1)$:

Thus, the inductive step holds.

Therefore, by mathematical induction, $P(n)$ is true for all $n \ge 1$.

Solution

Let $P(n): \prod_{i=1}^{n} 2i = 2^n \cdot n!$.

Base case: For $n=1$, the left-hand side is:

$2 = 2^1 \cdot 1! = 2$

Thus, $P(1)$ holds.

Inductive step: Assume $P(k)$ is true for some $k \ge 1$. We must prove $P(k+1)$:

LHS of $P(k+1)$:

Thus, the inductive step holds.

Therefore, by mathematical induction, $P(n)$ holds for all $n \in \mathbb{N}$.

Solution

Let $P(n): a_n \leq \frac{2}{n}$. We will prove $P(n)$ by induction for all $n \in \mathbb{N}$.

Base case:
For $n=1$, $a_1 = 2 \leq \frac{2}{1}$. (True)
For $n=2$, $a_2 = 1 \leq \frac{2}{2}$. (True)

Thus, $P(1)$ and $P(2)$ hold.

Inductive step: Assume $P(i)$ holds true for all $i \in [1,k]$ for some $k \ge 2$. We need to show that $P(k+1)$ holds.

LHS of $P(k+1)$:

Therefore, $a_{k+1} \leq \frac{2}{k+1}$, and $P(k+1)$ holds.

By induction, $P(n)$ is true for all $n \in \mathbb{N}$. Therefore, $a_n \leq \frac{2}{n}$ for all $n \in \mathbb{N}$.

Solution

Let $P(n): a_n < 3$. We will prove $P(n)$ by induction for all $n \in \mathbb{N}$.

Base cases
For $n=1$, $a_1 = 0 < 3$.
For $n=2$, $a_2 = 1 < 3$.
For $n=3$, $a_3 = 2 < 3$.

Thus, $P(1)$, $P(2)$, and $P(3)$ hold.

Inductive step: Assume $P(i)$ holds true for all $i \in [1,k]$ for some $k \ge 3$. We need to show that $P(k+1)$ holds.

LHS of $P(k+1)$:

Therefore, $a_{k+1} < 3$, and $P(k+1)$ holds.

By induction, $P(n)$ is true for all $n \in \mathbb{N}$. Therefore, $a_n < 3$ for all $n \in \mathbb{N}$.

Solution

Proof by contradiction.

Negation: Suppose that $A \subseteq B$ and $A-B$ is not an empty set.

Suppose $x \in A - B$.

Contradiction since $x \in B$ and $x \notin B$.

Hence, the negation is false and the original statement is true.

Solution

We will prove $(A \cup C) \cap (B \cup C) = C$ in two parts.

Part 1: $(A \cup C) \cap (B \cup C) \subseteq C$.

Let $x \in (A \cup C) \cap (B \cup C)$.

Therefore, $(A \cup C) \cap (B \cup C) \subseteq C$.

Part 2: $C \subseteq (A \cup C) \cap (B \cup C)$.

Let $x \in C$.

Therefore, $C \subseteq (A \cup C) \cap (B \cup C)$

Since both inclusions hold, we conclude that $(A \cup C) \cap (B \cup C) = C$.

Solution

To prove that $f$ is a one-to-one correspondence, we need to show that $f$ is both one-to-one and onto.

1. One-to-One:
A function $f$ is one-to-one $\forall a, b \in \mathbb{Z}^+$ if $f(a)=f(b)$ then $a=b$.

Simplifying:

2. Onto:
A function $f$ is onto if, for every $y \in \mathbb{O}^{+}$, there exists an $x \in \mathbb{Z}^{+}$ such that $f(x)=y$.
Let $y \in \mathbb{O}^{+}$. Since $\mathbb{O}^{+}=\{1,3,5,7,\dots\}$, we can write $y = 2x-1$. Solving for $x$:

Since $y$ is odd, $y+1$ is even, and $\frac{y+1}{2} \in \mathbb{Z}^{+}$. Hence, $f(x)=y$, proving $f$ is onto.

Conclusion:
Since $f$ is both one-to-one and onto, $f$ is a one-to-one correspondence.

Solution

Given that $1 \text{ kilogram} = 2.2046226218 \text{ pounds}$, we can express the function $f$ as:

where $x$ is the mass in pounds. The function maps from the set of nonnegative real numbers (including zero) to the set of nonnegative real numbers. Since $2.2046226218 > 0$, for any $x \ge 0$, $f(x)$ will also be nonnegative. Therefore, $f(x) \in \mathbb{R}^*$ for all $x \in \mathbb{R}^*$. Thus, $f$ is well-defined.

1. One-to-One:

To show that $f$ is injective, we need to prove that if $f(x_1)=f(x_2)$, then $x_1=x_2$.

Assume $f(x_1)=f(x_2)$:

Multiplying both sides by $2.2046226218$ (which is positive and does not change the equality) gives:

Thus, $f$ is injective.

2. Onto:

To show that $f$ is surjective, we need to prove that for every $y \in \mathbb{R}^*$, there exists an $x \in \mathbb{R}^*$ such that $f(x)=y$.

Let $y$ be any nonnegative real number. We want to find $x$ such that:

Solving for $x$ gives:

Since $y \ge 0$, it follows that $x = 2.2046226218y \ge 0$. Therefore, for every $y \in \mathbb{R}^*$, we can find an $x \in \mathbb{R}^*$ such that $f(x)=y$. Thus, $f$ is surjective.

Conclusion:

Since $f$ is both injective and surjective, we conclude that $f$ is a one-to-one correspondence (bijection) from $\mathbb{R}^*$ to $\mathbb{R}^*$. Thus, the function $f$ is a one-to-one correspondence.

Solution

To prove that the set consisting of numbers of the form $k^2$ or $2^k$, where $k \in \mathbb{N}$, is countable, we will first define the set clearly and then establish a one-to-one correspondence function.

Step 1: Define the Set
Let $S$ be the set defined as follows:

This means that $S$ contains all perfect squares and all powers of 2, where $k$ is a natural number.

Step 2: List the Set Elements
Perfect Squares: The elements of the form $k^2$ for $k = 1,2,3,\ldots$ are:
$1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 16, 5^2 = 25, 6^2 = 36, 7^2 = 49, 8^2 = 64, 9^2 = 81, \ldots$

Powers of 2: The elements of the form $2^k$ for $k=1,2,3,\ldots$ are:
$2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32, 2^6 = 64, 2^7 = 128, 2^8 = 256, \ldots$

Common elements:
$4$ appears as $2^2$ and $2^2$.
$16$ appears as $4^2$ and $2^4$.
$64$ appears as $8^2$ and $2^6$.
so on...

So, essentially, we will need to eliminate all numbers of the form $2^{\text{even}}$ to avoid double-counting.

Step 3: Create a One-to-One Correspondence
To show that the set $S$ is countable, we can create a function that maps each natural number $k$ to a unique element in $S$.

Define a function $f: \mathbb{N} \to S$ as follows:

Step 4: Diagram of the Function

Solution

1. $|A\cup B| = |A| + |B| - |A\cap B| = m + n - |A\cap B|$
2. $2^{mn}$
   ($|A \times B| = mn$. The number of subsets of $mn$ elements is $2^{mn}$.)
3. $2^{mn}$
   (Total number of binary relations from $A$ to $B$ is the total number of subsets of $A \times B$)
4. $n^{m}$
   (First input element can be mapped to any of $n$ output elements, so on till the $m$th input element)
5. $$ \left. \begin{cases} 0 & \text{if } m > n,\\ n \times (n-1) \times (n-2) \times \cdots \times (n-m+1) & \text{if } m \le n. \end{cases} \right\} $$ (First input element can be mapped to any of $n$ output elements, second input element can be mapped to any of remaining $(n-1)$ output elements, so on till the $m$th input element can be mapped to any of $(n-m+1)$ output elements)
6. $$ \left. \begin{cases} 0 & \text{if } m \ne n,\\ m! & \text{if } m = n. \end{cases} \right\} $$ (First input element can be mapped to any of $m$ output elements, second input element can be mapped to any of remaining $(m-1)$ output elements, so on till the $m$th input element can be mapped to the only remaining $1$ output element)

Solution

1. Reflexive:
For any $a \in \mathbb{Z}$, $a-a=0$ is divisible by 3. Hence, $a\,R\,a$ holds.

2. Symmetric:
If $a\,R\,b$, then $a-b=3k$ for some $k\in\mathbb{Z}$.
Thus, $b-a=-3k$, which is divisible by 3. Hence, $b\,R\,a$ holds.

3. Transitive:
If $a\,R\,b$ and $b\,R\,c$, then $a-b=3k$ and $b-c=3m$ for some $k,m\in\mathbb{Z}$.
Adding these gives $a-c=3(k+m)$, which is divisible by 3. Hence, $a\,R\,c$.

4. Equivalence Classes:
The equivalence classes are the sets of integers that leave a remainder of $0$, $1$, and $2$ when divided by $3$, as shown below:

Solution

1. Reflexive:
For any string $x$, we have $|x|=|x|$, so $x\,R\,x$ holds.

2. Symmetric:
If $x\,R\,y$, then $|x|=|y|$.
Thus, $|y|=|x|$, so $y\,R\,x$ holds.

3. Transitive:
If $x\,R\,y$ and $y\,R\,z$, then $|x|=|y|$ and $|y|=|z|$.
Thus, $|x|=|z|$, so $x\,R\,z$ holds.

4. Equivalence Classes:
The equivalence classes are the sets of strings with the same length.
For any non-negative integer $n$, the equivalence class of strings of length $n$ is:

Solution

1. Reflexive:
For any $a\in\mathbb{R}$, we have $a^2=a^2$, so $a\,R\,a$ holds.

2. Symmetric:
If $a\,R\,b$, then $a^2=b^2$.
Thus, $b^2=a^2$, so $b\,R\,a$ holds.

3. Transitive:
If $a\,R\,b$ and $b\,R\,c$, then $a^2=b^2$ and $b^2=c^2$.
Thus, $a^2=c^2$, so $a\,R\,c$ holds.

4. Equivalence Classes:
The equivalence classes are the sets of real numbers with the same absolute value.
For any non-negative real number $r$, the equivalence class of $r$ is:

Solution

1. Reflexive:
For any person $a$, the relation holds because $a$ has the same birth year as $a$.
Thus, $a\,R\,a$ holds.

2. Symmetric:
If $a\,R\,b$, then $a$ and $b$ have the same birth year.
Since having the same birth year is a mutual property, $b\,R\,a$ also holds.

3. Transitive:
If $a\,R\,b$ and $b\,R\,c$, then $a$ and $b$ have the same year, and $b$ and $c$ have the same year.
Thus, $a$ and $c$ must also have the same birth year, so $a\,R\,c$ holds.

4. Equivalence Classes:
The equivalence classes of $R$ are the sets of people born in the same year.
For any year $y$, the equivalence class of people born in year $y$ is:

Solution

1. Reflexive:
For any point $(x_1,y_1)$, we have $(x_1,y_1)\,R\,(x_1,y_1)$ since $x_1=x_1$ and $y_1=y_1$.
Thus, the relation is reflexive.

2. Symmetric:
If $(x_1,y_1)\,R\,(x_2,y_2)$, then either $x_1=x_2$ or $y_1=y_2$.
If $x_1=x_2$, then clearly $x_2=x_1$.
If $y_1=y_2$, then clearly $y_2=y_1$.
Thus, the relation is symmetric.

3. Not Transitive:
Consider $(1,1), (1,2), (2,2)$. $(1,1)R(1,2)$, $(1,2)R(2,2)$, but $(1,1)\bar{R}(2,2)$. Therefore, not transitive.

This is NOT an equivalence relation.

Solution

To find the units digit of $7^{100}$, observe the pattern of the units digits of powers of $7$:

The units digits repeat in a cycle of 4: $7,9,3,1$. To find the units digit of $7^{100}$, divide 100 by 4:

Since the remainder is 0, the units digit of $7^{100}$ corresponds to the units digit of $7^4$, which is 1.
Thus, the units digit of $7^{100}$ is $\boxed{1}$.

Solution

To find the units digit of $3^{50}$, observe the pattern of the units digits of powers of $3$:

The units digits repeat in a cycle of 4: $3,9,7,1$. To find the units digit of $3^{50}$, divide 50 by 4:

Since the remainder is 2, the units digit of $3^{50}$ corresponds to the units digit of $3^2$, which is 9.
Thus, the units digit of $3^{50}$ is $\boxed{9}$.

Solution

To find the units digit of $12^{1234}$, observe the pattern of the units digits of powers of $12$. The units digits of powers of $12$ follow the same pattern as powers of $2$:

The units digits repeat in a cycle of 4: $2,4,8,6$. To find the units digit of $12^{1234}$, divide 1234 by 4:

Since the remainder is 2, the units digit of $12^{1234}$ corresponds to the units digit of $12^2$, which is 4.
Thus, the units digit of $12^{1234}$ is $\boxed{4}$.

Solution

To find the units digit of $2^{987}$, observe the pattern of the units digits of powers of $2$:

The units digits repeat in a cycle of 4: $2,4,8,6$. To find the units digit of $2^{987}$, divide 987 by 4:

Since the remainder is 3, the units digit of $2^{987}$ corresponds to the units digit of $2^3$, which is 8.
Thus, the units digit of $2^{987}$ is $\boxed{8}$.

Solution

To find the units digit of $9^{999}$, observe the pattern of the units digits of powers of $9$:

The units digits repeat in a cycle of 2: $9,1$. To find the units digit of $9^{999}$, divide 999 by 2:

Since the remainder is 1, the units digit of $9^{999}$ corresponds to the units digit of $9^1$, which is 9.
Thus, the units digit of $9^{999}$ is $\boxed{9}$.