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

Practice Quiz 2 Solutions

Problem 1

(a) Give tight (Θ) bounds for

∑_{i=1}^{n} \frac{1}{\sqrt{i}}.

Solution.

∫_{1}^{n} \frac{1}{\sqrt{x}}dx  ≤ ∑_{i=1}^{n} \frac{1}{\sqrt{i}}  ≤ 1 + ∫_{1}^{n} \frac{1}{\sqrt{x}}dx

2x^{\frac{1}{2}} |_{1}^{n}  ≤ ∑_{i=1}^{n} \frac{1}{\sqrt{i}}  ≤ 1 + 2x^{\frac{1}{2}} |_{1}^{n}

2\sqrt{n} − 2  ≤ ∑_{i=1}^{n} \frac{1}{\sqrt{i}}  ≤ 2\sqrt{n} − 1

lim_{n→∞} \frac{2\sqrt{n} − 2}{\sqrt{n}} ≤ lim_{n→∞} \begin{matrix}∑ & {n \atop i=1} & \frac{1}{\sqrt{i}} \\ √ & \overline{n} \end{matrix} ≤ 1 + lim_{n→∞} \frac{2\sqrt{n} − 1}{\sqrt{n}}
2 ≤ lim_{n→∞} \begin{matrix}∑ & {n \atop i=1} & \frac{1}{\sqrt{i}} \\ √ & \overline{n} \end{matrix} ≤ 2

That is

∑_{i=1}^{n} \frac{1}{\sqrt{i}} = Θ(\sqrt{n}).

(b) Express the following in closed form

∑_{p=1}^{∞} ∑_{q=p}^{∞} x^{p}y^{q}.

(Note that the lower indices are not constants.)

Solution.

∑_{p=1}^{∞} ∑_{q=p}^{∞} x^{p}y^{q}  = ∑_{p=1}^{∞} x^{p}y^{p} ∑_{q=p}^{∞} y^{q−p}

= ∑_{p=1}^{∞} x^{p}y^{p} ∑_{r=0}^{∞} y^{r}

= (∑_{p=1}^{∞} x^{p}y^{p}) (∑_{r=0}^{∞} y^{r})

= (\frac{xy}{1−xy}) (\frac{1}{1−y}) .

Problem 2 I have n one-dollar bills that I wish to donate to m charities.

(a) In how many ways can I do this if I don’t care how much each charity gets?

Solution. Simply insert m−1 bars into a string of n one-dollar bills. Then the i-th charity gets the money between bars i − 1 and i. This gives you \binom{n+m−1}{m−1} ways to distribute the money.

(b) In how many ways can I do this so that each charity gets at least $ 10?

Solution. First give 10 dollars to each charity, then distribute the remaining n − 10m dollars as in part a. This gives you \binom{n+m−1−10m}{m−1} = \binom{n−9m−1}{m−1} ways as long as n ≥ 10m.

Problem 3 In how many ways can 5 indistinguishable covered wagons, 4 indistinguishable uncovered wagons and 1 horse be arranged in a circle?

Solution. This problem is just a permutation of a multiset, except that we need to account for rotations of a circle being the same. This can be thought of either as fixing one object, say the horse, and arranging the wagons around it (\binom{9}{5} ways), or counting the permutations and dividing by 10 to avoid overcounting the rotations (\frac{1}{10} \frac{10!}{5!4!1!}). Either way the answer is 126. The most common mistake was to forget about overcounting the rotations.

Problem 4 How many 6-digit decimal numbers are there that do not contain “123” or “456” as a subsequence? (for purposes of this problem numbers may have leading 0’s)

Solution. Let

• A be the set of all six-digit strings, using the digits {0, 1, …, 9}.

• B be the set of six-digit strings that contain the subsequence 123.

• C be the set of all six-digit strings that contain the subsequence 456.

• D be the set of all six-digit strings that do not contain 123 or 456.

We’re interested in figuring out |D|. Since

D = A − (B ∪ C),

and B ∪ C ⊆ A, we can use the inclusion-exclusion formula:

|D| = |A| − |B ∪ C| = |A| − |B| − |C| + |B ∩ C|.

First, |A| = 10^{6}, since we can put any of ten digits in each of six places.

Now, a string can contain 123 in any of four positions; once this position is chosen, we have 1000 choices for the remaining positions. However, this approach counts the string 123123 twice, so the total size of B is

|B| = 4(1000) − 1 = 3999.

By the same reasoning, we get

|C| = 3999.

Finally, there are only two strings in B ∩ C, namely 123456 and 456123. Thus,

|B ∩ C| = 2.

Plugging this into our formula, we get

|D| = 10^{6} − 3999 − 3999 + 2 = 992004.

