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

← Back to the worksheet

1. Answer to Question 1

   1. The negation is "\(n\) is not a multiple of 3" (it leaves remainder 1 or 2 when divided by 3).
   2. "There are only finitely many prime numbers".
   3. "There exists a real number \(x\) such that \(x^2<0\)". The word "for all" becomes "there exists", and the inequality is reversed.
   4. "\(\sqrt{x}\) is rational", that is, it can be written as \(\dfrac ab\) with \(a\) and \(b\) integers and \(b\ne0\).
   5. "There are no integers \(m\) and \(n\) such that \(6m+9n=1\)", or equivalently "for all integers \(m\) and \(n\), \(6m+9n\ne1\)".

2. Answer to Question 2

   1. Assume \(n^2\) is even but \(n\) is odd. Then \(n=2k+1\) for an integer \(k\), and \(n^2=4k^2+4k+1=2(2k^2+2k)+1\), which is odd. This contradicts \(n^2\) being even. So \(n\) is even. \(\blacksquare\)
   2. Assume \(3\mid n^2\) but \(3\nmid n\). Then \(n=3k+1\) or \(n=3k+2\). If \(n=3k+1\): \(n^2=9k^2+6k+1=3(3k^2+2k)+1\), remainder 1. If \(n=3k+2\): \(n^2=9k^2+12k+4=3(3k^2+4k+1)+1\), remainder 1. In both cases \(n^2\) is not divisible by 3, a contradiction. So \(3\mid n\). \(\blacksquare\)

3. Answer to Question 3

   1. Assume \(xy\) is rational, \(xy=\dfrac pq\), and \(x=\dfrac rs\) with \(r\ne0\) (all integers, \(q,s\ne0\)). Then \(y=\dfrac{xy}x=\dfrac{p/q}{r/s}=\dfrac{ps}{qr}\), a ratio of integers with \(qr\ne0\), so \(y\) is rational. This contradicts \(y\) being irrational. So \(xy\) is irrational. \(\blacksquare\)
   2. Take \(x=3\) (rational and non-zero) and \(y=\sqrt2\) (irrational). By part (a), \(3\sqrt2\) is irrational.
   3. Assume \(1+\sqrt2=\dfrac ab\) with integers \(a,b\), \(b\ne0\). Then \(\sqrt2=\dfrac ab-1=\dfrac{a-b}b\), a ratio of integers, so \(\sqrt2\) is rational. This contradicts the fact that \(\sqrt2\) is irrational. So \(1+\sqrt2\) is irrational. \(\blacksquare\)

4. Answer to Question 4

   1. Squaring \(\sqrt3=\dfrac ab\) gives \(3=\dfrac{a^2}{b^2}\), so \(a^2=3b^2\).
   2. \(a^2=3b^2\) is a multiple of 3. By the result in the previous question, if \(3\mid a^2\) then \(3\mid a\). So \(a\) is divisible by 3.
   3. \(a=3k\) gives \(9k^2=3b^2\), so \(b^2=3k^2\), a multiple of 3. So \(3\mid b\) by the same result.
   4. Both \(a\) and \(b\) are divisible by 3, so \(\dfrac ab\) was not in lowest terms. This contradicts the assumption. Hence \(\sqrt3\) is irrational. \(\blacksquare\)

5. Answer to Question 5

   1. Assume integers exist. Then \(3(2m+3n)=1\), so \(2m+3n=\dfrac13\). But \(2m+3n\) is an integer, and \(\dfrac13\) is not. Contradiction. \(\blacksquare\)
   2. Assume integers exist. Then \(5(2m+3n)=3\), so \(2m+3n=\dfrac35\), not an integer. Contradiction. \(\blacksquare\)
   3. Assume integers exist, so \(x^2=4y+2\). If \(x\) is even, \(x=2k\) and \(x^2=4k^2\), a multiple of 4, but \(4y+2\) leaves remainder 2 on division by 4. If \(x\) is odd, \(x=2k+1\) and \(x^2=4k^2+4k+1\) leaves remainder 1. Neither case gives remainder 2. Contradiction. \(\blacksquare\)

