MATH 211 Final, Spring 2015

MATH 211-2015S AUB FINAL EXAM NAME: SECTION: INSTRUCTIONS: (1) Begin by writing your name and section. (2) Keep your ID on the desk and your cell phone away. (3) Read the questions carefully before you attempt to answer. (4) Give concise justification to all your answers. • Suppose that the variable x represents students and y represents courses, and: U(y): y is an upper-level course M(y): y is a math course F(x): x is a freshman A(x): x is a part time student T(x, y): student x is taking course y. Write the statements below using these predicates and any needed quantifiers. (i) (2 pt.) there is a part time freshman student who is not taking any course. (ii) (2 pt.) every freshman student is taking exactly one math course. (iii) (2 pt.) there are at least two freshmen students who are taking the same upper level math courses. 1 • (3 pt.) Let S be a set with at least two elements. Show that the number of possible one-to- one functions from S to an arbitrary set T is even. Make sure to discuss all possibilities. • (3 pt.) Prove that an integer n is odd unless 5n2 + 16 is even, stating clearly what must be proven. • (3 pt.) Among the integers between 56 and 560 inclusive, how many are neither divisible by 4 nor divisible by 6? • (3 pt.) Consider the system of two congruence equations: � 2x + 4 ≡ 3 mod 17 5x − 4 ≡ 1 mod 18. Show without actually solving the system, that infinitely many integers satisfy the two congruence equations simultaneously. • (3 pt.) A communication channel can transmit four types of signals, a, b, c and d. Signal a is transmitted in 3 microseconds while each of the other three signals takes one microsecond to be transmitted. So, for example, some of the possible messages that can be transmitted in 3 microseconds are: a, bcd, bbc, and cbc. Write a recurrence relation for the number of distinct messages that can be transmitted in n microseconds. Specify any necessary initial conditions. • (3 pt.) Consider any 5 points in xy-plane, say (ai, bi), i = 1, · · · , 5 such that every point has integer coordinates. Recalling that the midpoint of (x1, y1) and (x2, y2) is (x1 + x2 2 , y1 + y2 2 ), use the pigeon hole principle to show that the midpoint of at least one pair of these points must also have integer coordinates. • (3 pt.) Write the general solution of the recurrence equation an = 2an−1 − an−1 • (3 pt.) Find a particular solution of the recurrence equation an = 2an−1 − an−2 + 2n • (3 pt.) Use Pascal’s identity to show that r � k=0 �n + k k � = �n + r + 1 r � , where n and r are two positive integers. Hint: Pascal’s identity states that �n+1 k+1 � = �n k � + � n k+1 � . • (3 pt.) Give a recursive definition for the set of bit strings that are palindromes. For the following three problems, consider a group of people consisting of Luna, Lina and six other persons. • (3 pt.) Find the total number of ways to divide the group into two subgroups of the same size so that Luna and Lina are not together. • (3 pt.) Find the total number of ways to place the eight people in four rooms (with two people in each room) so that Luna and Lina are roommates. • (3 pt.) Find the total number of ways to make a committee consisting of a president, vice president, treasurer and secretary so that both Luna and Lina serve on the committee. • (3 pt.) 10 indistinguishable balls are placed in five distinguishable boxes. Find the number of ways so that box 1 receives exactly two ball while box 2 receives at least one ball. BONUS (3 pt.) Describe the set A of binary strings defined recursively by the following steps. Base Step: ‘0’ belongs to A. Recursive Step: if w1 and w2 are strings in A, then so are the strings 1w1w2, w11w2 and w1w21.