MyA67Final (1)

Graded FINAL EXAM Student Casper Sajewski-Lee Total Points 79 / 120 pts 

Question 1 EXAM INSTRUCTIONS 17 / 22 pts 1.1 STUDENT ID and DECLARATION 2 / 2 pts  + 2 pts Correct + 2 pts no student number or other info. + 0 pts no proof 1.2 Counting 4 / 4 pts  + 4 pts Correct + 0 pts Incorrect 1.3 (no title) 0 / 4 pts + 4 pts Correct  + 0 pts Incorrect 1.4 Pizza! 4 / 4 pts  + 4 pts Correct + 0 pts Incorrect 1.5 Triangles 4 / 4 pts  + 4 pts Correct. C(n, 3) = n(n-1)(n-2)/6 + 1 pt gives answer for n=8 or n=5 (56 or 10), or attempt but really not on track. + 0 pts wrong or missing + 2 pts on the right track + 3 pts small error

Question 4 Birthdays 5 / 5 pts  + 5 pts Correctly cites the generalized PHP and says prob is therefore 1. + 4 pts Final answer not mentioned + 2.5 pts makes a reasonable attempt to find the probability using counting arguments. + 2.5 pts NO justification + 0 pts wrong + 0 pts not submitted Question 5 Conditional Probability 4 / 4 pts  + 4 pts Correct + 0 pts Incorrect Question 6 Proof 0 / 10 pts + 10 pts Correct + 4 pts Recognizes its a PHP problem. + 3 pts Correctly creates holes as all the possible sums. + 1 pt Attempts to create sums or some other reasonable notion as holes. + 3 pts Correctly creates pigeons as all the possible sets. + 1 pt attempts to create a subset or other definition that is pigeons.  + 0 pts Submission not found or incorrect. Question 7 Predicate Logic 4 / 4 pts  + 4 pts Correct + 0 pts Incorrect Question 8 Equivalence? 0 / 4 pts + 4 pts Correct  + 0 pts Incorrect

Question 9 Combinatorial Argument 0 / 5 pts + 5 pts Correct + 1 pt gives a scenario for C(n,k) + 2 pts Gives a scenario or explanation for C(n-1, k) + 2 pts Gives a scenario of explanation for C(n-1,k-1). + 0 pts missing/no answer given  + 0 pts incorrect/not a combinatorial argument + 3 pts Gives scenario for each but does not properly explain how/why they connect/add up + 4 pts Correct but does not mention variables and + 2.5 pts Only writes what each term means but does not attempt to connect them together Question 10 Proof Primes 10 / 10 pts  + 10 pts Correct using direct proof. + 3 pts Notice that x-1, x, x+1 are consecutive + 3 pts if consecutive, and x-1 prime, then odd and so x is even and divisible by 2. + 3 pts if consecutive, one must be divisible by 3 and since neither x-1 or x-2 are, x must be + 1 pt x div by 2 and 3 means . + 10 pts correct by using indirect. check each possible case of for each ? possible. + 2 pts Sets up contradiction/contrapositive properly. + 1 pt Contradiction/contrapositive set up almost correct + 3 pts correctly does 1 case + 4 pts correctly does 2 remainder cases + 5 pts correctly does 3 remainder cases + 6 pts correctly does 4 remainder cases + 7 pts correctly does 5 remainder cases. + 2 pts Writes the claim in predicate logic correctly + 1 pt Claim almost correct in predicate logic + 0 pts No submission/Empty Answer or completely off (gives an example of x) n k 6 ∣ x x mod 6 =?

Question 13 Induction 7 / 10 pts + 10 pts Correct  + 2 pts Correctly states S(n) and the values for which we want to prove S(n) correct  + 2 pts Base Case correct. + 2 pts correctly states the induction hypotheses.  + 1 pt sets up I.S. properly + 1 pt correctly applies I.H for S(k).  + 2 pts finishes math to complete the proof. + 0 pts no answer + 0 pts incorrect Question 14 Strong Induction 6 / 10 pts + 10 pts Correct + 2 pts Correctly states S(n) and the values for which we want to prove S(n) correct + 1 pt correctly states the induction hypotheses.  + 2 pts Base Case correct - has two base cases. + 1 pt Only one correct base case  + 1 pt sets up I.S. properly + 2 pts correctly applies I.H stating that we require that n-2>= 2 and n-1>=2 for it to apply.  + 1 pt correctly applies I.H. but does not state why it applies  + 2 pts finishes math to complete the proof. + 0 pts Wrong or no answer

Q1 EXAM INSTRUCTIONS 22 Points ALLOWED AIDS: Calculator and one page double sided of notes. CAMERA: You must be on zoom for the duration of the exam and your camera must show as much as possible of your workspace including your writing space and face (if possible). For this whole exam, please follow the directions given for each question carefully. If you are writing a long answer solution in the boxes provided you may use $$math$$ to write mathematical symbols for example $$x^2$$ would be . NOTE: GRADESCOPE logs all clicks outside the exam webpage window. Make sure you only click between the zoom call and the exam webpage. Q1.1 STUDENT ID and DECLARATION 2 Points By entering your name and student ID here you are confirming that you are adhering to the University of Toronto's academic integrity rules. I, with name and student number below, attest that I am the person with said student number and that I have not visited any webpages/applications other than our zoom call and this exam, that I have not received any help from any other person or textbook during this exam and that my only aids are a calculator and one page double sided of notes. Name and Student number: Upload student id if you have. No files uploaded Casper Sajewski-Lee 1008493701 x 2 

