CS 70 Discrete Mathematics for CS Spring 2004 Papadimitriou/Vazirani Review 1

Don’t worry if you haven’t seen all of the terms used in the following problems—many of these are taken from past semesters, and the coverage of topics among CS70 classes isn’t always the same. Also note that I haven’t read all of these in detail (much less worked through them), so there could be some errors.

1. Suppose you have n infinite, straight lines in the plane, no two of which are parallel and no three of which meet in a common point. Prove that the lines divide the plane into (n^{2}+ n + 2)/2 regions.

2. This problem is concerned with quantifiers (such as ∀). We didn’t cover these in much detail, so don’t worry if the concepts here seem foreign. That said, you may want to try this anyway.

(a) A binary operator f(x,y) is commutative if the result does not depend on the order of the arguments. State using quantifier notation the proposition that f is not commutative. (Matrix multiplication is an example of a noncommutative operator.)

(b) An identity for a binary operator is an element that, when combined with any element x, yields x itself. For example, the identity for + is 0; the identity for × is 1. For a noncommutative operator, a left-identity is an identity when it is the first argument; a right-identity is an identity when it is the second argument. State using quantifier notation the propositions that i_{L} is a left-identity for f and that i_{R} is a right-identity for f.

(c) Prove that for any i_{L} and i_{R} satisfying your definitions, it must be the case that i_{L}= i_{R}.

(d) Does your proof imply that f has exactly one identity element? If not, what have you proved?

3. Double induction

(a) Prove that k^{n} > n! for all positive integers k,n with n ≤ 2k.

(b) Prove that k^{n} < n! for all positive integers k,n with n ≥ 3k.

4. Prove that 1 · 1! + 2 · 2! + ··· + n · n! = (n + 1)! − 1 for all integers n ∈ N.

5. Strong induction

(a) Which amounts of postage can be formed from combinations of 3¢ and 11¢ stamps?

(b) Prove your claim using simple induction.

(c) Prove your claim using strong induction.

(d) Conjecture (and prove if possible) a general theorem concerning the amounts of postage that can be formed using stamps of values a and b.

6. Assign a grade of A (correct) or F (failure) to each of the following proofs. If you give a F, please explain exactly what is wrong with the structure or the reasoning in the proof. You should justify all your answers (remember, saying that the claim is false is not a justification).

(a) Theorem 0.1: For all positive integers n, ∑ _{i=1}^{n} i = (n − 1)(n + 2)/2. Proof: The proof will be by induction. Base case: The claim is valid for n = 1. Induction step: Assume that ∑ _{i=1}^{k} i = (k − 1)(k + 2)/2. Then ∑ _{i=1}^{k+1} i = (∑ _{i=1}^{k} i) + (k + 1). By the inductive hypothesis, ∑ _{i=1}^{k+1} i = (k − 1)(k + 2)/2 + (k + 1). Collecting terms and simplifying, the right-hand side becomes k(k + 3)/2. Thus ∑ _{i=1}^{k+1} i = ((k + 1) − 1)((k + 1) + 2)/2, which completes the induction step. □

(b) Theorem 0.2: For every n ∈ N, n^{2}+ n is odd.

Proof: The proof will be by induction. Base case: The natural number 1 is odd. Inductive step: Suppose k ∈ N and k^{2}+ k is odd. Then,

(k + 1)^{2}+ (k + 1) = k^{2}+ 2k + 1 + k + 1 = (k^{2}+ k) + (2k + 2)

is the sum of an odd and an even integer. Therefore, (k + 1)^{2}+ (k + 1) is odd. By the Principle of Mathematical Induction, the property that n^{2}+ n is odd is true for all natural numbers n. □

(c) Theorem 0.3: For all x,n ∈ N, if nx = 0 and n > 0, then x = 0. Proof: The proof will be by induction. Base case: If n = 1, then the equation nx = 0 implies x = 0, since nx = 1 · x = x in this case. Induction step: Fix k > 0, and assume that kx = 0 implies x = 0. Suppose that (k + 1)x = 0. Note that (k + 1)x = kx + x, hence we can conclude that kx + x = 0, or in other words, kx = −x. Now there are two cases: Case 1: x = 0. In this case, kx = −x = −0 = 0, so kx = 0. Consequently, the inductive hypoth-

esis tells us that x = 0. Case 2: x > 0. In this case, −x < 0 (since x > 0). At the same time, kx ≥ 0 (since k,x ≥ 0). But

this is impossible, since we know kx = −x. We have a contradiction, and therefore Case 2 cannot happen.

In either case, we can conclude that x = 0. This completes the proof of the induction step. □

(d) Theorem 0.4: For all x,y,n ∈ N, if max(x,y) = n, then x = y. Proof: The proof will be by induction. Base case: Suppose that n = 0. If max(x,y) = 0 and x,y ∈ N, then x = 0 and y = 0, hence x = y. Induction step: Assume that, whenever we have max(x,y) = k, then x = y must follow. Next suppose x,y are such that max(x,y) = k +1. Then it follows that max(x−1,y−1) = k, so by the inductive hypothesis, x − 1 = y − 1. In this case, we have x = y, completing the induction step. □

(e) Theorem 0.5: ∀n ∈ N. n^{2} ≤ n.

Proof: The proof will be by induction. Base case: When n = 0, the statement is 0^{2} ≤ 0 which is true. Induction step: Now suppose that k ∈ N, and k^{2} ≤ k. We need to show that

(k + 1)^{2} ≤ k + 1

Working backwards we see that:

(k + 1)^{2} ≤ k + 1
k^{2}+ 2k + 1 ≤ k + 1
k^{2}+ 2k ≤ k
k^{2} ≤ k

