Logic, sets and proof techniques – university Year 1 maths worksheet answers to download as PDF

← Back to the worksheet

1. Answer to Question 1

   1. Negation: there exists a real number \(x\) with \(x^2\le0\). This is true because \(0^2=0\), so the original is false.
   2. Negation: for every integer \(n\), \(n^2\ne2\). This is true because \(1^2=1\), \(2^2=4\) and larger squares are bigger, so the original is false.
   3. Negation: there is an integer \(n\) that is prime and not odd. This is true with \(n=2\), so the original statement is false: one counterexample is enough.

2. Answer to Question 2

   1. Rows \((P,Q)\): (T,T): \(P\Rightarrow Q\) is T and \(\neg P\vee Q\) is T. (T,F): both F. (F,T): both T. (F,F): both T. The columns agree in all four rows, so the statements are equivalent.
   2. The only way the whole implication could fail is if \((P\Rightarrow Q)\wedge(Q\Rightarrow R)\) is true while \(P\Rightarrow R\) is false. \(P\Rightarrow R\) false needs \(P\) true and \(R\) false. Then \(P\Rightarrow Q\) true forces \(Q\) true, and \(Q\Rightarrow R\) with \(Q\) true forces \(R\) true, contradicting \(R\) false. So the failure never happens: the statement is true in all 8 rows, a tautology (the transitivity of implication).

3. Answer to Question 3

   1. Converse: if \(n\) is even, then \(n^2\) is even.
   2. Contrapositive: if \(n\) is odd, then \(n^2\) is odd.
   3. The contrapositive is true: \(n=2k+1\) gives \(n^2=4k^2+4k+1=2(2k^2+2k)+1\), which is odd. A statement is logically equivalent to its contrapositive, so S is true. The converse is true too: \(n=2k\) gives \(n^2=4k^2=2(2k^2)\), even.

4. Answer to Question 4

   1. \(A\cup B=\{1,2,3,4,5,6,8\}\), \(A\cap B=\{2,4,6\}\), \(A\setminus B=\{1,3,5\}\).
   2. \(A^c=\{7,8,9,10\}\) and \(A\triangle B=\{1,3,5,8\}\).
   3. \(A\) has \(6\) elements, so \(2^6=64\) subsets. The number with exactly 2 elements is \(\binom62=\dfrac{6\times5}2=15\).

5. Answer to Question 5

   1. Let the integers be \(2a+1\) and \(2b+1\). The sum is \(2a+2b+2=2(a+b+1)\), which is even.
   2. Let \(n=2k+1\). Then \(n^2-1=4k^2+4k=4k(k+1)\). The product \(k(k+1)\) of consecutive integers is even (part c), say \(2m\), so \(n^2-1=8m\), divisible by 8.
   3. Let the integers be \(k\) and \(k+1\). If \(k\) is even the product is even. If \(k\) is odd then \(k+1\) is even, so the product is even. In every case \(k(k+1)\) is even.

6. Answer to Question 6

   1. Base: \(n=1\): left side \(1\), right side \(\dfrac{1\cdot2}2=1\). Step: assume it holds for \(n=k\). Then \(1+\cdots+k+(k+1)=\dfrac{k(k+1)}2+(k+1)=\dfrac{(k+1)(k+2)}2\), which is the formula for \(n=k+1\). By induction it holds for all \(n\ge1\).
   2. Base: \(n=1\): \(1=\dfrac{1\cdot2\cdot3}6\). Step: assume true for \(n=k\). Then the sum to \(k+1\) is \(\dfrac{k(k+1)(2k+1)}6+(k+1)^2=\dfrac{(k+1)\left[k(2k+1)+6(k+1)\right]}6=\dfrac{(k+1)(2k^2+7k+6)}6=\dfrac{(k+1)(k+2)(2k+3)}6\), which is the formula for \(n=k+1\) (since \(2(k+1)+1=2k+3\)). Done.

7. Answer to Question 7

   1. \(P\): the card has a vowel; \(Q\): the card has an even number on the other side. The claim is \(P\Rightarrow Q\).
   2. A claim \(P\Rightarrow Q\) fails only when \(P\) is true and \(Q\) is false: a vowel with an odd number. The E might hide an odd number, and the 7 might hide a vowel.
   3. Turn over E (check there is an even number) and 7 (check there is no vowel on the back, which is the contrapositive: not even implies not vowel). The K and the 4 cannot make the claim false.
   4. Whatever is behind the 4, the claim is not broken: a vowel with 4 agrees with the claim and a consonant with 4 is not covered by it. Most people choose 4 by mistake, confusing the claim with its converse.

