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

Problem Set 7.5 Solutions

Problems:

NOTE: There is no need to simplify sums, binomial coefficients, and factorials in your answers.

Problem 1 How many ways are there to distribute eight balls into six distinct boxes with the first two boxes having collectively at most four balls if

(a) the balls are identical?

Solution.

Let us consider placing n balls into k boxes so that exactly r balls are placed in the first two boxes. This can be done in

\binom{r + 2 − 1}{2 − 1}\binom{(n − r) + (k − 2) − 1}{(k − 2) − 1}

ways, since there are BP(r, 2) = \binom{r+2−1}{2−1} ways to place r balls into first two boxes and BP(n−r, k − 2) = \binom{(n−r)+(k−2)−1}{(k−2)−1} ways to place the remaining n − r balls into the other k − 2 boxes. We can place the balls into boxes, so that at most r balls go into the first two boxes, in

∑_{i=0}^{r} \binom{i + 2 − 1}{2 − 1}\binom{(n − i) + (k − 2) − 1}{(k − 2) − 1}

ways. In particular for n = 8, k = 6 and r = 4 we get

∑_{i=0}^{4} \binom{i + 2 − 1}{2 − 1}\binom{(8 − i) + (6 − 2) − 1}{(6 − 2) − 1} = 1056.

□

(b) the balls are distinct?

Solution.

As in the part (a), we compute the number of ways n balls can be placed into k boxes so that exactly r of them are placed in the first two boxes. Since the balls are distinct, we have \binom{n}{r} ways to choose which balls to place in the first two boxes, and then we have 2^{r} ways to place the balls into first two boxes, and (k − 2)^{n−r} ways to place the rest of the balls into the remaining k − 2 boxes. Thus the total number of posibilities is

\binom{n}{r}2^{r}(k − 2)^{n−r}.

If we require that at most r balls go into the first two boxes we compute that the number of posibilities is

∑_{i=0}^{r} \binom{n}{i}2^{i}(k − 2)^{n−i}.

For n = 8, k = 6 and r = 4 we get

∑_{i=0}^{4} \binom{8}{i}2^{i}(6 − 2)^{8−i} = 1531904.

□

Problem 2 Solve the following counting problems.

(a) Suppose that Math Moose starts at position (0, 0). At any time, he can step north (incrementing the first coordinate) or step east (incrementing the second coordinate). In how many different ways can he reach position (n, n), where n is a non-negative integer?

Solution.

Math Moose must take 2n steps in total. Of these, he must choose a subset of N to be north steps. This gives \binom{2n}{n} different ways to reach (n, n).

□

(b) How many different ways are there to list the numbers 1, 2, …, 2n such that the even numbers appear in increasing order and the odd numbers appear in decreasing order?

Solution.

There are (2n)! ways to list the numbers 1, 2, …, n. We can define a n!-to-1 mapping that takes an arbitrary listing to a listing in which the even numbers are sorted in increasing order and the odd numbers remain as before. Thus, by the quotient rule there are (2n)!/n! listings in which the even numbers appear in increasing order. Similarly, we can define an n!-to-1 mapping that takes a listing in which the even numbers appear in increasing order and the odd numbers are in an arbitrary order to a listing in which the even numbers appear in increasing order (as before) and the odd numbers appear in decreasing order. Therefore, there are

\frac{(2n)!}{n! n!} = \binom{2n}{n}

listings in which the even numbers are increasing and the odd numbers are decreasing. □ (c) Describe a bijection that maps each one of Math Moose’s paths to a listing of the numbers 1, 2, … 2n with even numbers increasing and odd numbers decreasing.

Solution.

Each time Math Moose take a step north, write down an even number, starting with 2 and working up. Each time Math Moose takes a step east, write an odd number, starting with 2n − 1 and working down.

□

Problem 3 A pizza house is having a promotional sale. Their commercial reads: “ … buy 2 large pizzas at regular price, get up to 11 different toppings for each pizza absolutely free. That’s 4, 194, 304 different ways to design your order! … ”

Note: (∑_{k=0}^{11} \binom{11}{k})^{2} = (2048)^{2} = 4, 194, 304

