Mathematics 220 Final Examination, April 23 2016
Mathematics 220 Final Examination, April 23 2016 Page 1 of 14
This final exam has 8 questions on 14 pages, for a total of 100 marks.
Duration: 2 hours 30 minutes
Full Name (including all middle names):
StudentNo:
Signature:
UBC Rules governing examinations:

Each candidate should be prepared to produce his/her library/AMS card upon request.

No candidate shall be permitted to enter the examination room after the expiration of one half hour, or to leave during the first half hour or the last 15 minutes of the examination. Candidates are not permitted to ask questions of the invigilators, except in cases of supposed errors or ambiguities in the examination questions.

Candidates guilty of any of the following or similar practices shall be immediately dismissed from the examination, and shall be liable to disciplinary action:
a) Making use of any books, papers or memoranda, other than those authorised by the examiners.
b) Speaking or communicating with other candidates.
c) Purposely exposing written papers to the view of other candidates. The plea of accident or forgetfulness will not be received.

Smoking is not permitted during examinations.
Question: 1 2 3 4 5 6 7 8 Total Points: 12 23 14 8 10 12 12 9 100 Score:
Mathematics 220 Final Examination, April 23 2016 Page 2 of 14
Please read the following points carefully before starting to write.

Read all the questions carefully before starting to work.

With the exception of Q1, you should give complete arguments and explanations for
all your calculations; answers without justifications will not be marked.

Continue on the back of the previous page if you run out of space.

Attempt to answer all questions for partial credit.

This is a closedbook examination. None of the following are allowed: documents, cheat sheets or electronic devices of any kind (including calculators, cell phones, etc.)

You may not leave during the first 30 minutes or final 15 minutes of the exam.
4 marks
Mathematics 220 Final Examination, April 23 2016 Page 3 of 14 1. Short answer questions: an answer without proof is sufficient.
(a) Let A, B and C be subsets of R. Negate the following statement: ?a∈A ?b∈B, s.t. ?c∈C, (c?3<b) =? (c2 ?9<a).
4 marks
(b) State the definition that the sets A and B have equal cardinality.
4 marks
(c) Let R be the universal set. For n ∈ N, let Sn be the interval Sn = (?1/n, n2 + 1].
Find ?? Sn. (Here, we think of the real line R as the universal set.) n∈N
Mathematics 220 Final Examination, April 23 2016 Page 4 of 14
5 marks
2. Determine whether the following statements are True or False. If a statement is True, provide a brief explanation why (you can refer to anything covered in class). If a state ment is False, provide a counterexample.
(a) The set {p/q : p and q are prime} is denumerable.
4 marks
(b) There exists a bijective function between the set of all rational numbers and the set of all irrational numbers.
4 marks
√√
(c) 2 ? 3 3 is irrational.
Mathematics 220 Final Examination, April 23 2016 Page 5 of 14
4 marks
(d) Given two arbitrary real numbers a and b, if a and b are both irrational then a ? b is irrational.
6 marks
(e) Let S denote the set of all sequences a1a2a3a4a5 . . . where, for all i ∈ N, ai ∈ {0, 1}. A student was asked to prove that S × S = S. The student wrote the following: Write S = {s1,s2,...}. Then
S × S = {(s1, s1), (s1, s2), . . . ; (s2, s1), (s2, s2), . . . ; . . . ; (sn, s1), (sn, s2), . . . ; . . .}.
This set of pairs can be arranged in a table: in the first row, put the pairs
(s1, s1), (s1, s2), (s1, s3), . . . , in the second row – the pairs where the first elements is s2, and so on. As discussed in class, we have an algorithm to list all the elements in this table as a single list, and thus we get that the cardinality of this set of pairs is the same as the cardinality of the set S.
Is this proof correct or not? If right, no explanation is needed; if wrong, briefly explain why.
Mathematics 220 Final Examination, April 23 2016 Page 6 of 14 6 marks 3. (a) Prove that for all integers n, n3 ≡ (n + 3)3 mod 9.
8 marks (b) Prove that for every integer n ≥ 0 , the sum n3 +(n+1)3 +(n+2)3 is divisible by 9.
Mathematics 220 Final Examination, April 23 2016 Page 7 of 14
This page has been left blank for your workings and solutions.
Mathematics 220 Final Examination, April 23 2016 Page 8 of 14 8marks 4. Leta∈R?{1}. Provethatforalln∈N,
??n an+1 ? a
ak= a?1 . k=1
Mathematics 220 Final Examination, April 23 2016 Page 9 of 14
5. Supposethatf:A→BisafunctionandletCbeasubsetofA. 5 marks (a) Prove that f(A) ? f(C) ? f(A ? C).
5 marks (b) Find a counterexample for f(A ? C) ? f(A) ? f(C).
Mathematics 220 Final Examination, April 23 2016 Page 10 of 14
8 marks 6. (a) Let f : Z×Z → Z be a function defined as f(a,b) := 4a+6b. Explicitly describe the set S := range(f). Prove your answer.
Mathematics 220 Final Examination, April 23 2016 Page 11 of 14
4 marks (b) Let f be the same function as in part (a), and let g : Z → N∪{0} be the function g(x) = x2. Explicitly describe the composite function g ? f.
Mathematics 220 Final Examination, April 23 2016 Page 12 of 14 6 marks 7. (a) Prove that if G is a connected graph with n vertices, then G has at least n?1 edges.
Mathematics 220 Final Examination, April 23 2016 Page 13 of 14
6 marks (b) Prove that if a connected graph with n vertices has exactly n ? 1 edges, then it is a tree.
Mathematics 220 Final Examination, April 23 2016 Page 14 of 14
9 marks 8. Let S and T be two arbitrary sets. Prove that if the sets S ?T and T ?S have the same cardinality, then the sets S and T have the same cardinality.