Massachusetts Institute of Technology Handout ??? 6.042J/18.062J: Mathematics for Computer Science April 19 2000 Professors David Karger and Nancy Lynch

Quiz 2 Solutions

Problem 1 [10 points] Pigeonhole Principle

Source: Fall 99 tut 7

In a city with more then one road, prove that there must be at least two roads which are crossed by the same number of other roads.

Solution. A straightforward application of the pigeonhole principle. Say that there are n roads in this city. Since no road can cross itself, the number of roads which cross any given road must be an integer from 0 to n − 1. If no two roads had the same number of crossings, then every one of these n numbers from 0 to n − 1 must equal the number of times some road is crossed. But that would mean that some road crosses 0, i.e. no roads, while some road crosses n − 1, i.e. all the other roads. This is a contradiction.

Handout ???: Quiz 2 Solutions  2  Name:

Problem 2 [10 points] Pigeonhole Principle

Source: Fall 98 rec 7

Suppose n > 1 and we place checkers on exactly n + 1 squares of the n × n checkerboard. Show that some length occurs more than once as the distance between two different checkered squares. (More precisely, there are checkered squares S1 ≠ S2 and S3 ≠ S4 such that the distance between S1 and S2 is the same as the distance between S3 and S4, but {S1, S2} ≠ {S3, S4}.)

Solution. The distance between checkers at distinct positions (x_{1}, y_{1}) and (x_{2}, y_{2}) is uniquely determined by the set of two numbers {|x_{1} − x_{2}| , |y_{1} − y_{2}|}. The values of these differences can be 0, …, n−1 except that both can’t be zero since the positions are different. These are the holes. So there are n(n + 1)/2 − 1 holes.

Each set of two checkers is a pigeon. There are (n + 1)n/2 pigeons by reasoning as in (a). A pigeon gets assigned to a hole which is the difference of the x and y coordinates of the checker positions. Since there is one more pigeon than hole, there must be two pigeons in the same hole. That means the x and y coordinate differences, and hence the distance, between the two pigeons is the same.

Handout ???: Quiz 2 Solutions  3  Name:

Problem 3 [10 points] Counting Source: Fall 99 pset 3 n.2b Use the product rule to show that there are 2^{2^{n}} different truth tables for propositions in n variables. Solution. There are 2^{n} lines (assignments) in the truth table for a formula with n variables, since each of the variables can take on one of two values. For a given truth assignment to the n variables, the proposition can be either true or false; hence, there are 2^{2^{n}} possibilities.

Problem 4 [10 points] Counting

Source: Fall 94 pset 7 n.2

In how many ways can a rook go from the lower-left corner of an m-by-n chess board to the upper-right corner by a shortest path, that is, a path that consists of m + n − 1 squares?

Solution. The rook must make m − 1 moves up and n − 1 moves right, but the order is arbitrary. A path is defined by which of the n+m−2 total moves are the “up” moves. Thus we may choose different paths simply by choosing which of the moves should be the “up”s, so there are \binom{m+n−2}{m−1} = \binom{m+n−2}{n−1} possible paths.

Problem 5 [10 points] Counting

Source: Fall 95 pset 8 n.3

How many distinguishable ways are there to put n books on r shelves (order on the shelf matters)?

Solution. For the first book there are r choices. For the next book there are r + 1 choices since we can think of the first book as splitting the shelf it is put on into two shelves. Similarly for the third book there are r + 2 choices. In this way we see that the total number of ways, by the product rule, is r × (r + 1) × (r + 2) … (n + r − 1).

Problem 6 [10 points] Inclusion-Exclusion

Source: Fall 94 pset 7 n.9

How many integers in the range from 1 to 2414 are not divisible by any of the numbers 18, 23, and 36?

Solution. First, if a number is divisible by 36, then it is also divisible by 18, so we can simplify our problem. Now, we use inclusion-exclusion to count the number of integers from 1 to 2414 not divisible by 18 or 23. Make a table, and add the numbers with appropriate signs:

divisible by least common multiple number of integers include/exclude
each of  of divisors  from 1 to 2414  +/−
1  2414  +
18  18  134  −
23  23  104  −
18, 23  414  5  +

