Mat 140: Bonus Sheet 1 Name: Instructions: Circle one of the options below. You may choose only one. You can decide which option you want after the final exam. Turn in this assignment with the final. 1. Replace the lowest test grade with the final exam, if the final exam grade is better than the lowest test grade. 2. Apply the worksheet as raw bonus points on the final exam. If you choose option 1, then do problems 1-5 with reasonable progress by getting at least 65 percent credit overall for these five problems. If you choose option 2, you may do any number of problems to receive bonus credit on the test; the bonus points each problem is worth is parenthetically listed next to the problem. If you choose option 1, then there will be no bonus points applied to the final. Staple your work to this sheet. Problem 1: (1 point) Write a truth table for the following logical expression [p (q r)] (q p) Problem 2: (1 point) Prove the following theorem: Suppose a and b are integers. If 3 | a and 5 | b then 15 | (ab 6b + 10a). Problem 3: (1 point) Prove the following theorem: Suppose a is an integer. If a2 + 2a is odd then a is odd. Problem 4: (1 point) Prove the following theorem: Suppose p R. If p3 3 is irrational then p is irrational. Problem 5: (1 point) Suppose we have a group of 30 computers and 4 are deficient. If we select 5 computers from the 30 at random, what is the probability that we have no deficient computers in our selected group of 5? (You may leave your answer in terms of product/quotients/sums of combinations and/or integers.) If you are only doing the page for the chance for the final to replace a low test grade, you don't need to do the following problems. Problem 6: (3 points) If we place the numbers 1, 2, 3, . . . , 10 in a circle (as in a clock) in any order, then at least three consecutive numbers in our circle will sum to 16 or higher. Present an argument on why this is true; don't quote specific examples as proof, since they won't cover all 9!/2 = 181400 possible configurations. (Hint: One direction to approach might be by contradiction. Assume there is a configuration where no three consecutive numbers sum to 16 or higher; e.g. The maximum any three consecutive numbers in this configuration could sum to would be 15. Hence the sum of all triples of consecutive numbers can't exceed a certain number. Then reach a contradiction by arguing that the sum of all triples of consecutive numbers must be larger than what is allowed.) Problem 7: (2 points) Prove the following: Suppose a and b are integers. If 3 | (ab) then 3 | a or 3 | b. (On a side note: This property is true for all prime numbers; i.e. if a prime number divides a product of integers, then it must divide at least one of them. But this is much harder to show than the specific case asked above.) Problem 8: (2 points) Recall that two statements are logically equivalent if they contain the same column configuration on a truth table. If two statements are equivalent we say they belong to the same equivalence class. There are an infinite number of statements which can be constructed using the variable p and logical connectives. For example: p p, p p, (p p) (p p), etc. However, it can be shown that all possible statements constructed with just one variable letter are all logically equivalent to one of four statements; i.e. there are only four equivalence classes for statements formed by one variable letter. For example: all statements formed from the single variable p and logical connectives are equivalent to one of the following statements: p, p, the contradiction p p, and the tautology p p. How many equivalence classes are there for statements formed with 5 letters; i.e. how many non-logically equivalent statements consist of 5 variable letters? Problem 9: (3 points) Suppose S is a set of 10 integers (any integers at all). Prove that there are a pair of numbers in S whose difference is a multiple of 9; i.e. Prove that there exists a, b S such that 9 | (a b). (Hint: Apply the Pigeonhole Principle to the potential remainders of elements of S with respect to division by 9)