MA103 Past Paper Exam PDF

Preview

Summary

Covers all the topics taught in MT and LT; a very challenging practice paper to attempt...

Description

Summer 2021 Assessment

MA103 Introduction to Abstract Mathematics Suitable for all candidates Instructions to candidates This paper contains 6 questions. Your answers to all 6 questions will count towards the final mark. All questions carry an equal number of marks. Answers should be justified by showing work. Please write your answers in dark ink (black or blue) on white paper only. Start your answer to a new question on a new sheet of paper. At the top of each sheet of paper, please write the question number you are answering on that page. At the top of each sheet of paper, please write your 5-digit candidate number for this academic year. Answers and all working should be uploaded in the question order. Ensure you do not write your name or LSE ID number anywhere.

Keep all rough work and upload it with your answers. Indicate rough work by drawing a line through it.

Assessment has to be uploaded within the 24-hour window as specified on the exam timetable. Expected effort for completing the exam: 3 hours

You are supplied with this examination paper only. You may use the course materials, including anything on the course’s Moodle page, lecture notes and your own notes.

© LSE ST 2021/MA103

Page 1 of 5

Question 1 (a)

Let a, b, c be natural numbers, and define statements p to be ‘b|a’ and q to be ‘b|c’. Consider the statement ‘If exactly one of p and q is true, then b 6 | (a + c).’ Is this statement true for all a, b, c ∈ N? What is its converse, and is that true for all a, b, c ∈ N? Justify your answers.





Let S = (a, b, c) : a, b, c ∈ Q \ {(0, 0, 0)}. We define a relation ∼ on S by (a, b, c) ∼ (d, e, f ) if and only if there exists r ∈ Q such that a = dr, b = er and c = f r. (b)

Show that ∼ is an equivalence relation.

Given a pair (a, b, c), (d, e, f ) ∈ S 2 , we say the pair is incident if ad + be + cf = 0.





(c)

Prove that if X and Y are two equivalence classes of ∼, then either all pairs of X × Y are incident or none are.

(d)

Explain why the following statement is well-defined:   We say [(ℓ, m, n)]∼ and [(p, q, r )]∼ are incident if (ℓ, m, n), (p, q, r) is incident.

(e)

Let N be your five-digit candidate number. Is it true that [(N, 2 + N, 1)]∼ and [(2, 3, 1 − 5N )]∼ are incident?

(f)

Does there exist X ∈ S/∼ such that X and X are incident?

Question 2 Let N be your five-digit candidate number. We define a sequence (an )n∈N as follows. We set a1 = 3 and a2 = 17. For each n ≥ 3, we define an by the following formula.

