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

← Back to the test

1. Answer to Question 1 (4 marks)

   1. There exists a real \(x\) such that for every real \(y\), \(y\le x\) (2).
   2. If \(n\) is not even (odd), then \(n\) is not divisible by 6 (2).

   In (a), negating swaps each quantifier, \(\forall\) becomes \(\exists\) and \(\exists\) becomes \(\forall\), and the final statement \(y\gt x\) becomes \(y\le x\), not \(y\lt x\). The original statement is true, so its negation is false: no real number is greater than or equal to every real number. In (b), the contrapositive of \(P\Rightarrow Q\) is \(\neg Q\Rightarrow\neg P\), which is logically equivalent to the original. A common error is to give the converse, if \(n\) is even then \(n\) is divisible by 6, which is false (take \(n=4\)).

2. Answer to Question 2 (4 marks)

   1. At least one language: \(50-10=40\) (1). \(|F\cup S|=30+22-|F\cap S|=40\) (1), so both \(=12\) (1).
   2. Exactly one: \(40-12=28\) (1).

   In (a), the 10 people who speak neither language are outside both sets, so \(|F\cup S|=40\). The inclusion-exclusion principle corrects for counting the people in \(F\cap S\) twice when adding 30 and 22. Solving \(52-|F\cap S|=40\) gives 12. In (b), French only is \(30-12=18\) and Spanish only is \(22-12=10\), and \(18+10=28\). Check with a Venn diagram: \(18+12+10+10=50\) people in total.

3. Answer to Question 3 (4 marks)

   Let the integers be \(n\), \(n+1\), \(n+2\) (1). Their sum is \(3n+3\) (2), which is \(3(n+1)\), divisible by 3 (1).

   This is a direct proof: we start from the general form of three consecutive integers and reach the conclusion by algebra. Since \(n\) is an integer, \(n+1\) is an integer, so \(3(n+1)\) is a multiple of 3 by definition of divisibility. Checking examples such as \(4+5+6=15\) illustrates the result but proves nothing. A neater choice is \(n-1\), \(n\), \(n+1\), whose sum is \(3n\) directly.

4. Answer to Question 4 (4 marks)

   Suppose there is a largest prime and list all primes \(p_1,\dots,p_k\) (1). Let \(N=p_1p_2\cdots p_k+1\) (1). \(N\) leaves remainder 1 when divided by each \(p_i\), so no \(p_i\) divides \(N\) (1). But \(N>1\) has a prime factor, which is a prime not in the list: contradiction (1).

   The proof does not claim that \(N\) itself is prime: for example \(2\times3\times5\times7\times11\times13+1=30\,031=59\times509\). It only shows that some prime outside the finite list must exist.

5. Answer to Question 5 (4 marks)

   Base \(n=1\): \(1=1^2\) (1). Assume \(\sum_{i=1}^k(2i-1)=k^2\) (1). Then \(\sum_{i=1}^{k+1}(2i-1)=k^2+2(k+1)-1=k^2+2k+1\) (1) \(=(k+1)^2\) (1).

   The base case checks that the statement holds for the first value. The inductive hypothesis assumes the statement for some \(k\ge1\). In the inductive step, the sum up to \(k+1\) is the sum up to \(k\) plus the next term \(2(k+1)-1=2k+1\), and the hypothesis replaces the first part with \(k^2\). Since \(k^2+2k+1=(k+1)^2\), the statement holds for \(k+1\). By the principle of mathematical induction it holds for all \(n\ge1\): the first \(n\) odd numbers always add up to \(n^2\), for example \(1+3+5+7=16\).

Total : 20 marks