(a) Show that 4, 194, 304 is actually wrong and give the right answer for the number of ways that you can choose toppings for the two pizzas.

Solution.

The number of ways to choose different toppings for one pizza is clearly A ≡ ∑_{k=0}^{11} \binom{11}{k} = 2^{11} =

2, 048. However, when they say there are A^{2} different ways to choose toppings for two pizzas, they are making the mistake of counting the combination “one mushroom pizza, and one cheese pizza” as different from the combination “one cheese pizza, and one mushroom pizza.”

The right solution is A + \binom{A}{2} = \frac{1}{2}(A^{2} + A) = 2, 098, 176, where A is the number of ways to choose

2 pizzas with the same toppings, and \binom{A}{2} is the number of ways to choose 2 different pizzas. □

(b) Now assume that you can choose any number of the same topping as long as the total number of toppings is no more than 11. (That is, you can have 2 meatball, 4 ham and 5 sausage toppings if you are truly a meat lover.) How many different ways can you now choose toppings for your two pizzas?

Solution.

For a single pizza, this is the “stars and bars” problem in disguised form. If k is the total number of toppings you want on a pizza then the number of ways of throwing k identical balls into 11 bins is identical to choosing a total of k toppings out a total of 11 different topping-possibilities.

Hence the number of ways to order one pizza is B ≡ ∑_{k=0}^{11} \binom{10 + k}{k} = \binom{22}{11} = 705, 432. Using the

same argument as in part (a), we see that the number of ways to order two pizzas is B + \binom{B}{2} =

\frac{B^{2} + B}{2} = 248, 817, 506, 028.

□

Problem 4 A computer operating system requires file names to be exactly four letters long; uppercase and lowercase letters are distinct.

(a) How many possible file names are there? Solution.

52^{4} = 7311616.

□

(b) The operating system is changed so that uppercase and lowercase are no longer distinct. Figure out the new number of file names in two ways: applying the division rule to (a) and directly. Solution.

52^{4} ÷ 2^{4} = 456976 = 26^{4}.

□

(c) The operating system is changed so that file names may be at least one letter and up to four letters long. Repeat (a) and (b). Can the division rule still be used? Solution.

∑_{i=1}^{4} 52^{i} = (52^{5} − 52)/(52 − 1) = 7454980; ∑_{i=1}^{4} 26^{i} = (26^{5} − 26)/(26 − 1) = 475254. The division rule can be applied only to the individual terms of the summation.

□

Problem 5

(a) How many ways can 2n people be divided into n pairs?

Solution.

(2n)!/n!2^{n}.

Consider all the ways of ordering the 2n people in a line. There are (2n)! ways of doing this. Now group them into pairs based on the linear order, i.e. group the first and second persons, group the third and fourth persons,..., group the (2n − 1)th and 2nth persons. Thus each linear order gives us a unique grouping into pairs. But observe that two different linear orders could give rise to the same grouping into pairs. So let us now count the number of linear orders that give rise to the same grouping into pairs. Given a grouping into pairs, to generate a linear order we need to order each pair (there are 2^{n} ways to do this) and then order the n pairs (there are n! ways to do this). Hence n!2^{n} linear orders give the same grouping into pairs. Thus the total number of ways 2n people can be divided into n pairs is (2n)!/n!2^{n}.

□

(b) How many ways can you choose n out of 2n objects, given that n of the 2n objects are identical?

Solution.

The answer is 2^{n}, since you can pick any subset from the n nonidentical objects, and make up the rest with the identical ones. And the number of subsets of n different objects is 2^{n}.

□

Problem 6 Find the coefficients of

(a) x^{5} in (1 + x)^{11} Solution.

\binom{11}{5} = 462

□

(b) a^{2}b^{8} in (a + b)^{10} Solution.

\binom{10}{2} = 45

□

(c) a^{6}b^{6} in (a^{2} + b^{3})^{5} Solution.

a^{6}b^{6} = (a^{2})^{3}(b^{3})^{2}, so the coefficient is \binom{5}{3} = 10

□

(d) x^{3} in (3 + 4x)^{6} Solution.