(Common Mistakes: A lot of people forgot about the double-counting of 123123 and 456456, and so had |B| = |C| = 4000. Some people also argued that since 123 can appear in one of only four places in the string, |B| = 4.)

Problem 5 Consider the following nuclear reaction. There is one particle of type 1 at time instant 1. Each particle of type i existing at time t undergoes fission to produce one particle of type i + 1 and one of type i + 2 at time instant t + 1.

(a) Write and justify a recurrence for f(i, t), the number of particles of type i at time t. (Make sure to include the base cases for your recurrence.)

Solution. Particles of types i − 2 and i − 1 at time t − 1 give rise to particles of type i at time t and this is the only way that particles of type i are formed at time t. Hence we get the recurrence

f(i, t) = f(i − 1, t − 1) + f(i − 2, t − 1), t > 1.

The base case is

• f(1, 1) = 1.

• f(i, 1) = 0, −∞ ≤ i ≤ ∞, i ≠ 1.

(b) Prove by induction that f(i, t) = \binom{t−1}{i−t}. (You do not need to reprove identities that were proven in class.)

Solution. (Note: Let a be any nonnegative integer and b be any integer. In what follows, we use the definition that \binom{a}{b} = \frac{a!}{b!(a−b)!} when a ≥ b ≥ 0 and otherwise \binom{a}{b} = 0 when . Pascal’s identity holds for this definition.)

The proof is by induction on t. Let P (t) be

f(i, t) = \binom{t − 1}{i − t}, ∀i.

Base Case. P (1) is true since

• f(1, 1) = \binom{0}{0} = 1.

• f(i, 1) = \binom{0}{i−1} = 0, −∞ ≤ i ≤ ∞, i ≠ 1.

Inductive step. Assume P (t) is true. Consider P (t + 1).

f(i, t + 1) = f(i − 1, t) + f(i − 2, t) by the recurrence from part a)
= \binom{t−1}{i−1−t} + \binom{t−1}{i−2−t}  by inductive hypothesis
= \binom{t}{i−1−t}  by Pascal’s identity

Hence P (t + 1) is true. Thus P (t) is true for all t and we are done.

Problem 6

(a) Give tight (Θ) bounds for T (n). Assume that T (n) is constant for n ≤ 10.

T (n) = 4T (n/2) + 6n.

Solution.

T (n)  = 4T (n/2) + 6n
= 4^{2}T (n/2^{2}) + 6(n + n/2)
= …
= 4^{i}T (n/2^{i}) + 6(n + n/2 + … + n/2^{i−1})
= …
= 4^{log_{2} n}T (1) + 6(n + n/2 + … + n/2^{log_{2} n −1})
= n^{2}T (1) + O(n)
= Θ(n^{2})

(b) Rank the following functions by order of growth; that is find an arrangement g_{1} = α(g_{2}) = α(g_{3}) = … = α(g_{6}) and state whether α is o or Θ for each step.

• n(log_{2} n)^{5}

• n^{3}

• n!

• (n!)^{2}

• n^{n}

• 3 · 8^{log_{2} n} + 4^{log_{2} n}

Solution.

n(log_{2} n)^{5} = o(n^{3}) = Θ(3 · 8^{log_{2} n} + 4^{log_{2} n}) = o(n!) = o(n^{n}) = o((n!)^{2}).

