Understanding Math Concepts: Tips and Solutions for 22F-MATH-61

22F-MATH-61-LEC-2 Final ARTYOM SAPA TOTAL POINTS 96 / 120 QUESTION 1 1 Problem 1 5 / 10 + 10 pts Correct + 6 pts knowing equivalence Euler connected and even degree or applying full definition of invariance + 2 pts proof connected + 2 pts proof even degree + 1 pts partial credit for having an idea to proof invariance but still not a formal proof ✓ + 5 pts partial credit: the idea is correct but does not answer the question. You should prove that it is invariant not only cite results. + 0 pts Incorrect + 3 pts Major partial credit with minor mistake or partial credit for knowing all definitions QUESTION 2 2 Problem 2.1 10 / 10 ✓ + 10 pts Correct + 1 pts definition + 3 pts proof reflexivity + 3 pts proof transitivity + 3 pts proof symmetry + 0 pts incorrect QUESTION 3 3 Problem 2.2 5 / 5 ✓ + 5 pts Correct + 4 pts applying pingeonnhole principle + 1 pts explaining why difference is n divisible + 0 pts incorrect + 2 pts partial credit: general ideal but not formalized properly QUESTION 4 4 Problem 3 1 / 10 + 2 pts Correct definition of simple path (=no repeated vertices) + 2 pts For formula $$\frac{n!}{(n-k-1)!}$$ if $$k < n$$. + 2 pts For noticing that there are $$0$$ simple paths if $$k\geq n$$. + 4 pts Correct justification + 2 pts Partial justification ✓ + 2 pts For solving an incorrect problem (wrong definition of a simple path or a different similarly difficult and related problem) correctly + 0 pts No substantial progress - 1 Point adjustment The two paths in your example are actually different, since the orientation of paths is important, QUESTION 5 5 Problem 4 20 / 20

✓ + 20 pts Clear, rigorous and correct solution + 16 pts Rigorous solution with small mistakes or one that is unclear. Forgotten inductive hypothesis + 10 pts Any proof that does induction so that it starts with a specific tree of order $$n-1$$ and adds a vertex. + 5 pts Hand-wavy argument that contains the correct heuristics, but is not a mathematical proof + 2 pts Only inductive hypothesis (case $$n=1$$), but point will be given also if $$n=2$$ is done instead + 1 pts A useful observation + 0 pts No significant progress - 1 pts Not enough details. - 2 pts Not enough details. - 3 pts Existence of a leaf is not justified. QUESTION 6 6 Problem 5.1 10 / 10 ✓ - 0 pts Correct - 2 pts "There are $$C(8,3)$$ possibilities for how many yellow, red, and green balls a student could draw." Note $$C(8,3)$$ should be changed to $$C(8,2)$$ to make this sentence correct. - 3 pts The number of possibilities for how many yellow, red, and green balls a student could draw is $$|\{Y,R,G\in\mathbb{Z}_{\geq0}:Y+R+G=6\}|$$, but no further progress is made in calculating this number - 4 pts "There are $$C(6,3)$$ possibilities for how many yellow, red, and green balls a student could draw." Note $$C(6,3)$$ should be changed to $$C(8,2)$$ to make this sentence correct. - 5 pts "There are $$3^6$$ possibilities for how many yellow, red, and green balls a student could draw." Note $$3^6$$ should be changed to $$C(8,2)$$ to make this sentence correct. - 5 pts "There are $$25$$ possibilities for how many yellow, red, and green balls a student could draw." Note $$25$$ should be changed to $$C(8,2)$$ to make this sentence correct. - 5 pts "There are $$6\cdot3$$ possibilities for how many yellow, red, and green balls a student could draw." Note $$6\cdot3$$ should be changed to $$C(8,2)$$ to make this sentence correct. - 5 pts No progress correctly counting the possibilities for how many yellow, red, and green balls a student could draw - 1 pts "$$7\leq200/28$$ so there must be at least $$8$$ students with the same number of yellow, red, and green balls." Note $$\leq$$ should be changed to $$<$$ to make this sentence correct. - 1 pts The equation $$\lceil200/28\rceil=8$$ appears with the brackets misplaced (for example, $$\lceil200\rceil/28=8$$) - 2 pts "$$200/28=8$$". Note this should be changed to "$$\lceil200/28\rceil=8$$". - 2 pts Mentions that when $$n$$ pigeons inhabit $$k$$ holes, there must be at least $$n/k$$ pigeons sharing a hole, but doesn't mention the stronger fact that there must be at least $$\lceil n/k\rceil$$ pigeons sharing a hole - 3 pts "$$\lceil28\rceil/200=8$$." Note this should be changed to "$$\lceil200/28\rceil=8$$"

- 3 pts The fraction $$200/k$$ appears, where $$k$$ is the calculated number of possible combinations of yellow, red, and green balls, but it's unclear how the value of this fraction implies the existence of at least $$8$$ students who drew the same number of yellow, red, and green balls - 4 pts The words "pigeonhole principle" appear, but no correct explanation of the pigeonhole principle or its application here is given - 5 pts No attempt at applying pigeonhole principle - 10 pts Blank or incorrect QUESTION 7 7 Problem 5.2 5 / 10 - 0 pts Correct answer: $$3^6+1$$ - 3 pts "There are $$6^3$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$6^3$$ should be changed to $$3^6$$ to make this sentence correct. - 4 pts "There are $$P(6,3)$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$P(6,3)$$ should be changed to $$3^6$$ to make this sentence correct. - 5 pts "There are $$C(8,2)$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$C(8,2)$$ should be changed to $$3^6$$ to make this sentence correct. ✓ - 5 pts "There are $$6!$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$6!$$ should be changed to $$3^6$$ to make this sentence correct. - 5 pts "There are $$C(6,3)$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$C(6,3)$$ should be changed to $$3^6$$ to make this sentence correct. - 5 pts "There are $$6\cdot3$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$6\cdot3$$ should be changed to $$3^6$$ to make this sentence correct. - 5 pts "There are $$C(8,5)$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$C(8,5)$$ should be changed to $$3^6$$ to make this sentence correct. - 5 pts "There are $$C(31,6)$$ strings of length $$6$$ in the alphabet $$\{A,B,C\}$$". Note $$C(31,6)$$ should be changed to $$3^6$$ to make this sentence correct. - 3 pts "When placing pigeons into $$n$$ holes, we need at least $$2n$$ pigeons to be sure there are at least two pigeons sharing a hole". Note $$2n$$ should be changed to $$n+1$$ to make this sentence correct. - 4 pts "When placing pigeons into $$n$$ holes, we need at least $$2n+1$$ pigeons to be sure there are at least two pigeons sharing a hole". Note $$2n+1$$ should be changed to $$n+1$$ to make this sentence correct. - 4 pts "When placing pigeons into $$n$$ holes, we need at least $$2n-1$$ pigeons to be sure there are at least two pigeons sharing a hole". Note $$2n-1$$ should be changed to $$n+1$$ to make this sentence correct. - 4 pts "When placing pigeons into $$n$$ holes, we need at least $$n+2$$ pigeons to be sure there are at least two pigeons sharing a hole". Note $$n+2$$ should be changed to $$n+1$$ to make this sentence correct.

Your preview ends here