8. Answer to Question 8

   1. Only maths: \(25-8=\) 17. Only physics: \(18-8=\) 10. Both: 8.
   2. At least one: \(17+10+8=\) 35. Neither: \(40-35=\) 5.
   3. \(25+18-8=35\), which matches.
   4. Exactly one subject: \(17+10=27\). The probability is \(\dfrac{27}{40}=\) 0.675.

9. Answer to Question 9

   1. Each topping is chosen or not, so there are \(2^6=\) 64 subsets.
   2. Remove the empty set: \(64-1=\) 63.
   3. \(\binom63=\dfrac{6\times5\times4}{3\times2\times1}=\) 20.
   4. \(\binom60+\binom61+\binom62=1+6+15=\) 22, which is \(\dfrac{22}{64}=\dfrac{11}{32}\) of all orders.

10. Answer to Question 10

    1. Row 1 kept; row 2 broken (rain but no cancellation); row 3 kept; row 4 kept.
    2. Contrapositive: "If the match was not cancelled, then it did not rain." So it did not rain.
    3. No. The announcement does not say that rain is the only reason: the pitch might be flooded, or the other team might not turn up. This would be the converse.
    4. Converse: "If the match is cancelled, then it rains". It may be false, since a match can be cancelled for other reasons.

11. Answer to Question 11

    1. \(1+2+3+4+5=\) £15; \(\dfrac{20\times21}2=\) £210.
    2. Base \(n=1\): £1 \(=\dfrac{1\cdot2}2\). Step: if true for \(k\), then after \(k+1\) weeks she has \(\dfrac{k(k+1)}2+(k+1)=\dfrac{(k+1)(k+2)}2\), the formula for \(k+1\).
    3. \(\dfrac{n(n+1)}2>500\) means \(n(n+1)>1000\). \(31\times32=992\) (not enough) and \(32\times33=1056\). So 32 weeks.
    4. Week 32 deposit: £32. Total after week 31: \(\dfrac{31\times32}2=\) £496, so the week 32 deposit lifts her total to £528.

12. Answer to Question 12

    1. \(M_1=1\), \(M_2=3\), \(M_3=7\): indeed \(2^1-1=1\), \(2^2-1=3\), \(2^3-1=7\).
    2. To move \(n+1\) discs, first move the top \(n\) discs to the spare peg (\(M_n\) moves), move the largest disc (1 move), then move the \(n\) discs back on top (\(M_n\) moves): \(M_{n+1}=2M_n+1\). Base: \(M_1=1=2^1-1\). If \(M_k=2^k-1\) then \(M_{k+1}=2(2^k-1)+1=2^{k+1}-1\). Done by induction.
    3. \(M_{10}=1023\); \(M_{20}=1\,048\,575\).
    4. \(1\,048\,575\div86\,400\approx\) 12.1 days.

13. Answer to Question 13

    1. Reflexive: \(12\mid(a-a)=0\). Symmetric: if \(12\mid(a-b)\) then \(12\mid(b-a)\). Transitive: if \(a-b=12m\) and \(b-c=12n\) then \(a-c=12(m+n)\).
    2. Twelve classes, one for each remainder \(0,1,\dots,11\) on division by 12; the class of 0 is the 12 o'clock class.
    3. \(100=8\times12+4\), so the clock moves on 4 hours: \(9+4=13\equiv\) 1 o'clock.
    4. \(250=20\times12+10\), so going back 10 hours: \(9-10=-1\equiv\) 11 o'clock.

14. Answer to Question 14

    1. There are 12 months (boxes) and 13 people (objects), so some month is shared.
    2. There are at most 366 possible birthdays and 367 students, so two must coincide.
    3. With 24 people it is possible that each month appears exactly twice. With 25 people, some month must appear at least 3 times (otherwise \(12\times2=24<25\)). So 25 people.
    4. Suppose that every box contains at most one object. Then the total number of objects is at most \(n\), contradicting the assumption that there are more than \(n\). So some box has two.