Problem 7 Prove or disprove: f(n) = O(g(n)) implies lg(f(n) = O(lg(g(n))), where g(n) is nondecreasing, g(1) > 1 and f(n) ≥ 0 for all sufficiently large n.

Solution. The theorem is true. Assume f(n) = O(g(n)), so ∃c, N ∀n ≥ N f(n) ≤ cg(n). Choose appropriate N > 1. Then, ∀n ≥ N,

f(n) ≤ cg(n)
⇒ log f(n) ≤ log cg(n)  (monotonicity)
= log c + log g(n)
≤ k log g(n)  when k = 1 + \frac{log c}{log g(1)} (∗)

So indeed, log f(n) = O(log g(n)). The justification for the step marked (∗) is simply that, as g(n) is nondecreasing and has some positive value (in this case at n = 1), then for all a > 1, log g(a)/ log g(1) ≥ 1, so

log c + log g(a) ≤ log c · \frac{log g(a)}{log g(1)} + log g(a)
= k log g(a)

Problem 8 Solve the following recurrence:

f(1) = f(2) = 1

f(n) − 4f(n − 1) + 4f(n − 2) = 3^{n}

Solution. The characteristic equation is x^{2} − 4x + 4 = 0, which has a double root at 2. The general solution to the homogeneous part is

f(n) = A2^{n} + Bn2^{n}

We now have to determine a particular solution to the inhomogeneous recurrence, whose form we guess is c3^{n}; thus, we need to find the constant c:

c3^{n} − 4c3^{n−1} + 4c3^{n−2} = 3^{n}
c · 9 − 4c · 3 + 4c = 9
(9 − 12 + 4)c = 9
c = 9

so the inhomogeneous part is 9 · 3^{n} = 3^{n+2}.

Now we know that the complete solution has the form

A2^{n} + Bn2^{n} + 3^{n+2}

for which we need to find the constants given the boundary conditions.

f(1) = 1 = 2A + 2B + 27
f(2) = 1 = 4A + 8B + 81

which resolves to A = −6, B = −7. Thus, the complete solution is

f(n) = −6 · 2^{n} − 7n2^{n} + 3^{n+2}

Problem 9 Give tight (Θ) bounds for T (n). Assume that T (n) is constant for n ≤ 2.

(a) T (n) = 7T (n/3) + n^{2}

Solution. Expand:

T (n) = 7T (n/3) + n^{2}
= 7^{2}T (n/3^{2}) + 7(n/3)^{2} + n^{2}
= 7^{3}T (n/3^{3}) + 7^{2}(n/3^{2})^{2} + 7(n/3)^{2} + n^{2}
⋮
= 7^{log_{3} n}T (1) + 7^{log_{3} n−1}(n/3^{log_{3} n−1})^{2} + ⋯ + 7^{2}(n/3^{2})^{2} + 7(n/3)^{2} + n^{2}
= 7^{log_{3} n}Θ(1) + (7/9)^{log_{3} n−1}n^{2} + ⋯ + (7/9)^{2}n^{2} + (7/9)n^{2} + n^{2}
= 7^{log_{3} n}Θ(1) + \frac{1 − (7/9)^{log_{3} n}}{2/9} n^{2}
≈ n^{1/ log_{7} 3}Θ(1) + \frac{9}{2}n^{2}

Since 1/ log_{7} 3 < 2, this recurrence is Θ(n^{2}).

(b) T (n) = T (2n/3) + T (n/4) + n

Solution. Guess and verify: assume T (n) = 12n. Then,

12n = T (n) = T (2n/3) + T (n/4) + n
= 8n + 3n + n
= 12n

Alternatively, we can expand:

T (n) = T (2n/3) + T (n/4) + n
= T ((2/3)^{2}n) + 2T ((2/3)(1/4)n) + T ((1/4)^{2}n) + (11/12)n + n
= T ((2/3)^{3}n) + 3T ((2/3)^{2}(1/4)n) + 3T ((2/3)(1/4)^{2}n) + T ((1/4)^{3}n)
+(11/12)^{2}n + (11/12)n + n
⋮
= \underbrace{(1 + 1 + ⋯ + 1)} log n + n · ((11/12)^{log_{3/2} n} + ⋯ + (11/12)^{2} + (11/12) + 1)
= Θ(n) + n (\frac{1 − (11/12)^{log_{3/2} n}}{1/12} )
≈ Θ(n) + 12n = Θ(n)

(c) T (n) = 4T (n/3) + n

Solution. Expand:

T (n) = 4T (n/3) + n
= 4^{2}T (n/3^{2}) + 4(n/3) + n
= 4^{3}T (n/3^{3}) + 4^{2}(n/3^{2}) + 4(n/3) + n
⋮
= 4^{log_{3} n}T (1) + 4^{log_{3} n−1}(n/3^{log_{3} n−1}) + ⋯ + 4^{2}(n/3^{2}) + 4(n/3) + n
= 4^{log_{3} n}Θ(1) + (4/3)^{log_{3} n−1}n + ⋯ + (4/3)^{2}n + (4/3)n + n
= 4^{log_{3} n}Θ(1) + 3 · ((4/3)^{log_{3} n} − 1) n
= n^{1/ log_{4} 3}Θ(1) + 3 · (\frac{n^{1/ log_{4} 3}}{n} − 1) n
= n^{1/ log_{4} 3}Θ(1) + 3n^{1/ log_{4} 3} − 3n
= Θ(n^{1/ log_{4} 3})

Problem 10 Pick any set A of ten numbers from 1 to 100. Prove that there must exist two distinct, non-empty subsets whose sums are equal. E.g., consider the set A = {51, 11, 81, 68, 73, 87, 23, 29, 25, 94}; in this case, the subsets {25, 51, 29} and {94, 11} both add to 105. Hint: Consider the number of subsets of a 10-element set.

Solution. Note that ten numbers between 1 and 100 have a maximum sum of ≈ 100 (actually 100 + 99 + 98 + ⋯ + 91). However, there are 2^{10} − 1 = 1023 non-empty subsets of a set of 10 numbers. If we take our pigeonholes to be the possible sums and our pigeons to be the subsets, there are more subsets than possible sums, so at least one pigeonhole must have more than one pigeon.