\fCPSC 121: Models of Computation Assignment #4, due Wednesday, November 18th , 2015 at 17:00 Each of the following questions asks you to prove a theorem. When the theorem is stated in English, it would be an excellent idea to rst rewrite it in predicate logic, and then think about the proof techniques we discussed in class, and the general \"structure\" of direct proofs for certain types of statements. [8] 1. Prove that if n is a positive integer, then n2 + 5 is not divisible by 4. Hint: divide the proof into two cases. [8] 2. Prove that for every integer n, the product n(n2 1)(n + 2) is divisible by 4. [8] 3. Prove that for every real number c we pick, there will be some positive integer n such that 4n > c3n . Hint: the inside back cover of your textbook contains a list of properties of exponents and logarithms. A web search for \"logarithm reference\" will also turn up many alternative resources. [8] 4. Mr. Isulo, the alien computer scientist, has written an excellent algorithm whose execution requires 2n3 + 4n2 + 5 steps, where n is the size of the list the algorithm is given as its input. Prove that the number of steps of the algorithm is in O(n3 ). Recall that f 2 O(g) if 9n0 2 N 9c 2 R+ 8n 2 N, n n0 ! f (n) cg(n). [8] 5. Prove that for every three non-zero integers a, b and c, at least one of the three products ab, ac, bc is positive. Hint: use a proof by contradiction. p p [8] 6. Using an indirect proof, show that 3 + 5 is irrational. Recall that an irrational number is one that can not be written in the form a/b where a is an integer, and b is a positive integer. You may assume the following theorem has already been proved: p p If x is a positive integer, and x is not an integer, then x is irrational. The remaining questions are for additional practice only. You should not hand them in. Solutions will be posted at the same time as the solutions to the rst six questions. 1. For every non-negative integer x, bx/2c + dx/2e = x. Additional information: You will nd the denitions of the oor and ceiling functions in your textbook. In Epp's fourth edition, the oor and ceiling functions are dened on page 191. In Epp's third edition, they are dened on page 165. These functions are dened on pages 149 (143) in Rosen's seventh (sixth) edition. You should break the proof down into two cases. 2. Given an arbitrary positive integer n, we can nd n consecutive positive integers that are all composite. Additional information: a number is composite if it is greater than 1, and is not prime. Hint: use a trick similar to one we used in class. 3. For any three functions f , g and h, prove that if f 2 O(g) and g 2 O(h), then f 2 O(h). Additional information: if you assume that a statement such as 9x 2 D, P (x) is true, then you can choose the specic value of x (call it x0 ) for which P (x0 ) holds. You don't have to know what x0 is, as long as you know that such a value exists (you can only call it \"x0 \"; you can not give it an actual value). 4. Suppose that you are given a group of n children, and that you want to divide them into two soccer teams. Unfortunately, there are pairs of children that do not like each other, and you need to make sure that two children who do not like one another do not end up on the same team. Prove that, if you can achieve this, then for every group of k children c1 , . . . , ck where c1 does not like c2 , c2 does not like c3 , . . . , ck 1 does not like ck , and ck does not like c1 , then k must be even. Hint: use an indirect proof. 5. Can you draw a quadrilateral (4-sided gure) in which the sum of any two angles - no matter which two you pick - is less than 180 ? Explain how to do it, or prove that it can not be done. Hints: (1) the sum of the angles in a quadrilateral is always 360 . (2) use a proof by contradiction. CPSC 121: Models of Computation Assignment #4, due Wednesday, November 18th , 2015 at 17:00 Each of the following questions asks you to prove a theorem. When the theorem is stated in English, it would be an excellent idea to rst rewrite it in predicate logic, and then think about the proof techniques we discussed in class, and the general \"structure\" of direct proofs for certain types of statements. [8] 1. Prove that if n is a positive integer, then n2 + 5 is not divisible by 4. Hint: divide the proof into two cases. [8] 2. Prove that for every integer n, the product n(n2 1)(n + 2) is divisible by 4. [8] 3. Prove that for every real number c we pick, there will be some positive integer n such that 4n > c3n . Hint: the inside back cover of your textbook contains a list of properties of exponents and logarithms. A web search for \"logarithm reference\" will also turn up many alternative resources. [8] 4. Mr. Isulo, the alien computer scientist, has written an excellent algorithm whose execution requires 2n3 + 4n2 + 5 steps, where n is the size of the list the algorithm is given as its input. Prove that the number of steps of the algorithm is in O(n3 ). Recall that f 2 O(g) if 9n0 2 N 9c 2 R+ 8n 2 N, n n0 ! f (n) cg(n). [8] 5. Prove that for every three non-zero integers a, b and c, at least one of the three products ab, ac, bc is positive. Hint: use a proof by contradiction. p p [8] 6. Using an indirect proof, show that 3 + 5 is irrational. Recall that an irrational number is one that can not be written in the form a/b where a is an integer, and b is a positive integer. You may assume the following theorem has already been proved: p p If x is a positive integer, and x is not an integer, then x is irrational. The remaining questions are for additional practice only. You should not hand them in. Solutions will be posted at the same time as the solutions to the rst six questions. 1. For every non-negative integer x, bx/2c + dx/2e = x. Additional information: You will nd the denitions of the oor and ceiling functions in your textbook. In Epp's fourth edition, the oor and ceiling functions are dened on page 191. In Epp's third edition, they are dened on page 165. These functions are dened on pages 149 (143) in Rosen's seventh (sixth) edition. You should break the proof down into two cases. 2. Given an arbitrary positive integer n, we can nd n consecutive positive integers that are all composite. Additional information: a number is composite if it is greater than 1, and is not prime. Hint: use a trick similar to one we used in class. 3. For any three functions f , g and h, prove that if f 2 O(g) and g 2 O(h), then f 2 O(h). Additional information: if you assume that a statement such as 9x 2 D, P (x) is true, then you can choose the specic value of x (call it x0 ) for which P (x0 ) holds. You don't have to know what x0 is, as long as you know that such a value exists (you can only call it \"x0 \"; you can not give it an actual value). 4. Suppose that you are given a group of n children, and that you want to divide them into two soccer teams. Unfortunately, there are pairs of children that do not like each other, and you need to make sure that two children who do not like one another do not end up on the same team. Prove that, if you can achieve this, then for every group of k children c1 , . . . , ck where c1 does not like c2 , c2 does not like c3 , . . . , ck 1 does not like ck , and ck does not like c1 , then k must be even. Hint: use an indirect proof. 5. Can you draw a quadrilateral (4-sided gure) in which the sum of any two angles - no matter which two you pick - is less than 180 ? Explain how to do it, or prove that it can not be done. Hints: (1) the sum of the angles in a quadrilateral is always 360 . (2) use a proof by contradiction