Proof by contradiction – Year 13 A level maths worksheet with answers to download as PDF

The first step in a proof by contradiction is to write down the opposite of the statement. Write the negation of each statement, in good English.

1. \(n\) is a multiple of 3. [1 mark]
2. There are infinitely many prime numbers. [1 mark]
3. For all real \(x\), \(x^2\ge0\). [2 marks]
4. \(\sqrt{x}\) is irrational. [1 mark]
5. There exist integers \(m\) and \(n\) such that \(6m+9n=1\). [2 marks]

Use proof by contradiction to prove each statement, where \(n\) is an integer.

1. If \(n^2\) is even, then \(n\) is even. [3 marks]
2. If \(n^2\) is divisible by 3, then \(n\) is divisible by 3. [4 marks]

You may assume that \(\sqrt2\) is irrational.

1. Prove by contradiction that if \(x\) is a non-zero rational number and \(y\) is irrational, then \(xy\) is irrational. [4 marks]
2. Hence prove that \(3\sqrt2\) is irrational. [1 mark]
3. Prove that \(1+\sqrt2\) is irrational. [3 marks]

Prove that \(\sqrt3\) is irrational by completing the following steps.

1. Assume \(\sqrt3=\dfrac ab\) in lowest terms and show that \(a^2=3b^2\). [2 marks]
2. Explain why \(a\) is divisible by 3. [2 marks]
3. Write \(a=3k\) and deduce that \(b\) is also divisible by 3. [2 marks]
4. State the contradiction and conclude. [2 marks]

Prove by contradiction that there are no integers \(m\) and \(n\) satisfying each equation.

1. \(6m+9n=1\) [3 marks]
2. \(10m+15n=3\) [3 marks]
3. \(x^2-4y=2\), where \(x\) and \(y\) are integers [4 marks]

A student writes the following "proof" that \(\sqrt2\) is irrational.

"Assume \(\sqrt2=\dfrac ab\). Then \(a^2=2b^2\), so \(a\) is even and \(a=2k\). Then \(4k^2=2b^2\) and \(b^2=2k^2\), so \(b\) is even. Therefore \(\sqrt2\) is irrational."

1. Identify two things the student has not stated. [2 marks]
2. Explain why, without the missing statement, there is no contradiction. [2 marks]
3. Rewrite the proof so that it would gain full marks. [4 marks]

A tiler cuts square floor tiles of side 1 unit and wants to measure the diagonal exactly as a fraction of the side, say \(\dfrac ab\) of a unit with \(a\) and \(b\) whole numbers of tiny marks on her ruler.

1. Show that the diagonal has length \(\sqrt2\) using Pythagoras. [1 mark]
2. Prove that no such fraction exists. [5 marks]
3. The tiler measures 1.414 and says the diagonal is \(\dfrac{1414}{1000}\) units. Explain why this must be an approximation. [2 marks]

A \(8\times8\) chessboard has two opposite corner squares removed. A student claims that the remaining 62 squares can be covered exactly by 31 dominoes, each covering two adjacent squares.

1. How many black and how many white squares remain? [2 marks]
2. Use proof by contradiction to show that the student is wrong. [4 marks]
3. Would the claim be true if two adjacent squares were removed instead? Justify your answer. [2 marks]

A new league has 7 teams. The organiser wants every team to play exactly 3 matches, each against a different opponent, and no pair of teams to meet twice.

1. Assume the schedule is possible. Show that the total number of matches would have to be \(\dfrac{7\times3}2\). [3 marks]
2. Explain why this is a contradiction. [2 marks]
3. For what values of \(n\) teams is it possible for every team to play exactly 3 matches against different opponents? [3 marks]

A4 paper is cut so that the longer side divided by the shorter side is \(\sqrt2\), which keeps the shape when it is folded in half. A printing company states that it measures every sheet in whole millimetres.

1. Prove that no sheet can have an exact ratio of \(\sqrt2\) with both sides a whole number of millimetres. [5 marks]
2. A4 is \(297\text{ mm}\times210\text{ mm}\). Find the ratio to 4 decimal places and compare with \(\sqrt2\). [2 marks]
3. Explain what this tells you about the real size of sheets. [1 mark]

At a school fair, prizes cost a number of points. Points are earned only from 6-point and 9-point tokens. A pupil has a bag of both types and wants a prize costing exactly 50 points.

1. Show that if the pupil uses \(a\) tokens of 6 points and \(b\) tokens of 9 points, the total is a multiple of 3. [2 marks]
2. Prove by contradiction that a 50-point prize cannot be bought exactly. [3 marks]
3. Which of the prizes costing 48, 51, 52 and 57 points can be bought exactly? [3 marks]