6. Answer to Question 6

   1. The student did not say that \(\dfrac ab\) is in its lowest terms (no common factor), and did not state the contradiction or the conclusion that the assumption is false.
   2. It is quite possible for a fraction such as \(\dfrac{6}{4}\) to have both numerator and denominator even. Without the requirement of lowest terms, "\(a\) and \(b\) are both even" does not contradict anything.
   3. Assume, for contradiction, that \(\sqrt2=\dfrac ab\) where \(a,b\) are integers with no common factor and \(b\ne0\). Squaring, \(a^2=2b^2\), so \(a^2\) is even and hence \(a\) is even. Write \(a=2k\). Then \(4k^2=2b^2\), so \(b^2=2k^2\) and \(b\) is even. So \(a\) and \(b\) have a common factor 2, contradicting the assumption that \(\dfrac ab\) is in lowest terms. Therefore \(\sqrt2\) is irrational. \(\blacksquare\)

7. Answer to Question 7

   1. The diagonal \(d\) satisfies \(d^2=1^2+1^2=2\), so \(d=\sqrt2\).
   2. Assume \(\sqrt2=\dfrac ab\) in lowest terms. Then \(a^2=2b^2\), so \(a^2\) is even and \(a\) is even, \(a=2k\). Then \(4k^2=2b^2\) and \(b^2=2k^2\), so \(b\) is even. Both even contradicts lowest terms. So no fraction equals \(\sqrt2\). \(\blacksquare\)
   3. \(\left(\dfrac{1414}{1000}\right)^2=1.999396\ne2\). Since \(\sqrt2\) is irrational, no fraction (and no terminating decimal) is exactly equal to it.

8. Answer to Question 8

   1. Opposite corners have the same colour (say white). The board has 32 white and 32 black squares, so after removal there are 30 white and 32 black squares.
   2. Assume a covering exists. Each domino covers two adjacent squares, which always have different colours, so each domino covers exactly one black and one white square. So 31 dominoes cover 31 black and 31 white squares. But there are 32 black and 30 white squares. Contradiction, so no covering exists. \(\blacksquare\)
   3. Adjacent squares have different colours, so removing them leaves 31 white and 31 black squares, and the colour argument gives no contradiction. In fact a covering exists (for example rows of dominoes).

9. Answer to Question 9

   1. Each of 7 teams plays 3 matches, giving \(7\times3=21\) team-appearances. Each match involves exactly 2 teams, so the number of matches is \(\dfrac{21}2=10.5\).
   2. The number of matches must be a whole number, but 10.5 is not. This is a contradiction, so the schedule is impossible. \(\blacksquare\)
   3. The total \(\dfrac{3n}2\) must be an integer, so \(n\) must be even. It is also necessary that \(n\ge4\) (a team needs 3 different opponents). So any even \(n\ge4\) can work (for example \(n=4\): each team plays the other three).

10. Answer to Question 10

    1. Assume the sides are \(L\) mm and \(W\) mm, integers, with \(\dfrac LW=\sqrt2\). Then \(\sqrt2\) is rational. But \(\sqrt2\) is irrational (proved by contradiction). This is a contradiction. \(\blacksquare\)
    2. \(\dfrac{297}{210}=1.4143\). \(\sqrt2=1.4142\). They differ by about \(1.0\times10^{-4}\), so the ratio is an approximation.
    3. Real sheets are rounded to the nearest millimetre, so the sizes are not exactly in the ratio \(\sqrt2:1\).

11. Answer to Question 11

    1. Total \(=6a+9b=3(2a+3b)\), a multiple of 3 because \(2a+3b\) is an integer.
    2. Assume \(6a+9b=50\). Then \(3(2a+3b)=50\), so \(50\) would be a multiple of 3. But \(50=3\times16+2\). Contradiction. \(\blacksquare\)
    3. A prize must be a multiple of 3: 48 yes (\(6\times8\)), 51 yes (\(6\times7+9\)), 52 no (not a multiple of 3), 57 yes (\(9\times3+6\times5\)).