\binom{6}{3}3^{3}4^{3} = 34560

□

(e) x^{10} in (x + (1/x))^{100} Solution.

\binom{100}{55}
□

(f) x^{8}y^{9} in (3x + 2y)^{17} Solution.

\binom{17}{8}3^{8}2^{9}

□

(g) x^{k} in (x^{2} − (1/x))^{100} Solution.

x^{k} has a nonzero coefficient iff −100 ≤ k ≤ 200 and k = 2 mod 3. In such a case the coefficient is \binom{100}{(100+k)/3}(−1)^{(200−k)/3}.

□

Problem 7 We wish to prove the identity

∑_{r=0}^{n} \binom{n}{r}^{2} = \binom{2n}{n} ,

for n ∈ ℕ.

(a) Use the binomial theorem and the fact that

(1 + x)^{n}(1 + x^{−1})^{n} = x^{−n}(1 + x)^{2n}

to prove the identity. Solution.

x^{−n}(1 + x)^{n}x^{n}(1 + x^{−1})^{n} = x^{−n}(1 + x)^{n}(x + 1)^{n}
(1 + x)^{n}(1 + x^{−1})^{n} = x^{−n}(1 + x)^{2n}
∑_{i=0}^{n} \binom{n}{i}x^{i} ∑_{j=0}^{n} \binom{n}{j}x^{−j} = x^{−n} ∑_{i=0}^{2n} \binom{2n}{i}x^{i}

∑_{i=0}^{n} \binom{n}{i}^{2} = \binom{2n}{n}

by equating the coefficients of x^{0}.

□

(b) Consider a set of 2n objects, of which n are red and n are blue. Use the fact that

\binom{n}{r}^{2} = \binom{n}{r}\binom{n}{n − r}

to give a combinatorial proof of the identity. Solution.

Suppose we have 2n objects, n of which are red, and n of which are blue. How many ways can we pick r red ones and n − r blue ones? Clearly this is

\binom{n}{r}\binom{n}{n − r} = \binom{n}{r}^{2}.

How many ways can we choose n objects total, regardless of how many are of each color? This is just

∑_{r=0}^{n} \binom{n}{r}^{2}.

But there are \binom{2n}{n} ways to choose n objects, so these must be the same number.

□

Problem 8 Prove that

∑_{a=0}^{n} ∑_{b=0}^{n−a} \frac{n!}{a!b!(n − a − b)!} = 3^{n} .

[Hint: find a formula for (x + y + z)^{n} and then set x = y = z = 1.]

Solution.

We can write (x + y + z)^{n} as follows:

\begin{aligned}(x + y + z)^{n} & = & (x + y + z)(x + y + z) ⋯ (x + y + z) \\ & = & ∑_{\begin{matrix}a,b,c \\ a≥0,b≥0,c≥0 \\ a+b+c=n \end{matrix}} C_{a,b,c}x^{a}y^{b}z^{c} \end{aligned} .  (1)

where C_{a,b,c} is the number of ways to partition a set of a + b + c elements into three subsets of size, respectively, a, b, and c.

We compute C_{a,b,c} using the product rule. A partition can be obtained by first choosing a elements out of a + b + c ones, and then choosing b elements out of the remaining b + c ones. The number of ways to make such choices is

C_{a,b,c} = \binom{a + b + c}{a} · \binom{b + c}{b} = \frac{(a + b + c)!}{a!(b + c)!} · \frac{(b + c)!}{b!c!} = \frac{(a + b + c)!}{a!b!c!} .  (2)

Substituting Equation (??) into Equation (??) we have

(x + y + z)^{n} = ∑_{\begin{matrix}a,b,c \\ a≥0,b≥0,c≥0 \\ a+b+c=n \end{matrix}} \frac{n!}{a!b!c!}x^{a}y^{b}z^{c}

= ∑_{a=0}^{n} ∑_{b=0}^{n−a} \frac{n!}{a!b!(n − a − b)!}x^{a}y^{b}z^{n−a−b} .

If we set x = y = z = 1 we derive