These add up to 2181.

Handout ???: Quiz 2 Solutions  7  Name:

Problem 7 [10 points] Summations Source: New Find a closed form for

∑_{i=0}^{n} [zx^{i} (1 + \sqrt{[∑_{k=0}^{m} y^{k}]^{i}}) (1 − \sqrt{[∑_{ℓ=0}^{m} y^{ℓ}]^{i}})]

Solution. Denote β = ∑_{k=0}^{m} y^{k} = ∑_{ℓ=0}^{m} y^{ℓ} = (y^{m+1} − 1)/(y − 1). Then,

∑_{i=0}^{n} [zx^{i} (1 + \sqrt{β^{i}}) (1 − \sqrt{β^{i}})] = ∑_{i=0}^{n} [zx^{i} (1 − β^{i})]
= z (∑_{i=0}^{n} x^{i} − ∑_{i=0}^{n} [xβ]^{i})
= z (\frac{x^{n+1} − 1}{x − 1} − \frac{(xβ)^{n+1} − 1}{x − 1})
= \frac{zx^{n+1} (1 − β^{n+1})}{x − 1}

= \frac{zx^{n+1} (1 − (\frac{y^{m+1}−1}{y−1})^{n+1})}{x − 1}

Problem 8 [10 points] Combinatorics

Source: Fall 95 pset 7 n.6

Prove that

∑_{k=1}^{n}k ( \begin{matrix}n \\ k \end{matrix} ) = n2^{n−1}

(a) [5 points] using a combinatorial argument.

Solution. Consider the number of ways of picking a team of size k from a group of n people and designating one of them captain. This can be done in k\binom{n}{k} ways, for all k = 0, 1, …, n. But the total number of ways of doing this can also be counted differently. First select the captain - n ways - then select an arbitrary subset of the rest - 2^{n−1} ways. Hence the result follows.

(b) [5 points] by finding a closed form for ∑_{k=1}^{n} ( \begin{matrix}n \\ k \end{matrix} ) kx^{k} and evaluating it at x = 1.

Solution. Differentiating

(1 + x)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}

we get

n(1 + x)^{n−1} = ∑_{k=1}^{n} k\binom{n}{k}x^{k−1}

and evaluating it at x = 1 we get the desired result.

Handout ???: Quiz 2 Solutions  9  Name:

Problem 9 [10 points] Combinatorics Source: Fall 99 rec 18 Theorem. For any k and n such that n ≥ k ≥ 0,

∑_{m=k}^{n} \binom{m}{k} = \binom{n + 1}{k + 1}.

Give a combinatorial argument proving the theorem. Hint: Classify subsets of k+1 elements from {1, …, n + 1} by their maximum element. Solution. Combinatorial argument:

Proof. We know the righthand side of the equation is the number of ways to choose k + 1 elements from {1, …, n + 1}. For any such subset, the maximum element m + 1 must satisfy k + 1 ≤ m + 1 ≤ n + 1. For each m ∈ \{k, …, n\}, there are \binom{m}{k} subsets of k + 1 elements from \{1, …, m + 1\} whose maximum element is m + 1. So the lefthand side of the equation also counts the number of such subsets.

For the record, here’s an algebraic proof:

Proof. We prove the theorem by induction on n. Base Case: n = 0. Then also k = 0 and the statement of the theorem simplifies to

\binom{0}{0} = \binom{1}{1}

which is true. Inductive Step: We distinguish two cases. If n = k then the statement of the theorem simplifies to

\binom{n}{n} = \binom{n + 1}{n + 1}

which is true. Otherwise, we proceed as follows:

\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}  By Pascal’s equality
= \binom{n}{k} + ∑_{m=k}^{n−1} \binom{m}{k} By Inductive Hypothesis
= ∑_{m=k}^{n} \binom{m}{k}  QED

Problem 10 [10 points] Order of Growth

Source: New

(a) [5 points] From lecture, we know that any comparison sorting algorithm 𝔸 must take time Ω(n log n) on n elements. Which of the following is a consequence of this fact? Explain your answer.

a) There is some constant c > 0 for which all executions of 𝔸 will perform exactly cn log n steps.