15. Answer to Question 15

    1. \(f(10)=100+10+41=151\), prime. \(f(39)=1521+39+41=1601\), prime. \(f(2)=4+2+41=47\), prime.
    2. \(f(40)=1600+40+41=1681=41^2\). It is not prime, so the conjecture is false: \(n=40\) is a counterexample.
    3. \(f(41)=41^2+41+41=41(41+1+1)=41\times43\), a product of two numbers greater than 1.
    4. A universal statement "for all \(n\)" needs a proof that works for every \(n\). Examples (even 40 of them) only support it. One counterexample shows that the "for all" statement is false.

16. Answer to Question 16

    1. If \(F(a)=F(b)\) then \(\dfrac95a=\dfrac95b\), so \(a=b\): injective. For any \(y\), \(C=\dfrac59(y-32)\) gives \(F(C)=y\): surjective. So \(F^{-1}(F)=\dfrac59(F-32)\).
    2. \(K\left(F^{-1}(F)\right)=\dfrac59(F-32)+273.15\).
    3. \(\dfrac95C+32=C\) gives \(\dfrac45C=-32\), so \(C=\) \(-40\): both scales agree at \(-40\).
    4. No. On \(C\ge-273.15\) the image is \(F\ge-459.67\), not all of \(\mathbb R\). So it is injective but not surjective onto \(\mathbb R\); it is a bijection onto \([-459.67,\infty)\).

17. Answer to Question 17

    1. Reflexive: \(a-a=0\) is divisible by 3. Symmetric: \(3\mid(a-b)\Rightarrow3\mid(b-a)\). Transitive: if \(a-b=3m\) and \(b-c=3n\) then \(a-c=3(m+n)\).
    2. Class of 0: \(\{\dots,-3,0,3,6,\dots\}\); class of 1: \(\{\dots,-2,1,4,7,\dots\}\); class of 2: \(\{\dots,-1,2,5,8,\dots\}\).
    3. \(100=33\times3+1\), so pile of 1. \(-7=-9+2\), so pile of 2.
    4. Write \(a-b=3m\) and \(c-d=3n\). Then \((a+c)-(b+d)=3(m+n)\). For products, \(ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)=3(cm+bn)\), divisible by 3.

18. Answer to Question 18

    1. Suppose \(\sqrt2=\dfrac pq\) in lowest terms. Then \(p^2=2q^2\), so \(p^2\) is even and therefore \(p\) is even (previous exercise), say \(p=2m\). Then \(4m^2=2q^2\), so \(q^2=2m^2\) and \(q\) is even. Both \(p\) and \(q\) are even, contradicting lowest terms.
    2. Suppose \(\sqrt2+1=r\) is rational. Then \(\sqrt2=r-1\) is rational, contradicting (a).
    3. The left side \(2^a\) is even for \(a\ge1\) and the right side \(3^b\) is odd for every \(b\), so they cannot be equal.
    4. Suppose \(\log_23=\dfrac pq\) with positive integers \(p,q\). Then \(2^{p/q}=3\), so \(2^p=3^q\), contradicting (c).

19. Answer to Question 19

    1. False for \(n=2\) (equal), \(n=3\) (\(8<9\)) and \(n=4\) (equal). It is true for \(n=1\) (\(2>1\)), and \(n\ge5\).
    2. Base \(n=5\): \(32>25\). Step: assume \(2^k>k^2\) for some \(k\ge5\). Then \(2^{k+1}=2\cdot2^k>2k^2\). Now \(2k^2\ge(k+1)^2\) because \(k^2-2k-1\ge0\) for \(k\ge3\) (at \(k=5\) this is \(14\), and it increases). So \(2^{k+1}>(k+1)^2\).
    3. Base \(n=1\): \(7-1=6\). Step: assume \(7^k-1=6m\). Then \(7^{k+1}-1=7\cdot7^k-1=7(6m+1)-1=42m+6=6(7m+1)\), divisible by 6.
    4. The exponential algorithm becomes slower than the quadratic one from \(n=5\) onwards, and the gap grows without limit, so it is unusable for large inputs.

20. Answer to Question 20

    1. Base: \(n=2\) is prime. Hypothesis: every integer \(m\) with \(2\le m\lt n\) is a product of primes.
    2. If \(n\) is prime, it is a product of one prime. If \(n\) is not prime, then \(n=ab\) with \(2\le a,b\lt n\). By the hypothesis \(a\) and \(b\) are products of primes, so \(n=ab\) is too.
    3. \(360=36\times10=(6\times6)\times(2\times5)=2^3\times3^2\times5\).
    4. The factors \(a\) and \(b\) can be any smaller numbers, not just \(n-1\). We need all smaller cases, which is exactly what strong induction provides.