3^{n} = (1 + 1 + 1)^{n} = ∑_{a=0}^{n} ∑_{b=0}^{n−a} \frac{n!}{a!b!(n − a − b)!}1^{a}1^{b}1^{n−a−b} .

□

Problem 9 Prove or disprove the following statements about sets. (We use “collection” as a synonym for “set” to make some of the statements easier to read.)

(a) The product of a finite collection of countable sets is countable.

Solution.

The statement is true.

Proof. The proof is by induction. Let P (n) be the proposition that the product of n countable sets is countable. In the base case, P (1) is true because the product of a single countable set is itself. In the inductive step, for n ≥ 1 assume P (n) to prove P (n + 1). The product of n + 1 countable sets S_{1}, S_{2}, …, S_{n+1} can be written as shown below.

(S_{1} × S_{2} × … × S_{n}) × S_{n+1}

The first term is a countable set by induction, and the second term is a countable set by definition. The product of two countable sets is countable, as shown in lecture. Therefore, the product of n+1 countable sets is countable. This shows that P (n) implies P (n + 1), and the claim is proved by induction.

□

(b) The product of a countable collection of finite sets is countable.

Solution.

The statement is false.

We will construct a bijection between the product of a countable number of finite sets and the power set of the natural numbers. Since the latter is uncountable, the former must be uncountable as well.

Consider the countable collection of finite sets S_{1} = S_{2} = … = {0, 1}. The product S_{1} × S_{2} × … consists of all infinite binary sequences, e.g. (0, 1, 1, 0, 1, …). There is a natural bijection between such infinite binary sequences and the power set of the natural numbers. In particular, let the sequence (b_{0}, b_{1}, …) correspond to the set of all natural numbers i such that b_{i} = 1. This bijection implies that the set of infinite binary sequences is uncountable.

□ (c) The set of all finite subsets of a countable set is countable.

Solution.

The statement is true.

Proof. Let S be a countable set. For k ≥ 0, let S_{k} be the set of k-element subsets of S. The set of all finite subsets of S is then the union of the sets S_{k} for k ≥ 0. We will prove below that every set S_{k} is countable. This will imply that the set of all finite subsets of S is a union of a countable collection of countable sets and is therefore countable.

All that remains is to show that S_{k}, the set of k-element subsets of S, is countable for all k ≥ 0. We prove this by establishing an injection from S_{k} to S^{k}, the product of the set S with itself taken k times. In particular, the injection maps the set {s_{1}, s_{2}, … s_{k}} ∈ S_{k} to the tuple (s_{1}, s_{2}, …, s_{k}) ∈ S^{k}, where the elements in the tuple are ordered in an arbitrary way. Since S^{k} is countable, the injection implies that S_{k} is also countable.

□

(d) Suppose that the intersection of a countable collection of sets is finite. Then there exists a finite subcollection of the sets with finite intersection.

Solution.

The statement is false.

Let S_{k} be the set of integers divisible by k, for k ≥ 1. The intersection of this countable family of sets is finite; in fact, the intersection is {0}, since zero is the only integer divisible by every positive integer. However, there is no finite subfamily of sets S_{k} with finite instersection. In particular, the intersection of the finite subfamily

S_{a_{1}} ∩ S_{a_{2}} ∩ … ∩ S_{a_{n}}

contains all integers of the form m · a_{1} · a_{2} ⋯ a_{n} where m ∈ ℤ.

□

Problem 10 Use a diagonalization argument to show that the set of functions from the positive integers to the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is uncountable.

Solution.

Proof. Assume, for the purposes of contradiction, that this set is countable. Then there is a listing of the function in the set, f_{1}, f_{2}, . . .. Now define f such that f(i) = (f_{i}(i) + 5) mod 10. Then f is not in the list, because f differs from each f_{i} in the ith value. We have established a contradiction. We conclude that the set is uncountable.

□

Problem 11 A real number is algebraic if it is the root of a polynomial with rational number coefficients. Algebraic numbers form an important part in the study of (what else) modern algebra. A number that is not algebraic is called transcendental.

(a) Let S_{1}, S_{2}, S_{3}, … be a collection of countably many sets. Suppose each S_{i} is countable. Prove ⋃ S_{i} is countable.