So we get back to our original hypothesis which is assumed to be true. Hence, for every n ∈ N we know that n^{2} ≤ n. □

7. Induction over strings

(a) Write a recursive definition of the length function l(s) on strings.

(b) Using induction over strings, prove that

∀x,y∈ Σ^{∗} l(x · y) = l(x) + l(y)

8. Let B_{n} be the number of bit strings of length n that do not contain 00 as a substring. (For example, A_{3} = 5, since the allowed bit-strings are 010, 011, 101, 110, and 111.) Let C_{n}= B_{n}/2^{n}, so C_{n}represents the fraction of bit strings of length n that do not contain 00. Prove that C_{n} gets arbitrarily close to zero as n increases. In other words: prove that, for every real number ϵ > 0, there exists n so that C_{n} ≤ ϵ.

9. Consider the following variation on the stable marriage problem: In Hawkinsville this year, we have n eligible boys and girls. Everyone knows the preferences of all the boys, but the girls have managed to keep their preferences totally secret. Tomorrow night, the girls will throw a secret meeting (no boys allowed!), privately share their (true) preferences, and collude to come up with a set of fake preferences that they will announce to the village elders. As a twist, each girl may declare some boys to be unacceptable (she’d rather be single than marry any of them). Next week, the village elders will run the traditional marriage algorithm on the boys’ (true) preferences along with the girls’ announced (and totally fake) preferences. The output of the traditional marriage algorithm will be used to marry off all the eligible youngsters in Hawkinsville.

Show that the girls can conspire to choose fake preferences so that when the wedding bells ring next week, we’ll end up with a girl-optimal pairing. (By “optimal,” I mean optimal with respect to everyone’s true preferences.)

10. Binary GCD

(a) Prove that the following statements are true for all m,n ∈ N.

If m is even and n is even, gcd(m,n) = 2gcd(m/2,n/2).
If m is even and n is odd, gcd(m,n) = gcd(m/2,n).
If m,n are both odd and m ≥ n, gcd(m,n) = gcd((m − n)/2,n).

(b) Give an algorithm that computes gcd(m,n) using at most O(lgm + lgn) subtractions, halvings, doublings, and odd/even tests.

11. The purpose of this problem is to teach you Big-O notation in a careful way. First, study the following. (If you’d like additional reading on this subject, you may refer to Rosen, Chapter 2.2.)

Formally: If f(n),g(n) are two non-negative functions of a single integer variable, the statement f(n) ∈ O(g(n)) means that

∃N_{0} ∈ N. ∃C ∈ N. ∀x ∈ N. x ≥ N_{0} ⟹ f(x) ≤ C · g(x).

In other words, O(g(n)) is the set of functions {f_{i}(n) : ∃N_{0} ∈ N. ∃C ∈ N. ∀x ∈ N. x ≥ N_{0} ⟹ f_{i}(x) ≤ C · g(x)}. This is the definition of Big-O notation.

Informally: f(n) ∈ O(g(n)) means, roughly, that f(n) grows “no faster than” g(n) (except possibly for a constant factor), as n gets large. For instance, n^{2} ∈ O(n^{2}), n(n+1)/2 ∈ O(n^{2}), and 10000n^{2} ∈ O(n^{2}), because these functions all grow at asymptotically the same rate (ignoring constant factors). Also, n^{2} ∈ O(n^{3}), because n^{2} grows more slowly than n^{3} does, as n gets large.

Some basic facts: If f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)), then f(n) ∈ O(h(n)). If f(n) ∈ O(g(n)) and f′(n) ∈ O(g′(n)), then f(n) + f′(n) ∈ O(g(n) + g′(n)). If f(n) ∈ O(g(n)) and f′(n) ∈ O(g′(n)), then f(n) × f′(n) ∈ O(g(n) × g′(n)).

Common notation: Instead of writing f(n) ∈ O(g(n)), almost everyone instead writes f(n) = O(g(n)). Strictly speaking, this is a sloppy abuse of notation, but this practice is widespread; you are guaranteed to see it throughout your studies of computer science, so be prepared. Also, we often write something like n^{2} as a shorthand for the function f(n) = n^{2}, just to make our life easier.

Now, with that background established, do the following problems:

(a) Prove that n^{2}+ 2003 ∈ O(n^{3}).

Hint: One possible approach is to give an example of constants N_{0},C that satisfy the definition.

(b) Prove that 100n^{2}lgn ∈ O(n^{3}).

(c) True or false: There exists e ∈ N such that 2^{n} ∈ O(n^{e}). (You do not need to justify your answer.)

(d) Critique the following argument. Is the reasoning valid? If not, why not?

We have n^{2} = O(n^{4}). Also, we have n^{2} = O(n^{3}). By transitivity, it follows that O(n^{4}) = O(n^{3}). This means that n^{4} = O(n^{3}).

12. Z_{N}^{∗} denotes the set X = {x : 0 < x < N and gcd(x,N) = 1}, together with the binary operation of multiplication modulo N. Show that Z_{N}^{∗} is a group.

The order of a group G = (X,·) is the cardinality (number of elements) of the set X. If N = PQ, where P and Q are distinct primes, what is the order of Z_{N}^{∗}?

13. Use the polynomial interpolation formula to find a polynomial of degree 2, P(x), over the finite field GF_{11}, such that P(1) = 3, P(2) = 1 and P(3) = 7.

14. Calculations

(a) What is 7^{1,000,000,000} mod101? Justify your answer.

(b) What is 2^{3^{1,000}} mod47? Show your work. (Note that a^{b^{c}} means a^{(b^{c})}, not (a^{b})^{c}.)