A gardener wants a rectangular allotment with integer side lengths \(a\) and \(b\) metres, using exactly 30 m of fencing, so the perimeter is 30 m. She also wants the area to be exactly 57 m\(^2\).

1. Show that \(a+b=15\). [1 mark]
2. Use proof by contradiction to show that the gardener’s wish is impossible, even without the integer condition. [5 marks]
3. What is the largest area she could enclose? [2 marks]

In music, an octave multiplies a frequency by 2 and a perfect fifth multiplies it by \(\dfrac32\). Pythagoras wondered whether going up 12 perfect fifths could return exactly to a note some whole number of octaves above the start.

1. Show that this would require \(3^{12}=2^{19}\). [3 marks]
2. Prove by contradiction that no whole number \(n\) and positive integer \(m\) satisfy \(3^m=2^n\). [3 marks]
3. Calculate \(3^{12}\) and \(2^{19}\) and find their ratio to 4 decimal places. [2 marks]

A security engineer assumes that a computer system only ever needs the first six primes, 2, 3, 5, 7, 11 and 13, because these are "all the primes".

1. Calculate \(N=2\times3\times5\times7\times11\times13+1\). [1 mark]
2. Show that \(N\) is not divisible by any of the six primes. [2 marks]
3. Factorise \(N\) and explain how this shows there are more primes than the engineer assumed. [3 marks]
4. Explain why this does not prove that \(N\) itself is prime. [2 marks]

Musicians approximate the number \(\log_23=1.58496\ldots\) by fractions \(\dfrac nm\), because \(3^m=2^n\) would make twelve fifths fit exactly in octaves. The table shows successive attempts.

1. Suppose \(\log_23=\dfrac pq\) with \(p,q\) positive integers. Show that \(3^q=2^p\). [2 marks]
2. Prove that this is impossible, and so that \(\log_23\) is irrational. [4 marks]
3. Verify the last row of the table. [2 marks]
4. Explain why the fractions in the table can never be exact, however large \(m\) is. [2 marks]
5. Which of the fractions \(\frac32\), \(\frac85\), \(\frac{19}{12}\) is the best approximation to \(\log_23\)? Justify. [2 marks]

You may use the fact that \(\sqrt2\) is irrational.

1. Prove that \(\sqrt3\) is irrational. [5 marks]
2. Assume that \(\sqrt2+\sqrt3=r\) where \(r\) is rational. Show that \(\sqrt2=\dfrac{r^2-1}{2r}\). [3 marks]
3. Hence prove that \(\sqrt2+\sqrt3\) is irrational. [2 marks]
4. Evaluate \(\sqrt2+\sqrt3\) to 4 decimal places and explain why this decimal cannot prove its irrationality. [2 marks]

\(\(f(x)=x^3+x+1.\)\)

1. Use the table to show that \(f(x)=0\) has a real root between \(-1\) and \(0\). [2 marks]
2. Assume that \(\dfrac pq\) is a rational root in lowest terms, with \(q>0\). Show that \(p^3+pq^2+q^3=0\). [2 marks]
3. By considering whether \(p\) and \(q\) are odd or even, obtain a contradiction. [5 marks]
4. Find the root to 3 decimal places and say what your answers show. [3 marks]

Euclid proved that there are infinitely many primes using the number \(N=p_1p_2\cdots p_k+1\). The table shows \(N\) for the first few primes.

1. Confirm the last row and explain why it does not disprove Euclid’s argument. [3 marks]
2. Prove by contradiction that there is no largest prime, by considering \(P!+1\) where \(P\) is the supposed largest prime. [5 marks]
3. Use your proof to explain why there is always a prime between \(P\) and \(P!+1\). [2 marks]
4. Show that \(5!+1=121\) is not prime and find its prime factorisation. [2 marks]

A farmer has 40 m of fencing and wants a rectangle of sides \(a\) and \(b\) metres to enclose the largest possible area. A sample of possible rectangles is shown.

1. Show that \(a+b=20\) and check that the areas in the table are correct. [2 marks]
2. Prove by contradiction that the area can never exceed 100 m\(^2\). [5 marks]
3. State when the area equals 100 m\(^2\). [1 mark]
4. Use the same method to prove that for positive \(a,b\): \(\dfrac{a+b}2\ge\sqrt{ab}\). [4 marks]

Let \(p\) be a prime number.

1. Prove that if \(p\mid n^2\) then \(p\mid n\). (Hint: use the fact that if a prime divides a product of two integers, it divides at least one of them.) [3 marks]
2. Prove that \(\sqrt p\) is irrational. [4 marks]
3. Prove that \(\sqrt6\) is irrational. [4 marks]
4. The proof for \(\sqrt p\) fails for \(\sqrt4\). Explain exactly which step fails. [2 marks]