Solution.

Proof. Since each S_{i} is countable there is a surjection f_{i} from the naturals to S_{i}. Now define the function f: ℕ × ℕ → ⋃_{i∈ℕ} S_{i} by f(i, j) = f_{i}(j). Clearly, f is a surjection and since ℕ × ℕ is countable, also ∪S_{i} is countable.

□

(b) Prove that for any particular d ∈ ℕ, the set of degree d polynomials with rational coefficients is countable, for all d ≥ 1.

Solution.

Proof. There is a natural bijection between degree d polynomials and elements of the set (ℚ \ {0}) × ℚ^{d}. Specifically, a degree d polynomial is mapped to an element of this set by arranging the coefficients in a (d+1)-tuple. The set of rational numbers, ℚ, was shown to be countable in lecture. In the preceding problem, we showed that a finite product of countable sets is countable. Therefore, the set (ℚ \ {0}) × ℚ^{d} is countable. The bijection then implies that the degree d polynomials are countable.

□

(c) Prove that the set of all roots of degree d polynomials with rational coefficients is countable. (You may use the fact that a degree d polynomial has at most d roots).

Solution.

Proof. Since each degree d polynomial has at most d roots we can give a surjection from P_{d} × {1, …, d} to the set of all roots of degree d polynomials with rational coefficients. For example we can define f(p(x), i) = x_{i}, where x_{1}, …, x_{d} are the roots of p(x) (if p(x) has less then d roots, just repeat the last one many times).

□

(d) Prove that the set of algebraic numbers, which is just the union of the sets in the previous part, is countable.

Solution.

Proof. The set of algebraic numbers is the union of the sets of the roots of polynomials with rational coefficients of degree d, for all d. This is a countable union of countable sets, and from the result in part (a) it is countable.

□

(e) Prove that there is a trancendental number.

Solution.

Proof. The set of real number is uncountable. The subset of algebraic numbers is countable. Therefore, the algebraic numbers form a proper subset of the real numbers, and so there is at least one transcendental number.

□

Problem 12 In this problem we will prove the remarkable fact that there exist mathematical functions that computers, no matter how powerful, simply cannot compute. We will do this through countability arguments.

(a) Show that the set of finite length binary strings is countable.

Solution.

Let B_{n} denote the set of binary strings of length n. This set has exactly 2^{n} elements. Therefore the set of finite length binary strings B = ⋃_{n∈ℕ} B_{n} is a union of countable number of finite sets. We know from Lecture 13 that such union is countable.

Namely, one can easily list all elements of B by first listing the elements of B_{1}, then the elements of B_{2}, then the elements of B_{3}, etc,. We can do this since each set B_{i} has a finite number of elements.

□

(b) From your answer to the previous part, what can you conclude about the countability of the set of all computer programs?

Solution.

Since every computer program can be represented as a finite string of bits (e.g. machine language code), it follows that the set of all computer programs is countable.

Namely, the mapping which represents computer programs as finite strings of bits is an injection. Hence there is a surjection from the set of finite strings of bits to the set of computer programs. From (a) we know that there is a surjection from the set of natural numbers to the set of finite strings of bits. By transitivity of surjective mapping, there is a surjection between natural numbers and computer programs. Hence the set of all comptuer programs is countable.

□

(c) Show that the set of infinite length binary strings is uncountable.

Solution.

We construct a bijection from the set of infinite length binary strings to the power set of the natural numbers. Since the power set of the natural numbers is uncountable, it will then follow that the set of all infinite length binary strings is uncountable.

We need to associate a subset of the naturals with each infinite length binary string. Let b = b_{0}b_{1}b_{2}b_{3} … be an infinite length binary string (here each b_{i} ∈ {0, 1}). We associate with this string the set f(b) = S = {i | b_{i} = 1}. That is, we include i in S = f(b) if and only if the i-th bit position (from the left) of b is 1. Such mapping f is a bijection: It is an injection because if two infinite length binary strings are different, then clearly they map to different subsets. Furthermore, it is a surjection because for every subset S ⊂ ℕ, there is a binary string b s.t. f(b) = S, namely b = b_{0}b_{1}b_{2}b_{3} … where b_{i} is defined as 0 if i ∉ S and 1 if i ∈ S.