b) There is some constant c > 0 for which all executions of 𝔸 will perform at least cn log n steps.

c) There is some constant c > 0 for which the longest executions of 𝔸 will perform at least cn log n steps.

d) There is some constant c > 0 for which all executions of 𝔸 will perform at most cn log n steps.

e) There is some constant c > 0 for which the longest executions of 𝔸 will perform at most cn log n steps.

Solution. c is the correct answer. Ω-notation deals only with worst-case lower bounds; Ω(n log n) is a lower bound on the number of steps required for the worst-case input to 𝔸.

(b) [5 points] Prove that 10n^{2} = O(n^{3}).

Solution. 10n^{2} ≤ c · n^{3} for all n ≥ 1 when c ≥ 10, so the theorem follows.

Handout ???: Quiz 2 Solutions  11  Name:

Problem 11 [10 points] Order of Growth Source: New, but hardly original Prove that the following recurrence is O(n log n):

T (n) = T (n/2) + T (n/8) + n

Solution. We prove that ∃c such that T (n) ≤ cn log n:

T (n) = T (n/2) + T (n/8) + n
≤ c(n/2) log(n/2) + c(n/8) log(n/8) + n
= (n log n)(c/2 + c/8) − 3n
≤ (5c/8)n log n

which is less than cn log n when 5c/8 < c, which is true for all c > 0.

Handout ???: Quiz 2 Solutions  12  Name:

Problem 12 [10 points] Recurrences Source: New Find a closed form for the recurrence

T_{n} = T_{n−1} + 6T_{n−2}

given the initial conditions T_{0} = 5 and T_{1} = 1. Solution. The characteristic equation for this recurrence is x^{2} − x − 6 = 0, which has roots at 3 and −2. So, the general form for the solution is

T_{n} = A3^{n} + B(−2)^{n}

for which we have to determine the constants A and B. Plug in the initial conditions to get a system of two equations with two unknowns:

5 = A + B
1 = 3A − 2B

Thus, A = 11/5 and B = 14/5, so the solution to the recurrence is

\frac{11}{5}3^{n} + \frac{14}{5}(−2)^{n}

We can perform a sanity check to make us more confident of our answer:

T_{2} = 1 + 6 · 5 = 31
T_{2} = (11/5)3^{2} + (14/5)(−2)^{2} = 99/5 + 56/5 = 155/5 = 31
T_{3} = 31 + 6 · 1 = 37
T_{3} = (11/5)3^{3} + (14/5)(−2)^{3} = 297/5 − 112/5 = 185/5 = 37

Problem 13 [10 points] Recurrences

Source: New

Frohike and Langley have been computing the population growth rate of a certain type of EBE (extraterrestrial biological entity) under controlled conditions. They have determined that these EBE’s have two offspring in their first year, three offspring in their second year, and then die. In addition, 5 EBE’s spontaneously gestate in each year (after year 1) through invasions of other hosts.

(a) [3 points] State the recurrence describing the total number of gestations in year n for n > 1.

Solution. T_{n} = 2T_{n−1} + 3T_{n−2} + 5

(b) [7 points] In their experiment, there were 2 gestations in year 0 and 2 gestations in year 1. Find a closed form for the recurrence you stated in the previous part.

Solution. First, find the general solution to the homogeneous recurrence. The characteristic equation is x^{2} − 2x − 3 = 0, which has roots at 3 and −1. The general solution is then of the form

T_{n} = A3^{n} + B(−1)^{n}

Now we need to find a particular solution to the inhomogeneous recurrence. Since the inhomogeneous term is constant, we guess a constant solution b:

b = 2b + 3b + 5 ⟹ b = −\frac{5}{4}

Therefore, the inhomogeneous recurrence has the simple particular solution T_{n} = −5/4. We now need to determine the constants on the complete solution

T_{n} = A3^{n} + B(−1)^{n} − \frac{5}{4}

by plugging in the initial conditions and solving the resulting system:

T_{0} = 2 = A + B − \frac{5}{4}
T_{1} = 2 = 3A − B − \frac{5}{4}

which has the solution A = B = 13/8. The closed form for this recurrence is then

