title_temp

Mathematics 220 Final Examination, April 23 2016

Mathematics 220 Final Examination, April 23 2016 Page 1 of 14

page1image21308032

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):

Student-No:

Signature:

UBC Rules governing examinations:

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

  2. 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.

  3. 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.

  4. 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:

page1image21313024 page1image21311488page1image21304768page1image21304384 page1image21314752page1image21302272 page1image21312256

Mathematics 220 Final Examination, April 23 2016 Page 2 of 14

page2image21855424

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 closed-book 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.

page3image21907712 page3image21918656

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: ?aA ?bB, s.t. ?cC, (c?3<b) =? (c2 ?9<a).

page3image21889408 page3image21898048

4 marks

(b) State the definition that the sets A and B have equal cardinality.

page3image21900352 page3image22000384

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.) nN

page3image22001152 page3image21766400

Mathematics 220 Final Examination, April 23 2016 Page 4 of 14

page4image21004032 page4image20992128

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.

page4image20995968 page4image20989248

4 marks

(b) There exists a bijective function between the set of all rational numbers and the set of all irrational numbers.

page4image20992896 page4image20998080

4 marks

√√
(c) 2 ? 3 3 is irrational.

page4image21002112

Mathematics 220 Final Examination, April 23 2016 Page 5 of 14

page5image21180224 page5image21183488

4 marks

(d) Given two arbitrary real numbers a and b, if a and b are both irrational then a ? b is irrational.

page5image21175424 page5image21175808

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.

page5image21180608

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.

page6image21181760 page6image21175232 page6image21168320 page6image21180992

8 marks (b) Prove that for every integer n 0 , the sum n3 +(n+1)3 +(n+2)3 is divisible by 9.

page6image21298944

Mathematics 220 Final Examination, April 23 2016 Page 7 of 14

page7image21853312

This page has been left blank for your workings and solutions.

Mathematics 220 Final Examination, April 23 2016 Page 8 of 14 8marks 4. LetaR?{1}. ProvethatforallnN,

??n an+1 ? a

ak= a?1 . k=1

page8image21205888 page8image21211072 page8image21213760 page8image21209920

Mathematics 220 Final Examination, April 23 2016 Page 9 of 14

page9image21267968

5. Supposethatf:ABisafunctionandletCbeasubsetofA. 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).

page9image21270272 page9image21270848 page9image21267200 page9image21269696

Mathematics 220 Final Examination, April 23 2016 Page 10 of 14

page10image21841408 page10image21841984

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.

page10image21847552

Mathematics 220 Final Examination, April 23 2016 Page 11 of 14

page11image21853504 page11image21852736

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.

page11image21756736

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.

page12image21268352 page12image21268544 page12image21272768

Mathematics 220 Final Examination, April 23 2016 Page 13 of 14

page13image21207808 page13image21208576

6 marks (b) Prove that if a connected graph with n vertices has exactly n ? 1 edges, then it is a tree.

page13image21203584

Mathematics 220 Final Examination, April 23 2016 Page 14 of 14

page14image21262720 page14image21244800

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.

page14image21247104