12. Answer to Question 12

    1. Perimeter \(=2(a+b)=30\), so \(a+b=15\).
    2. Assume such a rectangle exists. Then \(b=15-a\) and \(a(15-a)=57\), so \(a^2-15a+57=0\). The discriminant is \(225-228=-3<0\), so there is no real solution for \(a\). Contradiction. \(\blacksquare\)
    3. Area \(=a(15-a)=-(a-7.5)^2+56.25\), which has maximum \(56.25\) m\(^2\) at \(a=7.5\). Since \(57>56.25\) the wish was impossible. With integer sides the maximum is \(7\times8=56\) m\(^2\).

13. Answer to Question 13

    1. Twelve fifths multiply the frequency by \(\left(\dfrac32\right)^{12}=\dfrac{3^{12}}{2^{12}}\). Seven octaves multiply it by \(2^7\). Equal means \(3^{12}=2^{12}\times2^7=2^{19}\).
    2. Assume \(3^m=2^n\) with \(m\ge1\). The left-hand side is odd (a product of odd numbers) and the right-hand side is even for \(n\ge1\) (and \(2^0=1\ne3^m\)). Contradiction. \(\blacksquare\)
    3. \(3^{12}=531\,441\) and \(2^{19}=524\,288\). The ratio is \(\dfrac{531441}{524288}=1.0136\). This small gap is called the Pythagorean comma.

14. Answer to Question 14

    1. \(2\times3\times5\times7\times11\times13=30030\), so \(N=30031\).
    2. Each of the six primes divides 30030, so each leaves remainder \(30031-30030=1\) when dividing \(N\). None divides \(N\).
    3. \(30031=59\times509\). Both 59 and 509 are prime and neither is on the engineer’s list, so the list was incomplete. The same argument works for any finite list.
    4. \(N\) itself may be composite, as here. The proof only needs \(N\) to have at least one prime factor not on the list.

15. Answer to Question 15

    1. \(\log_23=\dfrac pq\) means \(2^{p/q}=3\). Raise both sides to the power \(q\): \(2^p=3^q\).
    2. Assume \(2^p=3^q\) with \(p,q\ge1\). The left-hand side is even and the right-hand side is odd (product of odd numbers). Even \(\ne\) odd, a contradiction. So \(\log_23\) cannot be a fraction. \(\blacksquare\)
    3. \(3^{12}=531\,441\), \(2^{19}=524\,288\), ratio \(1.0136\). ✓.
    4. Because \(3^m\) is always odd and \(2^n\) is always even, the ratio can never be 1.
    5. \(\left|\log_23-\frac32\right|=0.085\), \(\left|\log_23-\frac85\right|=0.015\), \(\left|\log_23-\frac{19}{12}\right|=0.0016\). The fraction \(\frac{19}{12}\) is the best, shown also by a ratio nearest 1.

16. Answer to Question 16

    1. Assume \(\sqrt3=\dfrac ab\) in lowest terms. Then \(a^2=3b^2\), so \(3\mid a^2\) and hence \(3\mid a\) (if \(3\nmid a\), then \(a^2\) leaves remainder 1). Put \(a=3k\): \(9k^2=3b^2\), \(b^2=3k^2\), so \(3\mid b\). Both divisible by 3 contradicts lowest terms. \(\blacksquare\)
    2. \(\sqrt3=r-\sqrt2\). Squaring: \(3=r^2-2r\sqrt2+2\), so \(2r\sqrt2=r^2-1\) and \(\sqrt2=\dfrac{r^2-1}{2r}\) (note \(r\ne0\) since \(\sqrt2+\sqrt3>0\)).
    3. The right-hand side \(\dfrac{r^2-1}{2r}\) is rational because \(r\) is rational. So \(\sqrt2\) would be rational, contradicting its irrationality. Hence \(\sqrt2+\sqrt3\) is irrational. \(\blacksquare\)
    4. \(\sqrt2+\sqrt3=1.4142+1.7321=3.1463\). A calculator shows only a finite number of digits, and a rational number can also have a long decimal expansion, so no finite decimal can prove irrationality.