T_{n} = \frac{13}{8}3^{n} + \frac{13}{8}(−1)^{n} − \frac{5}{4}

We can perform a sanity check to make us more confident of our answer:

T_{2} = 2 · 2 + 3 · 2 + 5 = 15
T_{2} = (13/8)3^{2} + (13/8)(−1)^{2} − 5/4 = 15
T_{3} = 2 · 15 + 3 · 2 + 5 = 41
T_{3} = (13/8)3^{3} + (13/8)(−1)^{3} − 5/4 = 41

Problem 14 [10 points] Recurrences

Source: New

Frohike and Langley have been computing the population growth rate of a certain type of EBE (extraterrestrial biological entity) under controlled conditions. They have determined that these EBE’s have two offspring in their first year, three offspring in their second year, and then die. In addition, 4n + 4 EBE’s spontaneously gestate in each year n ≥ 2 through invasions of other hosts.

(a) [3 points] State the recurrence describing the total number of gestations in year n for n > 1.

Solution. T_{n} = 2T_{n−1} + 3T_{n−2} + 4n + 4

(b) [7 points] In their experiment, there were 2 gestations in year 0 and 2 gestations in year 1. Find a closed form for the recurrence you stated in the previous part.

Solution. First, find the general solution to the homogeneous recurrence. The characteristic equation is x^{2} − 2x − 3 = 0, which has roots at 3 and −1. The general solution is then of the form

T_{n} = A3^{n} + B(−1)^{n}

Now we need to find a particular solution to the inhomogeneous recurrence. Since the inhomogeneous term is linear, we guess a linear solution an + b:

an + b = 2[a(n − 1) + b] + 3[a(n − 2) + b] + 4n + 4
⟹ a = 2a + 3a + 4 ⇒ a = −1
b = −2a + 2b − 6a + 3b + 4 ⇒ b = −3

Therefore, the inhomogeneous recurrence has the simple particular solution T_{n} = −n − 3. We now need to determine the constants on the complete solution

T_{n} = A3^{n} + B(−1)^{n} − n − 3

by plugging in the initial conditions and solving the resulting system:

T_{0} = 2 = A + B − 3
T_{1} = 2 = 3A − B − 1 − 3

which has the solution A = 11/4 and B = 9/4. The closed form for this recurrence is then

T_{n} = \frac{11}{4}3^{n} + \frac{9}{4}(−1)^{n} − n − 3

We can perform a sanity check to make us more confident of our answer:

T_{2} = 2 · 2 + 3 · 2 + 8 + 4 = 22
T_{2} = (11/4)3^{2} + (9/4)(−1)^{2} − 2 − 3 = 22
T_{3} = 2 · 22 + 3 · 2 + 12 + 4 = 66
T_{3} = (11/4)3^{3} + (9/4)(−1)^{3} − 3 − 3 = 66

Problem 15 [10 points] Countability

Source: New

(a) [5 points] Ben Bitdiddle hears in class that the power set of the natural numbers is uncountable. He sweats over a hot X terminal for several hours, and then claims to have constructed a bijection from this set to the set of real numbers, showing that the reals are uncountable.

Given a subset S ⊆ ℕ, the binary expansion of corresponding real number is the number for which the n^{th} digit is 1 if and only if n ∈ S. Denote the mapping from 2^{ℕ} → ℝ by f. So, for example, f({1, 3, 4}) = .1011 and f(2ℕ) = .01010101 . . ..

Ben claims f is a bijection. “f is injective,” he says, “since f(S) = f(T) implies that the corresponding digits in the two real numbers have ones in exactly the same positions, so S and T must contain exactly the naturals corresponding to the indices of those positions.” He goes on to say that f is surjective, since every possible real number r can be represented as a (possibly infinitely-long) binary string, so clearly we can construct a set S such that f(S) = r.

While the real numbers are indeed uncountable, something is wrong with Ben’s proof. Explain the problem.

Solution. Ben claims f is injective while it is not. Remember that .1 = .01111 …, so in fact f({1}) = f({2, 3, 4, …}) while obviously {1} ≠ {2, 3, 4, …}.