( an−1 + an−2 if an−1 + an−2 ≤ N an = an−1 + an−2 − N otherwise (a)

Prove that for each n ∈ N we have 1 ≤ an ≤ N .

(b)

Use the Pigeonhole Principle to show that there exist k, t ∈ {1, 2, . . . , N 2 + 1} such that the following holds. For each n ≥ k , we have an+t = an .

For each n ≥ 1, we define

bn =

n X

am 10−7m .

m=1

(c)

Prove that (bn )n∈N converges.

Let b = limn→∞ bn . (d)

Is b ∈ Q? Justify your answer briefly.

(e)

Let S = {x ∈ R : x3 − bn x2 ≥ 0 for all n ∈ N}. Show that, for every k ∈ N, bk ∈ / S . Show also that b ∈ S . What does this imply about inf S ?

© LSE ST 2021/MA103

Page 2 of 5

Question 3 (a)

We wish to prove, using the definition of convergence, that, if (xn )n∈N is a sequence of positive real numbers with xn → 1 as n → ∞, then 1/xn → 1 as n → ∞. You are given, below, four proposals for such a proof. For each of them, either explain why the proof does not work, or fill in the missing details of the proof. (i) Take any ε > 0. Since xn → 1 as n → ∞, there is some n0 ∈ N such that, for n > n0 ,

|xn − 1| < ε/2. For n > n0 ,

  1 − 1 < ε. Therefore 1/xn → 1 as n → ∞. xn

and so 

(ii) Take any ε > 0. Since xn → 1 as n → ∞, there is some n0 ∈ N such that, for n > n0 ,

|xn − 1| < ε|xn |. For n > n0 ,

  1 − 1 < ε. Therefore 1/xn → 1 as n → ∞. xn

and so 

(iii) Take any ε > 0. Since xn → 1 as n → ∞, there is some n0 ∈ N such that, for n > n0 ,

1  − 1 < ε. Therefore 1/xn → 1 as n → ∞. xn (iv) Take any ε > 0. Since xn → 1 as n → ∞, there is some n0 ∈ N such that, for n > n0 ,   1 − 1 < ε. Therefore 1/xn → 1 as n → ∞. |xn − 1| < ε − ε2 . For n > n0 , and so  xn

|xn − 1| <

ε 1+ε .

For n > n0 ,

and so 

Let g : [0, ∞) → R be a continuous function, with 1 ≤ g(x) ≤ 2 for all x ≥ 0. (b)

Show that there is some c ∈ (0, ∞) with g(c) = 4/c.

(c)

Show that the function h(x) = g(x) − 4/x has a minimum on [1, ∞) – i.e., there is some c ∈ [1, ∞) such that h(c) ≤ h(x) for all x ∈ [1, ∞). Show however that h(x) does not have a minimum on (0, ∞).

© LSE ST 2021/MA103

Page 3 of 5

Question 4 (a)

Give a careful proof from the axioms N1 to N13, as well as (P1) to (P6) from the lecture notes, of the following statement:

∀ x, y ∈ N, x + y = 2 =⇒ (x = 1 ∧ y = 1). Any statement other than N1–N13 and (P1)–(P6) has to be carefully proved. (b)

Define an operation on our construction of the integers by [(a, b)] ⊟ [(c, d)] = [(a + d, b + c)] for all equivalence classes [(a, b)], [(c, d)], where a, b, c, d ∈ N. Is this operation well defined? Justify your answer. It is not necessary to give a detailed, step-by-step proof, but indicate all of the axioms N1–N13 that you use.

(c)

Let S be the set of all real numbers in the interval [0, 1) that have a decimal expansion

0.a1 a2 a3 a4 . . . (i)

where each ai ∈ {3, 5}.

Prove that S is an uncountable set.

(ii) Give an example of a rational number and of an irrational number in S . Explain why your examples are indeed rational and irrational, respectively. (iii) Explain why the set S ∩Q is an infinite countable set, where Q is the set of rational numbers. (iv) Does S contain a real number that is not an algebraic number? Justify your answer.

Question 5 (a)

Let m = 10100 + 1010 and n = 10100 − 1010 . Show that gcd(m, n) = 1010 , and find integers x and y such that xm + yn = 1010 .

(b)

(i)

Consider the following subset of GL(3, R):

     1 a b  G =  0 1 c  a, b, c ∈ Z .   0 0 1 

Prove that G is a subgroup of GL(3, R). (ii) Is G abelian?

(iii) Is there an element of order 2 in (G, ∗)? Let H = Z × Z and for two elements (a, b), (c, d) ∈ H , let ⊕ be defined as

(a, b) ⊕ (c, d) = (a + c, b + d). You may assume that (H, ⊕) is a group. Let φ : G → H be given by:

 1 a b 7 (a, c). φ: 0 1 c → 0 0 1 

(iv) Prove that φ is a homomorphism. What are the kernel and image of φ? (c)

Let (G, ∗) be a group and let H = {h ∈ G | g ∗ h = h ∗ g ∀g ∈ G}. Prove that H is a subgroup of G.

© LSE ST 2021/MA103

Page 4 of 5

Question 6 (a)

Determine whether each of the following statements is true or false. Give a reason for your answer. (i) For all m ∈ N, if 2x = 4 has a solution in Zm then 2 has an inverse in Zm . (ii) For all m ∈ N, if 2x = 5 has a solution in Zm then 2 has an inverse in Zm .

(b)

Prove that for all prime numbers p and q we have p2 + q 2 6≡ 3 (mod 6).

(c)

Let M3 (R) be the vector space of all 3 × 3 matrices with real entries and let L3 be the following subset:

       a11 a12 a13  L3 =  a21 a22 a23  ∈ M3 (R)  a11 + a22 + a33 = 0 .    a31 a32 a33

(i) Show that L3 is a subspace of M3 (R). (ii) For each i, j ∈ {1, 2, 3}, let Eij denote the 3 × 3 matrix whose entries are all 0, except for the entry aij = 1. Prove that

B = {E12 , E21 , E23 , E32 , E13 , E31 , E11 − E22 , E22 − E33 } is a basis for L3 . (iii) Let T : L3 → R3 be given by



 a11 a12 a13 T  a21 a22 a23  = (a13 , a22, a31 ). a31 a32 a33

Prove that T is a linear transformation.

(iv) What is the dimension of the image of T ? Use the Rank–Nullity Theorem to determine the dimension of ker(T ).

END OF PAPER © LSE ST 2021/MA103

Page 5 of 5...