CS 70 Discrete Mathematics and Probability Theory
Spring 2019 Ayazifar and Rao Midterm 1 Solutions
PRINT Your Name: Oski Bear SIGN Your Name: OS K I
Do not turn this page until your instructor tells you to do so.
CS 70, Spring 2019, Midterm 1 Solutions 1
SID:
1. TRUE or FALSE?: 2pts each
For each of the questions below, answer TRUE or FALSE. No need to justify answer.
Please fill in the appropriate bubble!
Answer: Note that the answers provide explanations for your understanding, even though no such justifica- tion was required
1. (¬P∨Q)∨¬(P =⇒ Q) is true for all P and Q.
Solution: True. This is a tautology and is true because the implication P =⇒ Q is true or not and
P ∨ ¬P is always true.
2. ∃n∈N,∀y∈Z,n>y.
Solution: False. It says there is a natural number which is larger than every number in Z.
3. ¬(∀n∈N,P(n)) =⇒ ∃n∈N,¬P(n).
Solution: True. There must exist a counterexample.
4. (¬A =⇒ ¬B)≡(A =⇒ B).
Solution: False. This is the converse not the contrapositive.
5. For n > 2, there is a stable marriage instance of n men and n women in which the traditional marriage algorithm takes at least n2 days.
Answer: False. If this were true, then there must have been at least n2 − 1 > n(n − 1) rejections. Therefore, by Pigeonhole, somebody got rejected n times, which is impossible.
We can get a tighter bound in the following way. Recall that there always exists a woman W who is not proposed to until the very last day. Furthermore, there can only be one man M who can propose to her on the last day, otherwise W will need to reject somebody and the algorithm continues. Thus, n−1 of the men don’t propose to W, so they face at most n−2 rejections. M faces at most n−1 rejections. This gives us a (tight) bound of (n − 1)(n − 2) + (n − 1) = (n − 1)2 rejections, which means the duration is at most (n − 1)2 + 1 days.
6. If a stable pairing P has a pair (m, w) where P is optimal for both m and w, then every stable pairing is optimal for both m and w.
Answer: True. They would be a rogue couple in any supposed stable pairing where they are not paired, thus they would always be together in every stable pairing. Thus, every stable pairing would be optimal for both of them.
7. If at any point in the traditional marriage algorithm a woman’s optimal partner proposes to her, then every stable pairing is optimal for her.
Answer: True. It only gets better for women, so she must end up with her optimal partner. This suggests that in any other stable pairing, either this couple is rogue or this pairing is not optimal for both her and her partner, which it is. Thus, there are no pairings where they are not paired.
8. There is an n-edge, n-vertex connected graph where each pair of vertices is connected by 2 disjoint paths. (Paths are disjoint if they do not share an edge.)
Solution: True. Consider the cycle on n vertices.
9. Consider a function f :A→B, where |A|=|B|. An inverse function for f is a function g:B→A
where ∀x ∈ A, (g( f (x)) = x ∧ f (g(x)) = x). f (·) is a bijection if there is an inverse function.
Solution: True. The existence of the inverse suggests it is one-to-one and the fact that |A| = |B| suggests it is onto.
2
SID:
10. 11. 12.
f(x) = ax (mod m) is a bijection if and only if m is prime.
Answer: False. It just needs gcd(a,m) = 1
Any graph that is a simple cycle can be vertex colored with 2 colors. Answer: False. Consider K3.
For a hypercube of dimension 3, there is an edge between vertex 000 and 111. Answer: False. Edges are only between vertices that differ in one bit.
2. Short Answer. 3 pts each.
Write your answer in the simplest form possible. You should use only the variables in the question unless otherwise specified.
1. Write a logical formula that describes the proposition: the square of any natural number is a natural number.
Answer: ∀n ∈ N,∃m ∈ N,n2 = m
2. What is the number of edges in an n-vertex acyclic graph having k connected components?
Answer: n − k. Starting from n components, each edge addition either creates a cycle or reduces the number of components by 1. Thus, to get to k components, one can and has to add n − k edges.
3. What is the number of edges in a planar graph where every face has five sides? (Answer in terms of v, the number of vertices.)
Answer: 5(v − 2)/3. Eulers v + f = e + 2. 5 f = 2e by counting edge face adjacencies. This implies v + 2e/5 = e + 2, which implies e = 5(v − 2)/3. Notice this puts conditions on the values of v for which this can hold.
4. Iftherearen/2leavesinann-vertextree,whatistheaveragedegreeoftheothern/2vertices?(Assume n is even.)
Answer: Total degree is 2(n − 1). The degree of those vertices is n/2, so remaining total degree is 2n − n/2 − 2, the average degree of the remaining n/2 vertices is thus 3 − 4/n.
5. For a hypercube of dimension 4, how many edges (u, v) are there where u has a leading 0 and v has a leading 1?
Answer: 8. The number of vertices in each cube is 8 and each has a mate in the other subcube.
6. What is the longest simple cycle in a d-dimensional hypercube, for d > 1?
Answer: 2d . They have a Hamiltonian cycle as proved in discussion.
7. For positive x,y, 2x = 1 (mod n) and 2y = 1 (mod n) what is 2gcd(x,y) (mod n)?
Answer: 1. There is r,s where gcd(x,y) = rx+sy. Thus, we have agcd(x,y) = arx+sy = (ax)r(ay)s = (1)r(1)s = 1 (mod n)
8. If x−y < x/2, then y > . (The answer should be in terms of x.)
Answer: x/2. This is just algebra but happens to be part of the proof that the gcd algorithm’s first argument decreases by a factor of two every other iteration.
9. The least common multiple of two positive numbers m and n is the smallest positive number that is a
multiple of both. What is the least common multiple of m and n in terms of m, n and d = gcd(m,n)?
Answer: nm . There has to be all the factors of n and m, but multiplying them together gives the factors d
in d twice. We can remove them by dividing.
10. What is the maximum number of solutions in {0,1,…,n − 1} to the equation ax = b (mod n) if gcd(n,a) = d? (Answer in terms of n and d.)
Answer: d. If b is a multiple of d, then answer is d, otherwise there are no solutions.
3
SID:
11. Whatisthesizeoftherangeofthefunction f(x)=ax (mod n)wherex∈{0,1,…,n−1}ifgcd(n,a)= d?
Answer: n/d. The multiples of d is the range of this function.
12. For a prime p, how many numbers in {0,1,…,p2 −1} have an inverse modulo p2? (Answer in terms of p.)
Answer: p( p − 1). The number of values in that range that are relatively prime to p
13. Givenxandmwithgcd(x,m)=d,andd=ax+bm,whatisavalueofzwherezx=5d (modm)?(In terms of some subset of the variables x,m,a,d and b.)
Answer: 5a. ax = ax+bm = d (mod m) and then multiply by 5.
14. What is 275 (mod 73)?
Answer: 8 (mod 73). 272 = 1 (mod 73) makes it simple.
15. Let p > 2 be prime. What is 2k(p−1) (mod p)? Answer: 1. A quick test of exponents and FLT.
16. Find x (mod 20) that satisfies the equations: x = 2 (mod 4) and x = 4 (mod 5)? Solution:14.2(5)(5−1 (mod4))+4(3)(3−1)(mod5))=14(mod20)
17. If gcd(m,n) = 1, let x = a+km, what should k be to satisfy x = b (mod n)? Answer: m−1(b − a) (mod n). For a + km = b (mod n), and solve.
18. What are the last two digits of 4919? (Hint: gcd(4,25) = 1 and 24 = −1 (mod 25).)
Answer: 49. 4919 = (1)19 = 1 (mod 4) and (49)19 = (−1)19 = −1 (mod 25). That is raising to the 19th power didn’t change the modulus in either case. Thus, the value (mod 100) doesn’t change either and we have that the result is 49. If one didn’t notice that this is a fixed point, reconstructing using the CRT will work.
19. A fixed point of a function is a value x where f (x) = x. Consider the function f (x) = x3 (mod mn) forrelativelyprimem>2andn>2. Notethatx=−1,x=0,andx=1arefixedpointsforx3. Find another fixed point of f (·). (Your answer can include m, n and their inverses.)
Answer: n(n−1 (modm))−m(m−1 (modn)).Afixedpointforx3arex=1orx=−1.Thatisalso true (modm)and (modn)aswell. So,takex=1 (modm)andx=−1 (modn). Thus,wehave n(n−1 (mod m))−m(m−1 (mod n)).
3. Short Proofs. 5 pts each.
1. Provethatifd̸| n2 thend̸| n.(d̸| nmeansnisnotamultipleofd.)
Solution: By contraposition: d|n =⇒ d|n2.
d|n means there is an integer k where n = kd, we then have n2 = k2d2 = (k2d)d which implies d|n2 since k2d is an integer.
2. Prove by induction that (1−x)n ≥ 1−nx for any natural number n ≥ 1 and 0 < x < 1.
Solution: BaseCase:(1−x)1=(1−x)≥(1−(1)x).
Induction Step: (1−x)n = (1−x)n−1(1−x) ≥ (1−(n−1)x)(1−x) = (1−nx+(n−1)x2) ≥ (1−nx). We used the induction hypothesis in the first inequality, and the fact that (n − 1)x2 is positive for n ≥ 2.
3. Prove that x2 = 7 has no rational solutions. Solution:
4
SID:
Let a/b be a solution in reduced form to this equation and plug in to get a2
b =7.
Or we have a2 = 7b2, which indicates that 7 is a factor of a2, and thus of a since 7 is not a perfect square. But since 7 is not a perfect square, we have that b2 must also be a multiple of 7. This contradicts the notion that a/b was in reduced form.
4. Sleepiness.
1. (5 pts) Consider a set of intervals [s1,e1],...,[sn,en] where si is the start time and ei is the end time of an interval. The associated interval graph has a vertex for each interval and an edge between any pair of intervals that overlap; for example, if i1 = [3, 5] and i2 = [4, 6] and i3 = [6, 7], there are edges (i1 , i2 ), and (i2,i3) but no edge between i1 and i3.
Prove that if there is a cycle in an interval graph then there is a point in time where at least 3 intervals overlap.
Solution: Suppose for contradiction that within the cycle, n1 , . . . , nk , there does not exist three intervals that overlap. Let n1 be the nap with the smallest start time. Since n3 is connected to n2, we cannot have n3 overlap with n1, so n3’s start time must happen after n1’s end time. But then n4’s start time must occur after n3’s start time, so the start times of the nodes will strictly increase. This is a contradiction, since the last nap, nk, in the cycle must overlap with n1.
2. (3 pts) Argue that for a graph G = (V,E), if |E| ≥ |V|, then G has a cycle.
Solution: Ifthegraphisconnected,itcannotbeacyclicasithasmorethan|V|−1edgesandisnota tree. If it is disconnected, by the pigeonhole principle at least of the connected components has at least as many edges as vertices and we can apply the previous argument to that component.
3. (4 pts) Seven students each fall asleep three times during CS 70 lecture. Furthermore, for every two of these seven students, there exists a time when both of them are sleeping. Prove that there must be some time when at least three students were sleeping at once.
Solution: Give each student three vertices, representing each of the times they fell asleep. Draw an edge between two vertices if the respective naps overlap. There are 7 · 3 = 21 vertices and 7·6 = 21
2 edges. Therefore, this graph must have a cycle. By part (a), there must be three naps that overlap.
5. Colorings.
Define exploding a graph G as making a copy of it called G′, and then adding an edge between each vertex v ∈ G and its copy v′ ∈ G′. Note that exploding a graph doubles the number of vertices. So, exploding an (n − 1)-dimensional hypercube gets us an n-dimensional hypercube.
Jonathan has a graph G and wants to destroy all edges. At each step, he can choose to perform one of the following operations:
• Remove an odd-degree vertex and all its incident edges. • Explode the graph.
Prove to Jonathan that no matter what graph G he starts with, he can get rid of all edges in a finite number of operations.
To help you out, we will break this down into parts. Define f (G) as the smallest number of colors needed to vertex-color G.
5
SID:
1. (4 pts) Prove that exploding a graph where f (G) > 1 does not increase f (G).
2. (4 pts) Suppose every vertex in G has even degree, and let Gboom be its exploded graph. Given a coloring of Gboom, prove that you can remove all vertices of a particular color in Gboom. (Potentially in multiple steps.)
3. (2 pts) Prove that if f (G) = 1, then Jonathan is done.
4. (4 pts) Now finish the proof: prove that there exists a finite sequence of operations for Jonathan to
destroy all edges. (You may use results from previous parts.)
Solution:
1. Color G with f(G) colors, and denote the colors 0,1,2,3,…, f(G)−1. Color G′ the same way, but replace color i with i + 1 (mod f (G)). All edges within G and G′ do not invalidate the coloring, and edges between also do not since i ̸= i+1 (mod f(G)) if f(G) > 1.
2. After exploding G, we have a graph where every vertex has odd degree. Take color 0, and remove all vertices of that color one at a time. The removal of a 0-colored vertex does not decrease the degree of any other 0-colored vertex, because they cannot be connected by an edge, else they cannot both be colored 0.
3. Suppose Jonathan is not done. Then, there must still be an edge (u, v). But u and v must have different colors, so f (G) > 1. By contraposition, we have proven the statement.
4. Thealgorithmistofirstremoveodddegreeverticesoneatatimeuntileithernoedgesremain,inwhich case we are done, or until all vertices have even degree.
Then, we explode the graph and apply our procedure from part (b) to decrease the f (G) by 1. Thus, within a finite number of operations, we can always decrease f (G) by 1, until f (G) = 1. By part (c), we have reached our goal.
6. Chicken Nuggets.
In this problem, we explore the conundrum that Jonathan and Emaan face when they visit McDonald’s. The chicken nuggets are sold in boxes of two different quantities, and they’re interested in which quantities of chicken nuggets can be bought.
1. (3 pts) Find (x, y) that satisfy the equation 7x + 11y = 53, where x and y have to be non-negative integers, and y is as small as it can be. Hint: try taking mods of both sides to eliminate a variable first Solution: Take (mod 7) of both sides to get 4y ≡ 4 (mod 7). Multiplying both sides by 2 gives
us y ≡ 1 (mod 7). Therefore, the smallest y that works is y = 1. Plugging that in yields x = 6, so (x,y)=(6,1).
2. (3pts)Explainwhy7x+11y=59hasnonon-negativeintegersolutionsfor(x,y).
Solution: Again, take (mod 7) of both sides to get 4y ≡ 3 (mod 7). Multiplying both sides by
4−1 ≡ 2 (mod 7) gives us y ≡ 6 (mod 7). Therefore, the smallest that y can be is 6. However, this
means x must be at most 59−6·11 = −1, which is a contradiction. 7
3. Consider a store where chicken nuggets are sold in boxes of m and n with gcd(m, n) = 1. Buying x boxes of m chicken nuggets and y boxes of n chicken nuggets yields xm + yn chicken nuggets.
(a) (2 pts) For any solution to xm+yn = mn−m−n, what is x (mod n)? Solution: −1 or n − 1.
6
SID:
(b) (4 pts) Argue that there is no solution for xm+yn = mn−m−n where x and y are both non- negative integers.
Solution: If k = mn−m−n = xm+yn, we see that x = −1 (mod n). The minimim value of this is n−1. Now the expression (n−1)m+yn = mn−m+ny. This is greater than mn−m−n for any non-negative y.
4. The following two parts will prove that mn − m − n is the largest number of chicken nuggets that cannot be bought.
(a) (3 pts) Prove that for any integer z, there is a solution to xm+yn = z where 0 ≤ x ≤ n−1.
Solution: By extended Euclid, there is x′,y′ such that x′m+y′n = 1. Therefore, taking (x,y) = (zx′ , zy′ ), we get xm + yn = z, which guarantees us the existence of an integer solution. Now, take (mod n) on both sides of the equation.
Now x = m−1z (mod n), and x = m−1z (mod n) has a representative in {0,…,n−1}. Thus,wehavexm=z (mod n)orz=xm+knforsomevalueofk. Thatis,takey=k. Alternative: One can notice that when x is positive (which is without loss of generality), one can subtract n from x and add m to y and xm+yn does not change. Thus, one can do this until x is in the right range.
(b) (3 pts) Argue that for any z > mn−m−n, there is a solution to xm+yn = z where x and y are non-negative.
Solution: Again,byextendedEuclidthereisz=xm+ynwherepossiblyoneofxpositiveandy is negative. (W.l.o.g.)
As per above we can assume x ≤ n−1.
We have xm ≤ (n−1)m = mn−m, and notice for y < 0, we have xm+yn ≤ mn−m−n. Thus, for z > mn−m−n, y is not negative.
7