practice_quiz0_solutions

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 21/39 For each question below, choose the correct answer from the provided list. Make sure to keep notes with your work, as you will be required to upload them at the end of this problem. Q1.1 2 Points Ariana has milk bones and she wants to give them to three of her dogs, with each getting one bone. In how many ways this can be done? EXPLANATION Choose first dog in ways, second in ways and third in ways, for the total of choices of three dogs. But since the ordering does not matter, you need to divide by (the number of permutations of the dogs that receive a bone), so the answer is . Alternatively, use the formula for -subsets of elements, . Q1.2 2 Points 3 6  120  20  6  27  10 none of the above  6 5 4 120 6 3 20 3 6 = ( 3 6 ) 20

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 22/39 Ariana also has other treats: Barkies, Poopsicles, and K9nies. She wants to distribute one piece of each among her dogs. There are no restrictions on which or how many treats each dog may receive. In how many ways this can be done? EXPLANATION Each treat can be assigned in ways, so the number of combined choices is . This is the number of functions from a -element set to a -element set. Q1.3 2 Points Bob wants to visit Lithuania, Latvia, Estonia, Ukraine, Poland and Slovakia during his visit to Europe. In how many orders he can visit these countries? EXPLANATION This is the number of permutations of elements, . Q1.4 2 Points 3 6  36  20  18  729  216 none of the above  6 6 ⋅ 6 ⋅ 6 = 216 3 6  360  36  6  720  120 none of the above  6 6! = 720

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 24/39 Give the numerical value of each expression. Make sure to keep notes with your work, as you will be required to upload them at the end of this problem. Q2.1 2 Points EXPLANATION Use the formula for the sum of the first integers, . This gives . Alternatively, you can use a formula for the sum of an arithmetic sequence: . Q2.2 2 Points 2 + 4 + 6 + ... + 30 =  60  96  480  120  160 none of the above  n n ( n + 1)/2 2 + 4 + 6 + ... + 30 = 2(1 + 2 + ... + 15) = 2 ⋅ 15 ⋅ 16/2 = 240 n ( a + 1 a )/2 = n 15 ⋅ (2 + 30)/2 = 240 3 = ∑ i =1 6 i

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 25/39 EXPLANATION Use the formula for the sum of a geometric sequence, . Then subtract , because our summation starts with index not , so the result is . It can also be calculated as follows: . Q2.3 2 Points EXPLANATION Q2.4 2 Points  2187  2186  1092  1093  729 none of the above  3 = ∑ i =0 6 i (3 − 7 1)/(3 − 1) = 1093 3 = 0 1 1 0 1092 3 = ∑ i =1 6 i 3 ⋅ 3 = ∑ i =0 5 i 3 ⋅ (3 − 6 1)/(3 − 1) = 3 ⋅ 364 = 1092 log 625 = 5 3  12  5  25  4  10 none of the above  log 625 = 5 3 3 ⋅ log 625 = 5 3 ⋅ 4 = 12. = ( 7 11 )

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 27/39 EXPLANATION The only candidates for integral roots are , and neither works. Alternatively, you can substitute , which gives equation . This equation does not have integer roots, and thus the original one doesn't either. Q3.2 2 Points EXPLANATION For all we have , because the polynomial does not have real roots (as its discriminant is negative) and the coefficient of is positive. Q3.3 2 Points EXPLANATION We have $x^2+1\ge 1$ and the exponent is never positive. Q3.4 True  False  1, 2, −1, −2 y = x 2 y − 2 y − 2 = 0 ∀ x ∈ R [ x + 2 10 > 6 x ] True  False  x ∈ R x − 2 6 x + 10 > 0 x − 2 6 x + 10 x 2 ∀ x ∈ R [ ( x + 2 1) ≤ − x 2 1 ] True  False  − x 2

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 28/39 2 Points EXPLANATION For any , choose , and then and the exponent is . Q3.5 Upload notes with your work (required). 0 Points No files uploaded Q4 Sets and Relations 8 Points Make sure to keep notes with your work, as you will be required to upload them at the end of this problem. Q4.1 2 Points Let , , , and . Which of the relations below are true? (There may be multiple true answers.) ∀ y ∈ R ∃ x ∈ R [ ( x + 2 y + 2 1) = x + y +1 1 ] True  False  y x = − y − 1 x + 2 y + 2 1 > 0 x + y + 1 0  A = { a , b } B = { a , b , c } C = { a , c , d } D = {{ a , b }, c }

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 30/39 EXPLANATION is reflexive because . It is symmetric because implies . It is not transitive. For example, and but . Therefore is not an equivalence relation. Q4.4 2 Points Let be the relation defined by the table below. In this table "1" represents "true" and "0" represents "false". Determine whether relation has the following properties: Reflexive  Symmetric  Transitive Equivalence Q ∣ x − x ∣ = 0 ≤ 1 ∣ x − y ∣ ≤ 1 ∣ y − x ∣ ≤ 1 1 Q 2 2 Q 3 ¬1 Q 3 Q R R

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 31/39 EXPLANATION It's reflexive because all entries on the diagonal are 1's. It is also symmetric, because its matrix (table) is symmetric with respect to the diagonal. The transitivity can be checked by exhausting all cases. (There aren't many cases. It is sufficient to check if only for and .) Another way to do this is to swap rows and columns . This shows that are mutually related but not related to , and are mutually related, but not related to . Therefore is an equivalence relation. Its equivalence classes are and . Q4.5 Upload notes with your work (required). 0 Points No files uploaded Q5 Number Theory 8 Points Make sure to keep notes with your work, as you will be required to upload them at the end of this problem. Reflexive  Symmetric  Transitive  Equivalence  xRy ∧ yRz ⇒ xRz x =  y y =  z 2, 3 2, 3 a , c b , d , e b , d , e a , c R { a , c } { b , d , e } 

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 33/39 Q5.3 2 Points Let and . Determine the value of . EXPLANATION The common prime powers in the factorizations of and are , , and . So Q5.4 2 Points Let be positive natural numbers. Determine whether the following statement is true or false: If and then . EXPLANATION To show that it's false, it's sufficient to give a counter-example. As one example, take , , and , . Then , but . Q5.5 Upload notes with your work (required). 0 Points No files uploaded a = 64 ⋅ 9 ⋅ 121 ⋅ 125 ⋅ 17 b = 4 ⋅ 243 ⋅ 11 ⋅ 5 ⋅ 169 gcd( a , b )  2970  1980  330  119  2310 none of the above  a b 2 = 2 4 3 = 2 9 5 = 1 5 11 = 1 11 gcd( a , b ) = 4 ⋅ 9 ⋅ 5 ⋅ 11 = 1980. a , b , c u ≥ x v ≥ y gcd( u , v ) ≥ gcd( x , y ) True  False  u = 3 v = 5 x = 2 y = 2 gcd( u , v ) = 1 gcd( x , y ) = 2 

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 34/39 Q6 12 Points Make sure to keep notes with your work, as you will be required to upload them at the end of this problem. Q6.1 3 Points Prove that equation has only one solution: and . Individual steps of a correct proof are given below, you only need to choose the correct ordering of these steps. Proof: (1) In the second case, when , rewrite this equation as . (2) Summarizing, we showed that in the first case the only solution is and , and in the second case there is no solution --- completing the proof. (3) We will consider two cases: when and when . (4) Since and , we obtain that , that is the equation does not have a solution in this case. (5) In the first case, for , this is a quadratic equation and its only root is . QED From the list below, select an ordering of these statements that will form a correct proof: x + 2 2 x + 1 + y = 2 0 x = −1 y = 0 y =  0 x + 2 2 x + 1 + y = 2 ( x + 1) + 2 y 2 x = −1 y = 0 y = 0 y =  0 ( x + 1) ≥ 2 0 y > 2 0 x + 2 2 x + 1 + y = 2 ( x + 1) + 2 y > 2 0 y = 0 x + 2 2 x + 1 = 0 x = −1

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 36/39 Choose a correct Phrase 3: Choose a correct Phrase 4: Choose a correct Phrase 4: Q6.3 3 Points equals  6 + 7 = 13 is at most  = ( 2 6 ) 15 is at least  7 is at most  6 ⋅ 7 = 42 is at least  6 is at most  5 ⋅ 7 = 35 is at most  = ( 2 7 ) 21 is at least  7 is at least  6 equals  5 + 7 = 12 cannot exceed  30 + 42 + 35 = 107 is at most  6 ⋅ 5 ⋅ 7 = 210 is at least  6 + 5 + 7 = 18 equals  10 + 15 + 21 = 46 is at most  11 + 13 + 12 = 36  110 < 210  107 < 110  110 > 37  37 > 36  210 > 107

4/7/22, 10:08 AM Edit Assignment | Gradescope https://www.gradescope.com/courses/381500/assignments/1954706/outline/edit 37/39 For integers , notation means that is a divisor of . (For example , but it is not true that .) denotes the set of natural numbers. (Recall that in this class we assume that ). Consider the following claim: Claim: . The inductive proof of this claim is given below, but in the inductive part the steps of the argument are out of order. Give a correct ordering of these steps. (The argument must be correct mathematically and grammatically as well.) Proof: We apply mathematical induction. In the base case, when , we have , and is a multiple of (because ), so the claim holds for . In the inductive step, let be some arbitrary positive integer and assume that the claim holds for , that is . We now proceed as follows. (1) This implies that is a multiple of , completing the inductive step. (2) . (3) From the inductive assumption, we have that , for some integer . (4) Next, we compute for the next value of , that is for : (5) This gives us that . We proved the base case, for , and that the claim holding for implies that it holds for . By the principle of induction, this proves the claim for all . QED Choose the correct ordering in the derivation above: Q6.4 3 Points x , y x ∣ y x y 5∣30 5∣21 N 0 ∈ N ∀ n ∈ N 3∣(2 − 2 n 1) n = 0 2 − 2 n 1 = 2 − 0 1 = 0 0 3 0 = 3 ⋅ 0 n = 0 k n = k 3∣(2 − 2 k 1) 2 − 2( k +1) 1 3 2 − 2( k +1) 1 = 2 − 2 k +2 1 = 4 ⋅ 2 − 2 k 1 = 4(3 c + 1) − 1 = 12 c + 3 = 3(4 c + 1) 2 − 2 k 1 = 3 c c 2 − 2 n 1 n n = k + 1 2 = 2 k 3 c + 1 n = 0 n = k n = k + 1 n 1-2-3-4-5  2-5-4-3-1  3-2-1-4-5  3-5-4-2-1 