Q1.5 Triangles 4 Points Consider a regular n-gon (an n sided polygon) for . For example, if n=8, we have an octagon. How many triangles can be formed by selecting corners of the n- gon. For example, for a 5-gon, two possible triangles are shown in orange and blue. You should assume each corner of the n-gon is distinguishable. State your answer. No work needed. C(n, 3) n ≥ 3

Q1.6 Triangles 4 Points Consider the n-gon and triangles from the previous question now with . Suppose you select 3 corners of the polygon at random. What is the probability that the triangle formed does not share any sides with the n-gon sides. For example, this red triangle does not share any sides in common with the octagon. Again you should assume the corners of the n-gon are distinguishable. Briefly explain your answer. State your answer and briefly show your work. C(n-4, 3)/C(n,3). There are C(n, 3) total ways to pick a triangle from the n-gon. To make a triangle with no shared sides to the n-gon, corners adjacent to a picked corner of the triangle may not be picked. For instance, if corner a is picked, corner h and b may not be picked. This happens twice, since the first corner has 2 corners that can't be picked and the second also has two corners which also may not be picked. n ≥ 4

Q2.2 Truth Values 4 Points Select all truth assignments of that make the following statement is true: p , q , r ( p → q ) → r p=T, q=T, r=T p=T, q=T, r=F p=T, q=F, r=T p=T, q=F, r=F p=F, q=T, r=T p=F, q=T, r=F p=F, q=F, r=T p=F, q=F, r=F

Q3 Integer Equations 8 Points Q3.1 Integer Equation (a) 4 Points How many integer solutions are there to the equation with . Leave your answer as a number without any spaces. Do not show your work. 6188 Q3.2 Integer Equation (b) 4 Points Read this question carefully. You'll notice it is slightly different than what we have seen before (highlighted in red). How many integer solutions are there to the equation with , , , , , and . Leave your answer as a number without any spaces. Do not show your work. 336 x + 1 x + 2 x + 3 x + 4 x + 5 x = 6 12 x ≥ i 0, i = 1,…,6 x − 1 x + 2 x + 3 x + 4 x + 5 x = 6 12 x ≥ 1 0 0 ≤ x ≤ 2 1 x ≥ 3 1 x ≥ 4 2 x ≥ 5 2 x ≥ 6 2

Q6 Proof 10 Points Consider a set where each and each is unique. Prove that there exists two subset of whose sums are equal. For example, if then two possible subsets are and . You may type your answer here or upload a handwritten answer. No files uploaded Q7 Predicate Logic 4 Points Select all statements which are equivalent to the following statement: S = { x , x , x , x , x , x } 1 2 3 4 5 6 1 ≤ x ≤ i 12 x i S S = {3,5,6,9,11,12} {3,5,12} {9,11}  ∀ n ∈ Z , n is even → 2 n is even All integers have even squares and are even. Given an integer whose square is even, that integer is itself even There does not exist an integer that is odd and has an even square. is even is necessary for to be even. n n 2 is even is sufficient for an is even. n n 2 All integers with even squares are even integers. All integers that are even have even squares.

Q8 Equivalence? 4 Points Select all options in which the pair of statements have the same truth value for all domains and predicate definitions. and ∀ x ∈ D ,( P ( x ) ∧ Q ( x )) (∀ x ∈ D , P ( x )) ∧ (∀ x ∈ D , Q ( x )) and ∃ x ∈ D ,( P ( x ) ∧ Q ( x )) (∃ x ∈ D , P ( x )) ∧ (∃ x ∈ D , Q ( x )) and ∀ x ∈ D ,( P ( x ) ∨ Q ( x )) (∀ x ∈ D , P ( x )) ∨ (∀ x ∈ D , Q ( x )) and ∃ x ∈ D ,( P ( x ) ∨ Q ( x )) (∃ x ∈ D , P ( x )) ∨ (∃ x ∈ D , Q ( x )) and ∀ x ∈ D ,( P ( x ) → Q ( x )) (∀ x ∈ D , P ( x )) → (∀ x ∈ D , Q ( x )) and ∃ x ∈ D ,( P ( x ) → Q ( x )) (∃ x ∈ D , P ( x )) → (∃ x ∈ D , Q ( x )) None of the above

Q10 Proof Primes 10 Points Consider a natural number such that and are both prime. Prove that is divisible by 6. Write the claim in predicate logic and prove the statement. You may use words and symbols such as " is prime" and " ". Put your answer in the box or upload a handwritten file. x > 5 x − 1 x + 1 x x − 1 6 ∣ x

IMG_20211211_101400233.jpg  Download 