Alternative Solution: One can also show that the set B′ is uncountable directly by a diagonalization argument.

Assume B′ is countable and let b^{(1)}, b^{(2)}, b^{(3)}, b^{(4)}, ... be a list of all elements of B′. By diagonalization, we will construct an element b = b_{0}b_{1}b_{2}b_{3}... ∈ B′ s.t. b ≠ b^{(i)} for all i ∈ ℕ as follows: j-th bit of b is defined as the opposite of the j-th bit of string b^{(j)}. Obviously, so defined b is not equal to any b^{(i)} from the list because for every i, the i-th bit of b^{(i)} is different than the i-th bit of b. Therefore, the list b^{(1)}, b^{(2)}, b^{(3)}, b^{(4)}, ... is not a list of all elements in B′, and thus the assumption that B′ is countable leads to a contradiction.

□

(d) A function is a decision function if it maps finite length bit strings into the range {0, 1}. Let F be the set consisting of all possible decision functions. Show that set F is uncountable.

Solution.

From part (a), we know that there is a bijection from the set of all finite length bit strings to the set of natural numbers, hence we can think of decision functions as mapping natural numbers to single bits.

It is an easy bijection between a set of such mappings and a power set of the natural numbers. Namely, we associate with a decision function f a set S = {i ∈ ℕ s.t. f(i) = 1}. Clearly, this is an injection and a surjection. Therefore, since the power set of the set of natural numbers is uncountable then so is the set of decision functions.

Alternative Solution: We can give a bijection between the set of all decision functions and the set of all infinite length bit strings, which by part (c), implies that the set of decision functions is uncountable. Let f be a decision function. We map f to an infinite length string as follows. We set bit i of the string to be f(i). That is, our infinite length bit string will be f(1)f(2)f(3) . . .. Now, observe that this mapping is a bijection. In particular, suppose we have two different decision functions f and g. Since they are different, they must give a different output on some particular input. Suppose that this particular input is the number j. That is, f(j) ≠ g(j). Then, the corresponding infinite length binary strings will differ in the j − th position. This shows that the function is injective. Now, if we have an infinite length bit string b_{0}b_{1}b_{2} …, then a decision function f defined as f(0) = b_{0}, f(1) = b_{1}, f(2) = b_{2}, …, will be mapped to that string. Therefore, the mapping function is surjective. Since it’s injective and surjective, it must be bijective. Alternative Solution 2:

Some students gave a diagonalization argument for why F is uncountable: Assume otherwise and let {f_{1}, f_{2}, f_{3}, ...} be the list of all elements of F. From part (a) we know that B, the set of all finite length binary strings is countable, so there must exist a bijection g : B → ℕ. Now, define a decision function f : B → {0, 1} as follows:

f(s) = the opposite of f_{g(s)}(s)

Then f is different from all f_{i}’s because for all i ∈ ℕ, h differs from f_{i} on string s = g^{−1}(i).

Alternative Solution 3:

One can also argue, as some students did, that F is uncountable by showing the bijection between F and the set, P (B), of all subsets of B. The bijection associates with f ∈ F a set of strings b ∈ B s.t. f(b) = 1. Then, since by part (a) there is a bijection between B and ℕ, there must be a bijection between P (B) and P (ℕ). By transitivity of bijective relation between sets, there is a bijection then between F and P (ℕ). Hence F is uncountable.

□

(e) A function is computable if there is a computer program that computes it. From your answers to the previous parts, prove that there is a decision function that is not computable.

Solution.

Since there are only countably many computer programs, but uncountably many decision functions, there can be no surjection from the set of computer programs to the set of decision functions (In fact, this means that there is more decision functions than computer programs). In particular, if we associate a computer program to a decision function which this program is computing^{1}, this association is not a surjection either. Therefore there must be some decision function which is not computed by any computer program.

□

1If a program is not computing any decision function, associate it with a trivial decision function f(b) = 0, for all finite bit strings b.