4.2 Proofs

Investigate!

Decide which of the following are valid proofs of the following statement:

If $a b$ is an even number, then $a$ or $b$ is even.

Suppose $a$ and $b$ are odd. That is, $a = 2 k + 1$ and $b = 2 m + 1$ for some integers $k$ and $m$ . Then
$\begin{aligned} a b & = (2 k + 1) (2 m + 1) \\ = 4 k m + 2 k + 2 m + 1 \\ = 2 (2 k m + k + m) + 1 \end{aligned}$
.
Therefore $a b$ is odd.
Assume that $a$ or $b$ is even - say it is $a$ (the case where $b$ is even will be identical). That is, $a equals 2 k$ for some integer $k$ . Then
$\begin{aligned} a b & = (2 k) b \\ = 2 (k b) \end{aligned}$
.
Thus $a b$ is even.
Suppose that $a b$ is even but $a$ and $b$ are both odd. Namely, $a b equals 2 n$ , $a = 2 k + 1$ and $b = 2 j + 1$ for some integers $n$ , $k$ , and $j$ . Then
$\begin{aligned} 2 n & = (2 k + 1) (2 j + 1) \\ 2 n & = 4 k j + 2 k + 2 j + 1 \\ n & = 2 k j + k + j + \frac{1}{2} \end{aligned}$
.
But since $2 k j + k + j$ is an integer, this says that the integer $n$ is equal to a non-integer, which is impossible.
Let $a b$ be an even number, say $a b equals 2 n$ , and $a$ be an odd number, say $a = 2 k + 1$ .
$\begin{aligned} a b & = (2 k + 1) b \\ 2 n & = 2 k b + b \\ 2 n - 2 k b & = b \\ 2 (n - k b) & = b \end{aligned}$
.
Therefore $b$ must be even.

