Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science March 10, 1995 Professors Mauricio Karchmer and Ron Rivest

Problem Set 4 Solutions

Problem 4-1. Prove that any countable cover of an uncountable set contains an uncountable set. (Recall that a cover of X is a collection of sets whose union is X).

Proof. To prove this it is enough to show that a countable union of countable sets is countable. Why? If we have a countable cover of an uncountable set X where each of the sets is countable, then the union of all of the sets in the cover is countable. But X is uncountable, a contradiction.

To show that a countable union of countable sets is countable note that any element in the union can be denoted by a_{i,j}, i.e. the ith element of the jth set. So we have an surjective function f : ℕ × ℕ → X by f(i, j) = a_{i,j}. But we know that ℕ × ℕ is countable so we have a surjection from a countable set to X. Thus X is countable.

Problem 4-2. Let A and B be finite sets. How many functions are there from A to B? That is, what is the cardinality of {f | f : A → B}?

Proof. It is |B|^{|A|}. Why? To totally specify the function it is enough to give its value at each element of A. There are |B| choices for each element of A and so the total number of functions is |B|^{|A|}.

Problem 4-3. A certain hotel has 90 rooms and 100 guests. We wish to give keys to the guests so that any subset of 90 guests collectively hold keys to all of the rooms. What is the smallest number of keys that we have to distribute?

We need 990 keys.

Proof. If we give all of the keys to each of 11 guests, then any subset of 90 guests must contain one of these “special” guests who can open all of the rooms. We must now show that it can’t be done with fewer keys. Let g_{i} for i = 1, …, 90 be the number of guests that have a key to room i. We know that ∑ g_{i} ≤ 989 and so some g_{k} must be less than 11 (If not then the sum would be greater than 990). In other words fewer than 11 guests have keys to this room. So if we pick all of the guests that don’t have keys to this room then we have at least 90 guests who can’t open room k.

Problem 4-4. Recall that the composition g ∘ f of two functions f and g is defined by (g ∘ f)(x) = g(f(x)).

(a) Show that if f : A → B and g : B → C are both surjections, then (g∘f) : A → C is also a surjection. Let c ∈ C. Since g is a surjection, there must exist b ∈ B such that g(b) = c. Similarly there must exist a ∈ A such that f(a) = b. Thus (g ∘ f)(a) = c and g ∘ f is a surjection.

(b) Show that if f : A → B and g : B → C are both bijections, then (g ∘ f) : A → C is also a bijection. We already know that g∘f is a surjection. To prove it is injective, let (g∘f)(x) = (g ∘ f)(y). Then it must be that f(x) = f(y) since g is injective. But since f is also injective x = y.

(c) If g ∘ f is a bijection, what can you conclude about f and g? g must be surjective. If not then there will be elements of C that are not g(f(a)) for any a. f must be injective. If there exist x and y with x ≠ y such that f(x) = f(y) then g(f(x)) = g(f(y)). g isn’t necessarily injective and f isn’t necessarily surjective. Consider f : {1, 2} → {1, 2, 3} where f(x) = x and g : {1, 2, 3} → {1, 2} where g(1) = g(3) = 1 and g(2) = 2. g ∘ f is a bijection but f isn’t surjective and g isn’t injective.

Problem 4-5. For any rooted binary tree, let d(x) denote the depth of node x in the tree. (The depth of the root is 0.) Prove that

∑_{leaves x} 2^{−d(x)} ≤ 1

where the sum is over all leaves in the tree.

Proof. Let us prove this for a full binary tree (every node either has 0 or 2 children). We will do this by induction on the maximum depth of the tree.

Base Case: The maximum depth is 0. In this case we just have one node of depth 0 (which is a leaf) and so the left hand side if the sum is 2^{0} = 1.

Inductive Step: Assume the inequality holds for all trees with maximum depth less than k. We are now given a full binary tree T with maximum depth k. Remove the root giving 2 full binary trees T_{1} and T_{2}. The depth of every node in T_{1} and T_{2} is one less than in T and so we can apply the inductive hypothesis and assume that:

∑_{leaves in T_{1}} 2^{−d(x)} ≤ 1

and

∑_{leaves in T_{2}} 2^{−d(x)} ≤ 1

But the leaves in T are just the union of the leaves in T_{1} and T_{2}. Note also that the depths of these leaves in T are one more than the depths in T_{1}. Thus 2^{−(depth in T)} = 1/2 × 2^{−(depth in T_{1})}. Therefore we divide both expressions above by 2 to get

∑_{leaves in T} 2^{−d(x)} ≤ 1/2 + 1/2 = 1