17. Answer to Question 17

    1. \(f(-1)=-1<0\) and \(f(0)=1>0\), and \(f\) is continuous, so there is a root in \((-1,0)\) by the change of sign.
    2. \(\left(\dfrac pq\right)^3+\dfrac pq+1=0\). Multiplying by \(q^3\): \(p^3+pq^2+q^3=0\).
    3. \(p\) and \(q\) have no common factor, so they are not both even. Case 1: both odd: \(p^3+pq^2+q^3\) is odd + odd + odd = odd, not 0. Case 2: \(p\) even, \(q\) odd: even + even + odd = odd, not 0. Case 3: \(p\) odd, \(q\) even: odd + even + even = odd, not 0. Every case is a contradiction, so there is no rational root. \(\blacksquare\)
    4. Decimal search: \(f(-0.68)=0.0056>0\) and \(f(-0.69)=-0.0185<0\), so the root is between. Then \(f(-0.682)=0.0008>0\) and \(f(-0.683)=-0.0016<0\), so the root is \(x=-0.682\) to 3 d.p. This root is real but not rational, so it is irrational and cannot be written as a fraction.

18. Answer to Question 18

    1. \(30030+1=30031\) and \(59\times509=30031\) ✓. Euclid’s argument does not claim \(N\) is prime; it claims \(N\) has a prime factor not in the list. Here the prime factors 59 and 509 are new.
    2. Assume there is a largest prime \(P\). Consider \(M=P!+1\). \(M>1\), so it has a prime factor \(q\). Every integer from 2 to \(P\) divides \(P!\), so none divides \(M\) (each leaves remainder 1). So \(q>P\). This contradicts \(P\) being the largest prime. \(\blacksquare\)
    3. The prime factor \(q\) of \(P!+1\) satisfies \(P\lt q\le P!+1\), so a prime exists in that interval.
    4. \(5!+1=121=11\times11=11^2\). The prime factor 11 is greater than 5, as the proof predicts.

19. Answer to Question 19

    1. Perimeter \(2(a+b)=40\), so \(a+b=20\). Areas: \(10\times10=100\), \(5\times15=75\), \(8\times12=96\), \(9\times11=99\) ✓.
    2. Assume there are positive \(a,b\) with \(a+b=20\) and \(ab>100\). Then \(b=20-a\) and \(a(20-a)>100\), so \(20a-a^2-100>0\), i.e. \(-(a-10)^2>0\), so \((a-10)^2<0\). A real square cannot be negative. Contradiction. \(\blacksquare\)
    3. \((a-10)^2=0\), when \(a=10\): the square.
    4. Assume \(\dfrac{a+b}2\lt \sqrt{ab}\). Both sides are positive, so squaring preserves the inequality: \(\dfrac{(a+b)^2}4\lt ab\), so \((a+b)^2<4ab\), so \(a^2-2ab+b^2<0\), i.e. \((a-b)^2<0\). Contradiction. \(\blacksquare\)

20. Answer to Question 20

    1. \(p\mid n^2=n\times n\), so \(p\) divides one of the two factors, which are both \(n\). Hence \(p\mid n\). \(\blacksquare\)
    2. Assume \(\sqrt p=\dfrac ab\) in lowest terms. Then \(a^2=pb^2\), so \(p\mid a^2\) and by part (a) \(p\mid a\). Write \(a=pk\): \(p^2k^2=pb^2\), so \(b^2=pk^2\), so \(p\mid b^2\) and \(p\mid b\). Both are divisible by \(p\), contradicting lowest terms. \(\blacksquare\)
    3. Assume \(\sqrt6=\dfrac ab\) in lowest terms. Then \(a^2=6b^2\), so \(a^2\) is even and \(a\) is even: \(a=2k\). Then \(4k^2=6b^2\), so \(2k^2=3b^2\). The left side is even, so \(3b^2\) is even, which forces \(b^2\) even and \(b\) even. Both even contradicts lowest terms. \(\blacksquare\)
    4. For \(\sqrt4\), the number 4 is not prime, so the key step "\(p\mid n^2\Rightarrow p\mid n\)" cannot be used with \(p=4\): for example \(4\mid 2^2\) but \(4\nmid2\). Indeed \(\sqrt4=2\) is rational.