Proof by Contradiction

Show your work for each problem.

1.
You want to prove by contradiction that $\sqrt{3}$ is irrational. What is the correct first line?
1. a)Assume $3$ is irrational
2. b)Assume $\sqrt{3}$ is rational
3. c)Assume $\sqrt{3} = 3$
4. d)Assume $\sqrt{3}$ is irrational
Answer: Assume $\sqrt{3}$ is rational
The statement is " $\sqrt{3}$ is irrational", so its negation is " $\sqrt{3}$ is rational". Assuming the statement itself would be circular.
2.
What is the smallest number of people you need so that at least two of them are guaranteed to be born in the same month?
Answer: 13
With 12 people, all months can be different. With 13, assuming all months are different would need 13 months, but there are only 12. So the answer is $13$ .
3.
Which statement is false for every truth value of $p$ , so that it is a contradiction?
1. a) $p \lor \neg p$
2. b) $p \land \neg p$
3. c) $p \Rightarrow p$
4. d) $\neg\neg p$
Answer: $p \land \neg p$
$p \land \neg p$ needs $p$ and its opposite to be true at the same time, which never happens, so it is F in every row. $p \lor \neg p$ and $p \Rightarrow p$ are always true, and $\neg\neg p$ has the same value as $p$ .
4.
Someone claims that $N = 100$ is the largest even number. Follow the proof to show the claim is false.
Answer: 102
1. Write $100 = 2k$ . What is $k$ ? 50
2. What is $N + 2$ ? 102
3. Write $N + 2 = 2(k + 1)$ . What is $k + 1$ ? 51
5.
In the proof that $\sqrt{2}$ is irrational, you square $\sqrt{2} = \frac{a}{b}$ and multiply by $b^2$ . You get $a^2 = k \cdot b^2$ . What is $k$ ?
Answer: 2
Squaring gives $2 = \frac{a^2}{b^2}$ , and multiplying by $b^2$ gives $a^2 = 2b^2$ , so $k = 2$ . This shows that $a^2$ is even.
6.
Show with the pigeonhole idea that in a group of 13 people, some birth month is shared.
Answer: 2
1. How many months (boxes) are there? 12
2. At most how many people can all have different birth months? 12
3. After one person is placed in each month, how many of the 13 people are left over? 1
4. So the most crowded month has at least how many people? 2
7.
What is the correct negation of "Every prime number is odd"?
1. a)Every prime number is even
2. b)Every odd number is prime
3. c)No prime number is odd
4. d)At least one prime number is not odd
Answer: At least one prime number is not odd
The negation of "every ... is odd" is "at least one ... is not odd". Here the negation is even true: $2$ is a prime number that is not odd.
8.
You want to prove $x > 5$ by contradiction. What do you assume?
1. a) $x \le 5$
2. b) $x \ge 5$
3. c) $x \neq 5$
4. d) $x < 5$
Answer: $x \le 5$
$x > 5$ is false exactly when $x < 5$ or $x = 5$ , that is $x \le 5$ . Assuming only $x < 5$ would leave the case $x = 5$ open.
9.
A box holds single gloves in 7 different colors. How many gloves must you take without looking to be sure that two have the same color?
Answer: 8
7 gloves can all have different colors. With 8, assuming all colors differ would need 8 colors, but there are only 7. So $8$ gloves guarantee a matching pair.
10.
Use a calculator to show that $\sqrt{2}$ lies strictly between $1.4142$ and $1.4143$ , so it equals neither of them.
Answer: 0
1. What is $1.4142^2$ ? 1.99996164
2. What is $1.4143^2$ ? 2.00024449
3. How many of these two squares are exactly equal to 2? 0
11.
Someone claims that $\frac{1}{1000}$ is the smallest positive rational number. Halve it as in the proof. Which smaller positive rational number do you get? Write it as a fraction.
Answer: 1/2000
$\frac{1}{1000} \div 2 = \frac{1}{2000}$ , which is positive, rational and smaller than $\frac{1}{1000}$ . So the claim is false, and the same trick works for any candidate.
12.
How many people guarantee that two of them have the same birthday (day and month), counting February 29 as a possible birthday?
Answer: 367
1. How many possible birthdays are there, including February 29? 366
2. What is the largest number of people who can all have different birthdays? 366
3. How many people guarantee a shared birthday? 367
13.
Run Euclid's proof with the list of primes $2, 3, 5$ : build $N = 2 \cdot 3 \cdot 5 + 1$ and check that no prime on the list divides it.
Answer: 31
1. What is $2 \cdot 3 \cdot 5$ ? 30
2. What is $N = 2 \cdot 3 \cdot 5 + 1$ ? 31
3. What is the remainder when you divide $31$ by $3$ ? 1
4. What is the remainder when you divide $31$ by $5$ ? 1
14.
In Euclid's proof, compute $N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1$ for the first five primes.
Answer: 2311
$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310$ , so $N = 2311$ . Dividing $2311$ by 2, 3, 5, 7 or 11 always leaves remainder 1, so its prime factors are not on the list (here $2311$ happens to be prime itself).
15.
With the primes $2, 3, 5, 7, 11, 13$ , Euclid's number is $N = 30031 = 59 \times 509$ , which is not prime. What does this mean for the proof?
1. a)The proof fails, because $N$ is not prime
2. b)There are only six primes
3. c) $N$ has prime factors that are not on the list, so the proof still works
4. d) $59$ is the largest prime
Answer: $N$ has prime factors that are not on the list, so the proof still works
The proof never claims that $N$ is prime. It only needs a prime factor of $N$ that is missing from the list, and $59$ and $509$ are exactly such primes. The proof still works.
16.
Follow the proof that $\sqrt{2}$ is irrational. Assume $\sqrt{2} = \frac{a}{b}$ in lowest terms and fill in the numbers.
Answer: 2
1. Squaring gives $a^2 = m \cdot b^2$ . What is $m$ ? 2
2. $a$ is even, so $a = 2k$ . Then $a^2 = m \cdot k^2$ . What is $m$ ? 4
3. From $4k^2 = 2b^2$ you get $b^2 = m \cdot k^2$ . What is $m$ ? 2
4. So $a$ and $b$ are both divisible by which number? 2
17.
Prove that $\sqrt{3}$ is irrational the same way. Assume $\sqrt{3} = \frac{a}{b}$ in lowest terms and fill in the numbers. Use the fact that if a prime divides $a^2$ , it divides $a$ .
Answer: 3
1. Squaring gives $a^2 = m \cdot b^2$ . What is $m$ ? 3
2. $3$ divides $a$ , so $a = 3k$ . Then $a^2 = m \cdot k^2$ . What is $m$ ? 9
3. From $9k^2 = 3b^2$ you get $b^2 = m \cdot k^2$ . What is $m$ ? 3
4. So $a$ and $b$ are both divisible by which prime? 3
18.
Run Euclid's proof with the primes $2, 3, 5, 7, 11, 13$ and find the prime factors of $N$ .
Answer: 509
1. What is $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ ? 30030
2. What is $N$ , the product plus 1? 30031
3. What is the remainder when you divide $N$ by $13$ ? 1
4. $N = 59 \times q$ . What is $q$ ? 509