201609 Math 122 Assignment 4 Due: Wednesday, March 16, 2016, in class, before the lecture starts There are ve questions worth eight marks each, and one bonus question worth four marks. Answers that are complete and correct will receive full marks. Answers that are complete and substantially correct will receive about 70% of the marks available, depending on rounding. Small deductions will be made for minor errors. Complete solutions are those which are coherently written, and include appropriate justications. 1. Let f and g be the functions from {a, b, c, d, e, f } to {a, b, c, d, e, f } given in the following table: x= a b c d e f f (x) = c d a e b f g(x) = b c a e f d (a) Find f g and g f . (b) Show that g 1 = g 2 , where the notation g 2 means g g. (c) Find f 2 , f 3 , f 4 , f 5 and f 6 , where f 1 = f and f n = f n does this tell you about f 1 ? 2. Let f : ( 1, 1) ! R be dened by f (x) = 8 >0 < 1 >x :1 x 1 f for n 1. What if x = 0, 1 if 0 < x < 1, + 1 if 1 < x < 0, where ( 1, 1) is the open interval of real numbers between 1 and 1. (a) Prove that f is a 1-1 correspondence. (b) Show that R is uncountable by nding, with proof, a 1-1 correspondence between (0, 1) and R. (Hint: use part (a) and function composition.) 3. Let A1 , A2 , . . . be a countably innite collection of countably innite sets, where Ai = {ai,1 , ai,2 , ai,3 , . . .}. Consider the innite array in which the rst row is a1,1 , a1,2 , a1,3 , . . ., the second row is a2,1 , a2,2 , a2,3 , . . ., and in general the k-th row is ak,1 , ak,2 , ak,3 , . . .. (a) Explain why the array contains every element of A1 [ A2 [ . (In what cell of the array would one nd the element aij ?) (b) Show how to construct a sequence that contains every element of the array. (c) What does this tell you about |A1 [ A2 [ |? Why? (d) Formally state the theorem that has been proved in this question. 4. (a) Show that the set of all nite sequences of the numbers 0, 1, . . . , 9 is countably innite. (b) Show that the set of all innite sequences of the numbers 0, 1, . . . , 9 is uncountable. 5. (a) Suppose that each of n1 , n2 , . . . , nk is an odd integer, so that there exist integers `1 , `2 , . . . `k such that ni = 2`i + 1 for i = 1, 2, . . . , k. Prove that the sum n1 + n2 + + nk is even if and only if k is even. (b) Suppose (d5 d4 d3 d2 d1 d0 )9 is the base-9 representation of an even integer n (that is, an integer n which is a multiple of 2). Show that an even number of the digits dk , dk 1 , . . . , d0 belong to {1, 3, 5, 7}. That is, if t is the number of odd integers among dk , dk 1 , . . . , d0 , then t is an even number. Is the converse true? 6. (Bonus Problem; 4 bonus marks) A group of ve rened criminals come across stash consisting of ve $1000 bills. For reasons alluded to below, they eventually decide that a \"democratic\" way of deciding how to divide the loot is best. They number themselves by rank, with the leader being number 1 and the lowly getaway car driver being number 5. The following procedure is repeated until the loot is nally divided up. (a) The living criminal of lowest rank (i.e., with the highest number among the criminals still alive) proposes a way of dividing the loot. (b) All living criminals vote on the proposal. (c) If the proposal receives at least 50% of the votes, the loot is divided as proposed. Otherwise, the criminal who made the proposal is killed, and the process starts over. Everyone involved is aware of the following facts. All criminals are perfectly logical. All criminals want as much money as possible. They will reject a proposal if doing so guarantees getting more loot later. All criminals like killing other criminals. They will reject a proposal if doing so guarantees getting the same amount of loot later because voting this way may mean that the proposer is killed. The question is: If you are the getaway car driver (rened criminal number 5), what do you propose? Does it matter? Page 2