Anyone who doesn't believe there is creativity in mathematics clearly has not tried to write proofs. Finding a way to convince the world that a particular statement is necessarily true is a mighty undertaking and can often be quite challenging. There is not a guaranteed path to success in the search for proofs. For example, in the summer of 1742, a German mathematician by the name of Christian Goldbach wondered whether every even integer greater than 2 could be written as the sum of two primes. Centuries later, we still don't have a proof of this apparent fact (computers have checked that “Goldbach's Conjecture” holds for all numbers less than $4 \times 10^{18}$ , which leaves only infinitely many more numbers to check).

Writing proofs is a bit of an art. Like any art, to be truly great at it, you need some sort of inspiration, as well as some foundational technique. Just as musicians can learn proper fingering, and painters can learn the proper way to hold a brush, we can look at the proper way to construct arguments. A good place to start might be to study a classic.

Proof

Suppose this were not the case. That is, suppose there are only finitely many primes. Then there must be a last, largest prime, call it $p$ . Consider the number

$N = p! + 1 = (p \cdot (p - 1) \cdot \dots 3 \cdot 2 \cdot 1) + 1$

Now $N$ is certainly larger than $p$ . Also, $N$ is not divisible by any number less than or equal to $p$ , since every number less than or equal to $p$ divides $p!$ . Thus the prime factorization of $N$ contains prime numbers (possibly just $N$ itself) all greater than $p$ . So $p$ is not the largest prime, a contradiction. Therefore there are infinitely many primes.

This proof is an example of a proof by contradiction, one of the standard styles of mathematical proof. First and foremost, the proof is an argument. It contains sequence of statements, the last being the conclusion which follows from the previous statements. The argument is valid so the conclusion must be true if the premises are true. Let's go through the proof line by line.

Suppose there are only finitely many primes. [this is a premise. Note the use of “suppose.”]
There must be a largest prime, call it $p$ . [follows from line 1, by the definition of “finitely many.”]
Let $N = p! + 1$ . [basically just notation, although this is the inspired part of the proof; looking at $p ! plus 1$ is the key insight.]
$N$ is larger than $p$ . [by the definition of $p!$ ]
$N$ is not divisible by any number less than or equal to $p$ . [by definition, $p!$ is divisible by each number less than or equal to $p$ , so $p ! plus 1$ is not.]
The prime factorization of $N$ contains prime numbers greater than $p$ . [since $N$ is divisible by each prime number in the prime factorization of $N$ , and by line 5.]
Therefore $p$ is not the largest prime. [by line 6, $N$ is divisible by a prime larger than $p$ .]
This is a contradiction. [from line 2 and line 7: the largest prime is $p$ and there is a prime larger than $p$ .]
Therefore there are infinitely many primes. [from line 1 and line 8: our only premise lead to a contradiction, so the premise is false.]

We should say a bit more about the last line. Up through line 8, we have a valid argument with the premise “there are only finitely many primes” and the conclusion “there is a prime larger than the largest prime.” This is a valid argument as each line follows from previous lines. So if the premises are true, then the conclusion must be true. However, the conclusion is NOT true. The only way out: the premise must be false.

The sort of line-by-line analysis we did above is a great way to really understand what is going on. Whenever you come across a proof in a textbook, you really should make sure you understand what each line is saying and why it is true. Additionally, it is equally important to understand the overall structure of the proof. This is where using tools from logic is helpful. Luckily there are a relatively small number of standard proof styles that keep showing up again and again. Being familiar with these can help understand proof, as well as give ideas of how to write your own.

Direct Proof

The simplest (from a logic perspective) style of proof is a direct proof. Often all that is required to prove something is a systematic explanation of what everything means. Direct proofs are especially useful when proving implications. The general format to prove $P \to Q$ is this:

Assume $P$ . Explain, explain, …, explain. Therefore $Q$ .

Often we want to prove universal statements, perhaps of the form $∀ x open parenthesis P open parenthesis x close parenthesis → Q open parenthesis x close parenthesis close parenthesis$ . Again, we will want to assume $P (x)$ is true and deduce $Q (x)$ . But what about the $x$ ? We want this to work for all $x$ . We accomplish this by fixing $x$ to be an arbitrary element (of the sort we are interested in).

Here are a few examples. First, we will set up the proof structure for a direct proof, then fill in the details.

Example 1

Prove: For all integers $n$ , if $n$ is even, then $n^{2}$ is even.

The format of the proof will be this: Let $n$ be an arbitrary integer. Assume that $n$ is even. Explain explain explain. Therefore $n^{2}$ is even.

To fill in the details, we will basically just explain what it means for $n$ to be even, and then see what that means for $n^{2}$ . Here is a complete proof.

Example 2

Prove: For all integers $a$ , $b$ , and $c$ , if $a | b$ and $b | c$ then $a | c$ . (Here $x | y$ , read “ $x$ divides $y$ ” means that $y$ is a multiple of $x$ , i.e., that $x$ will divide into $y$ without remainder).

Even before we know what the divides symbol means, we can set up a direct proof for this statement. It will go something like this: Let $a$ , $b$ , and $c$ be arbitrary integers. Assume that $a | b$ and $b | c$ . Dot dot dot. Therefore $a | c$ .

How do we connect the dots? We say what our hypothesis ( $a | b$ and $b | c$ ) really means and why this gives us what the conclusion ( $a | c$ ) really means. Another way to say that $a | b$ is to say that $b = k a$ for some integer $k$ (that is, that $b$ is a multiple of $a$ ). What are we going for? That $c = l a$ , for some integer $l$ (because we want $c$ to be a multiple of $a$ ). Here is the complete proof.

Proof by Contrapositive

Recall that an implication $P \to Q$ is logically equivalent to its contrapositive $\neg Q \to \neg P$ . There are plenty of examples of statements which are hard to prove directly, but whose contrapositive can easily be proved directly. This is all that proof by contrapositive does. It gives a direct proof of the contrapositive of the implication. This is enough because the contrapositive is logically equivalent to the original implication.

The skeleton of the proof of $P \to Q$ by contrapositive will always look roughly like this:

Assume $\neg Q$ . Explain, explain, … explain. Therefore $\neg P$ .

As before, if there are variables and quantifiers, we set them to be arbitrary elements of our domain. Here are two examples:

Example 3

Is the statement “for all integers $n$ , if $n^{2}$ is even, then $n$ is even” true?

This is the converse of the statement we proved above using a direct proof. From trying a few examples, this statement definitely appears to be true. So let's prove it.

A direct proof of this statement would require fixing an arbitrary $n$ and assuming that $n^{2}$ is even. But it is not at all clear how this would allow us to conclude anything about $n$ . Just because $n squared equals 2 k$ does not in itself suggest how we could write $n$ as a multiple of 2.

Try something else: write the contrapositive of the statement. We get, for all integers $n$ , if $n$ is odd then $n^{2}$ is odd. This looks much more promising. Our proof will look something like this:

Let $n$ be an arbitrary integer. Suppose that $n$ is not even. This means that …. In other words …. But this is the same as saying …. Therefore $n^{2}$ is not even.

Now we fill in the details:

Example 4

Prove: for all integers $a$ and $b$ , if $a + b$ is odd, then $a$ is odd or $b$ is odd.

The problem with trying a direct proof is that it will be hard to separate $a$ and $b$ from knowing something about $a + b$ . On the other hand, if we know something about $a$ and $b$ separately, then combining them might give us information about $a + b$ . The contrapositive of the statement we are trying to prove is: for all integers $a$ and $b$ , if $a$ and $b$ are even, then $a + b$ is even. Thus our proof will have the following format:

Let $a$ and $b$ be integers. Assume that $a$ and $b$ are both even. la la la. Therefore $a + b$ is even.

Here is a complete proof:

Note that our assumption that $a$ and $b$ are even is really the negation of $a$ or $b$ is odd. We used De Morgan's law here.

We have seen how to prove some statements in the form of implications: either directly or by contrapositive. Some statements are not written as implications to begin with.

Proof by Contradiction

There might be statements which really cannot be rephrased as implications. For example, “ $the square root of 2$ is irrational.” In this case, it is hard to know where to start. What can we assume? Well, say we want to prove the statement $P$ . What if we could prove that $\neg P \to Q$ where $Q$ was false? If this implication is true, and $Q$ is false, what can we say about $\neg P$ ? It must be false as well, which makes $P$ true!

This is why proof by contradiction works. If we can prove that $\neg P$ leads to a contradiction, then the only conclusion is that $\neg P$ is false, so $P$ is true. That's what we wanted to prove. In other words, if it is impossible for $P$ to be false, $P$ must be true.

Here are three examples of proofs by contradiction:

Example 6

Prove that $the square root of 2$ is irrational.

Proof

Suppose not. Then $the square root of 2$ is equal to a fraction $\frac{a}{b}$ . Without loss of generality, assume $\frac{a}{b}$ is in lowest terms (otherwise reduce the fraction). So,

$2 = \frac{a^{2}}{b^{2}}$

$2 b squared equals a squared$

Thus $a^{2}$ is even, and as such $a$ is even. So $a equals 2 k$ for some integer $k$ , and $a squared equals 4 k squared$ . We then have,

$2 b squared equals 4 k squared$

$b squared equals 2 k squared$

Thus $b^{2}$ is even, and as such $b$ is even. Since $a$ is also even, we see that $\frac{a}{b}$ is not in lowest terms, a contradiction. Thus $the square root of 2$ is irrational.

Example 7

Prove: There are no integers $x$ and $y$ such that $x^{2} = 4 y + 2$ .

Proof

We proceed by contradiction. So suppose there are integers $x$ and $y$ such that $x^{2} = 4 y + 2 = 2 (2 y + 1)$ . So $x^{2}$ is even. We have seen that this implies that $x$ is even. So $x equals 2 k$ for some integer $k$ . Then $x squared equals 4 k squared$ . This in turn gives $2 k^{2} = (2 y + 1)$ . But $2 k squared$ is even, and $2 y plus 1$ is odd, so these cannot be equal. Thus we have a contradiction, so there must not be any integers $x$ and $y$ such that $x^{2} = 4 y + 2$ .

Example 8

The Pigeonhole Principle: If more than $n$ pigeons fly into $n$ pigeon holes, then at least one pigeon hole will contain at least two pigeons. Prove this!

While we phrased this proof as a proof by contradiction, we could have also used a proof by contrapositive since our contradiction was simply the negation of the hypothesis. Sometimes this will happen, in which case you can use either style of proof. There are examples however where the contradiction occurs “far away” from the original statement.

Proof by (counter) Example

It is almost NEVER okay to prove a statement with just an example. Certainly none of the statements proved above can be proved through an example. This is because in each of those cases we are trying to prove that something holds of all integers. We claim that $n^{2}$ being even implies that $n$ is even, no matter what integer $n$ we pick. Showing that this works for $n equals 4$ is not even close to enough.

This cannot be stressed enough. If you are trying to prove a statement of the form $∀ x P open parenthesis x close parenthesis$ , you absolutely CANNOT prove this with an example.¹

However, existential statements can be proven this way. If we want to prove that there is an integer $n$ such that $n^{2} - n + 41$ is not prime, all we need to do is find one. This might seem like a silly thing to want to prove until you try a few values for $n$ .

$n$	1	2	3	4	5	6	7
$n^{2} - n + 41$	41	43	47	53	61	71	83

So far we have gotten only primes. You might be tempted to conjecture, “For all positive integers $n$ , the number $n^{2} - n + 41$ is prime.” If you wanted to prove this, you would need to use a direct proof, a proof by contrapositive, or another style of proof, but certainly it is not enough to give even 7 examples. In fact, we can prove this conjecture is false by proving its negation: “There is a positive integer $n$ such that $n^{2} - n + 41$ is not prime.” Since this is an existential statement, it suffices to show that there does indeed exist such a number.

In fact, we can quickly see that $n equals 41$ will give $41 squared$ which is certainly not prime. You might say that this is a counterexample to the conjecture that $n^{2} - n + 41$ is always prime. Since so many statements in mathematics are universal, making their negations existential, we can often prove that a statement is false (if it is) by providing a counterexample.

Example 9

Above we proved, “for all integers $a$ and $b$ , if $a + b$ is odd, then $a$ is odd or $b$ is odd.” Is the converse true?

The converse is the statement, “for all integers $a$ and $b$ , if $a$ is odd or $b$ is odd, then $a + b$ is odd.” This is false! How do we prove it is false? We need to prove the negation of the converse. Let's look at the symbols. The converse is

$∀ a ∀ b open parenthesis open parenthesis O open parenthesis a close parenthesis ∨ O open parenthesis b close parenthesis close parenthesis → O open parenthesis a plus b close parenthesis close parenthesis$

We want to prove the negation:

$¬ ∀ a ∀ b open parenthesis open parenthesis O open parenthesis a close parenthesis ∨ O open parenthesis b close parenthesis close parenthesis → O open parenthesis a plus b close parenthesis close parenthesis$

Simplify using the rules from the previous sections:

$∃ a ∃ b open parenthesis open parenthesis O open parenthesis a close parenthesis ∨ O open parenthesis b close parenthesis close parenthesis ∧ ¬ O open parenthesis a plus b close parenthesis close parenthesis$

As the negation passed by the quantifiers, they changed from $∀$ to $∃$ . We then needed to take the negation of an implication, which is equivalent to asserting the if part and not the then part.

Now we know what to do. To prove that the converse is false we need to find two integers $a$ and $b$ so that $a$ is odd or $b$ is odd, but $a + b$ is not odd (so even). That's easy: 1 and 3. (remember, “or” means one or the other or both). Both of these are odd, but $1 + 3 = 4$ is not odd.

Proof by Cases

We could go on and on and on about different proof styles (we haven't even mentioned induction or combinatorial proofs here), but instead we will end with one final useful technique: proof by cases. The idea is to prove that $P$ is true by proving that $Q \to P$ and $\neg Q \to P$ for some statement $Q$ . So no matter what, whether or not $Q$ is true, we know that $P$ is true. In fact, we could generalize this. Suppose we want to prove $P$ . We know that at least one of the statements $Q sub 1, Q sub 2, and so on, Q sub n$ is true. If we can show that $Q sub 1 → P$ and $Q sub 2 → P$ and so on all the way to $Q_{n} \to P$ , then we can conclude $P$ . The key thing is that we want to be sure that one of our cases (the $Q_{i}$ 's) must be true no matter what.

If that last paragraph was confusing, perhaps an example will make things better.

Example 10

Prove: For any integer $n$ , the number $(n^{3} - n)$ is even.

It is hard to know where to start this, because we don't know much of anything about $n$ . We might be able to prove that $n^{3} - n$ is even if we knew that $n$ was even. In fact, we could probably prove that $n^{3} - n$ was even if $n$ was odd. But since $n$ must either be even or odd, this will be enough. Here's the proof.

Proof

We consider two cases: if $n$ is even or if $n$ is odd.

Case 1: $n$ is even. Then $n equals 2 k$ for some integer $k$ . This give

$\begin{aligned} n^{3} - n & = 8 k^{3} - 2 k \\ = 2 (4 k^{2} - k) \end{aligned}$

, and since $4 k squared minus k$ is an integer, this says that $n^{3} - n$ is even.

Case 2: $n$ is odd. Then $n = 2 k + 1$ for some integer $k$ . This gives

$\begin{aligned} n^{3} - n & = (2 k + 1)^{3} - (2 k + 1) \\ = 8 k^{3} + 12 k^{2} + 6 k + 1 - 2 k - 1 \\ = 2 (4 k^{3} + 6 k^{2} + 2 k) \end{aligned}$

, and since $4 k^{3} + 6 k^{2} + 2 k$ is an integer, we see that $n^{3} - n$ is even again.

Since $n^{3} - n$ is even in both exhaustive cases, we see that $n^{3} - n$ is indeed always even.

Consider the statement “for all integers $a$ and $b$ , if $a + b$ is even, then $a$ and $b$ are even”

Write the contrapositive of the statement.
Write the converse of the statement.
Write the negation of the statement.
Is the original statement true or false? Prove your answer.
Is the contrapositive of the original statement true or false? Prove your answer.
Is the converse of the original statement true or false? Prove your answer.
Is the negation of the original statement true or false? Prove your answer.

For all integers $a$ and $b$ , if $a$ or $b$ is not even, then $a + b$ is not even.
For all integers $a$ and $b$ , if $a$ and $b$ are even, then $a + b$ is even.
There are numbers $a$ and $b$ such that $a + b$ is even but $a$ and $b$ are not both even.
False. For example, $a equals 3$ and $b equals 5$ . $a + b = 8$ , but neither $a$ nor $b$ are even.
False, since it is equivalent to the original statement.
True. Let $a$ and $b$ be integers. Assume both are even. Then $a equals 2 k$ and $b equals 2 j$ for some integers $k$ and $j$ . But then $a + b = 2 k + 2 j = 2 (k + j)$ which is even.
True, since the statement is false.

For each of the statements below, say what method of proof you should use to prove them. Then say how the proof starts and how it ends. Bonus points for filling in the middle.

There are no integers $x$ and $y$ such that $x$ is a prime greater than 5 and $x = 6 y + 3$ .
For all integers $n$ , if $n$ is a multiple of 3, then $n$ can be written as the sum of consecutive integers.
For all integers $a$ and $b$ , if $a^{2} + b^{2}$ is odd, then $a$ or $b$ is odd.

Proof by contradiction. Start of proof: Assume, for the sake of contradiction, that there are integers $x$ and $y$ such that $x$ is a prime greater than 5 and $x = 6 y + 3$ . End of proof: … this is a contradiction, so there are no such integers.
Direct proof. Start of proof: Let $n$ be an integer. Assume $n$ is a multiple of 3. End of proof: Therefore $n$ can be written as the sum of consecutive integers.
Proof by contrapositive. Start of proof: Let $a$ and $b$ be integers. Assume that $a$ and $b$ are even. End of proof: Therefore $a^{2} + b^{2}$ is even.

Consider the statement: for all integers $n$ , if $n$ is even then $8 n$ is even.

Prove the statement. What sort of proof are you using?
Is the converse true? Prove or disprove.

Direct proof.
Proof
Let $n$ be an integer. Assume $n$ is even. Then $n equals 2 k$ for some integer $k$ . Thus $8 n = 16 k = 2 (8 k)$ . Therefore $8 n$ is even.
The converse is false. That is, there is an integer $n$ such that $8 n$ is even but $n$ is odd. For example, consider $n equals 3$ . Then $8 n equals 24$ which is even but $n equals 3$ is odd.

The game TENZI comes with 40 six-sided dice (each numbered 1 to 6). Suppose you roll all 40 dice.

Prove that there will be at least seven dice that land on the same number.
How many dice would you have to roll before you were guaranteed that some four of them would all match or all be different? Prove your answer.

This is an example of the pigeonhole principle. We can prove it by contrapositive.
Proof
Suppose that each number only came up 6 or fewer times. So there are at most six 1's, six 2's, and so on. That's a total of 36 dice, so you must not have rolled all 40 dice.
We can have 9 dice without any four matching or any four being all different: three 1's, three 2's, three 3's. We will prove that whenever you roll 10 dice, you will always get four matching or all being different.
Proof
Suppose you roll 10 dice, but that there are NOT four matching rolls. This means at most, there are three of any given value. If we only had three different values, that would be only 9 dice, so there must be 4 different values, giving 4 dice that are all different.

Prove that for all integers $n$ , it is the case that $n$ is even if and only if $3 n$ is even. That is, prove both implications: if $n$ is even, then $3 n$ is even, and if $3 n$ is even, then $n$ is even.

One of the implications will be a direct proof, the other will be a proof by contrapositive.

Prove that $the square root of 3$ is irrational.

This is really an exercise in modifying the proof that $the square root of 2$ is irrational. There you proved things were even; here they will be multiples of 3.

Consider the statement: for all integers $a$ and $b$ , if $a$ is even and $b$ is a multiple of 3, then $a b$ is a multiple of 6.

Prove the statement. What sort of proof are you using?
State the converse. Is it true? Prove or disprove.

Part (a) should be a relatively easy direct proof. Look for a counterexample for part (b).

Prove the statement: For all integers $n$ , if $5 n$ is odd, then $n$ is odd. Clearly state the style of proof you are using.

Prove the statement: For all integers $a$ , $b$ , and $c$ , if $a^{2} + b^{2} = c^{2}$ , then $a$ or $b$ is even.

A proof by contradiction would be reasonable here, because then you get to assume that both $a$ and $b$ are odd. Deduce that $c^{2}$ is even, and therefore a multiple of 4 (why? and why is that a contradiction?).

Suppose that you would like to prove the following implication:

For all numbers $n$ , if $n$ is prime then $n$ is solitary.

Write out the beginning and end of the argument if you were to prove the statement,

Directly
By contrapositive
By contradiction

You do not need to provide details for the proofs (since you do not know what solitary means). However, make sure that you provide the first few and last few lines of the proofs so that we can see that logical structure you would follow.

Suppose you have a collection of 5-cent stamps and 8-cent stamps. We saw earlier that it is possible to make any amount of postage greater than 27 cents using combinations of both these types of stamps. But, let's ask some other questions:

Prove that if you only use an even number of both types of stamps, the amount of postage you make must be even.
Suppose you made an even amount of postage. Prove that you used an even number of at least one of the types of stamps.
Suppose you made exactly 72 cents of postage. Prove that you used at least 6 of one type of stamp.

Use a different style of proof for each part. The last part should remind you of the pigeonhole principle, so mimicking that proof might be helpful.

Prove: $x = y$ if and only if $x y = \frac{(x + y)^{2}}{4}$ . Note, you will need to prove two “directions” here: the “if” and the “only if” part.

Prove that $log ⁡ open parenthesis 7 close parenthesis$ is irrational.

Note that if $\log (7) = \frac{a}{b}$ , then $7 = 10^{\frac{a}{b}}$ . Can any power of 7 be the same as a power of 10?

Prove that there are no integer solutions to the equation $x^{2} = 4 y + 3$ .

What if there were? Deduce that $x$ must be odd, and continue towards a contradiction.

Prove that every prime number greater than 3 is either one more or one less than a multiple of 6.

Prove the contrapositive by cases. There will be 4 cases to consider.

Your “friend” has shown you a “proof” he wrote to show that $1 equals 3$ . Here is the proof:

What is going on here? Is your friend's argument valid? Is the argument a proof of the claim $1 equals 3$ ? Carefully explain using what we know about logic.

Your friend's proof a proof, but of what? What implication follows from the given proof? Is that helpful?

A standard deck of 52 cards consists of 4 suites (hearts, diamonds, spades and clubs) each containing 13 different values (Ace, 2, 3, …, 10, J, Q, K). If you draw some number of cards at random you might or might not have a pair (two cards with the same value) or three cards all of the same suit. However, if you draw enough cards, you will be guaranteed to have these. For each of the following, find the smallest number of cards you would need to draw to be guaranteed having the specified cards. Prove your answers.

Three of a kind (for example, three 7's).
A flush of five cards (for example, five hearts).
Three cards that are either all the same suit or all different suits.

Suppose you are at a party with 19 of your closest friends (so including you, there are 20 people there). Explain why there must be least two people at the party who are friends with the same number of people at the party. Assume friendship is always reciprocated.

Consider the set of numbers of friends that everyone has. If everyone had a different number of friends, this set must contain 20 elements. Is that possible? Why not?

Your friend has given you his list of 115 best Doctor Who episodes (in order of greatness). It turns out that you have seen 60 of them. Prove that there are at least two episodes you have seen that are exactly four episodes apart on your friend's list.

This feels like the pigeonhole principle, although a bit more complicated. At least, you could try to replicate the style of proof used by the pigeonhole principle. How would the episodes need to be spaced out so that no two of your sixty were exactly 4 apart?

Suppose you have an $n \times n$ chessboard but your dog has eaten one of the corner squares. Can you still cover the remaining squares with dominoes? What needs to be true about $n$ ? Give necessary and sufficient conditions (that is, say exactly which values of $n$ work and which do not work). Prove your answers.

An 8 by 8 chessboard with the top-right corner square removed. Every other square is shaded darker (checkerboard pattern).

What if your $n \times n$ chessboard is missing two opposite corners? Prove that no matter what $n$ is, you will not be able to cover the remaining squares with dominoes.

An 8 by 8 chessboard with the top-right and bottom-left corner squares removed. Every other square is shaded darker (checkerboard pattern).

Discrete Mathematics: An Open Introduction, 3rd edition, by Oscar Levin (discrete.openmathbooks.org), licensed under CC BY-SA 4.0; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.