[logic1] Problem 1 [12 points] Source: victor Topics: Logic Transcribe the following arguments into logic, and for each argument, show that it is valid, or give a counterexample. State clearly what your propositions and/or predicates are.

(a) [3 points] Either Jane or Bob ate the cheesecake. Neither Bob nor David drank the soda. If Bob ate the cheesecake, he also drank the soda. So Jane ate the cheesecake.

(b) [3 points] Unless we get up early, we won’t make it to the game on time. If we go to sleep early then we will get up early. Therefore, if we go to sleep, we will get to the game on time.

(c) [3 points] Suppose all circles are round, no squares are round, and some triangles are round. Then some circles are triangles.

[logic2]

Problem 2 Source: victor Topics: Logic Prove which of the following statements imply which other statements. (This includes showing that a statement does not imply another.)

1. ∀x(P (x) ⟹ Q(x))

2. ∃xQ(x) ⟹ ∀xP (x)

3. ∃xQ(x) ⟹ ∃xP (x)

4. ∃x(Q(x) ⟹ P (x))

5. ∀x¬P (x) ∨ ∃xQ(x)

6. ∃xP (x) ∨ ∀x¬Q(x)

[induction1]

Problem 3 Source: David Gries’ book

Topics: Induction, trees

A full binary tree is a binary tree in which each node has either 0 children or 2 children. Prove by induction that all non-empty full binary trees have an odd number of nodes.

Solution Base case: 1 node, odd.

Induction: Assume all full binary trees of height ≤ n have an odd number of nodes. Now, consider a full binary tree of height n + 1. Since the height is greater than 0, the root node must have two children, A and B, which must themselves be full binary trees of height ≤ n. The whole tree has 1 + |A| + |B| nodes which, by the induction hypothesis, is odd+odd+odd=odd. This proves the theorem.

Problem 4 [12 points] Source: s99 ps3

Topics: Induction, Graphs, Recursive Definitions

This problem concerns Hamiltonian circuits in n-cubes. A Hamiltonian circuit in a graph is a circuit traversing every vertex in the graph exactly once. The n-cube is defined on page 448 of Rosen (p. 441 in ed. 3). (Rosen also uses the name Q_{n} for an n-cube.) However, the following recursive definition of an n-cube is equivalent to the one given in Rosen, but may simplify your solutions. A 0-cube is a single vertex. An (n + 1)-cube consists of two n-cubes with corresponding vertices joined by edges. For example, a cube is two squares with corresponding corners joined.

(a) Draw a 4-cube. [2 points]

Solution

(b) In your drawing, highlight a Hamiltonian circuit. [2 points]

Solution The dotted edges in the diagram above form a Hamiltonian circuit.

(c) Use induction on n to prove that an n-cube has a Hamiltonian circuit for all n ≥ 2. [8 points]

Solution The proof is by induction. Let P (n) be the proposition that an n-cube has a Hamiltonian circuit. In the base case, P (2) is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an n-cube has a Hamiltonian circuit to prove that an (n + 1)-cube has a Hamiltonian circuit. Regard an (n + 1)-cube as two n-cubes with corresponding vertices joined. The first n-cube has a Hamiltonian circuit H by induction, and there is a matching Hamiltonian circuit H′ in the second n-cube.

Take an edge (u, v) ∈ H and the corresponding edge (u′, v′) ∈ H′. We can construct a Hamiltonian circuit in the (n + 1)-cube by starting at vertex u, traversing the circuit H all through the first n-cube until reaching vertex v, crossing the edge (v, v′), traversing the circuit H′ all through the second n-cube until reaching vertex u′, and then crossing the edge (u′, u).

Problem 5 Source: s97 ps3 Topics: Structural Induction, Recursive Definition (Binary Trees) Recall that we defined binary trees in class as either

• A node with no children.

• A node with a left child that is a binary tree, and no right child.

• A node with a right child that is a binary tree, and no left child.

• A node with left and right binary-tree children.

Consider the following recursive definition of the height of a binary tree:

• The height of a node with no children is 0

• The height of a tree on a node with children is one more than the maximum of its children’s heights.

Prove that a tree of height h contains at most 2^{h+1} − 1 nodes.

Solution The proof is by structural induction on the definition of binary tree. Base Case: A tree consisting of one node with no children has height h = 0. So 1 ≤ 2^{h+1} − 1 = 1. Inductive Steps: We have three cases corresponding to the three cases of the definition:

• If the tree T is a node with a left child but no right child, let L be the left child binary tree and let h be its height. By inductive hypothesis, the tree L has at most 2^{h+1} − 1 nodes. The height of tree T is h + 1, and the number of nodes in T is at most 1 + 2^{h+1} − 1 = 2^{h+1} < 2^{h+2} − 1.

• If the tree T is a node with a right child but no left child, it is analogous to the previous case.

• If the tree T is a node with both a left and right child L and R, then let h_{1} and h_{2} be the heights of the trees L and R respectively. Let also h be the maximum of h_{1} and h_{2}. By inductive hypothesis the trees L and R have at most 2^{h_{1}+1} − 1 ≤ 2^{h+1} − 1 and 2^{h_{2}+1} − 1 ≤ 2^{h+1} − 1 nodes. So, the number of nodes in T is at most 1 + (2^{h+1} − 1) + (2^{h+1} − 1) = 2^{h+2} − 1 = 2^{h′+1} − 1 nodes, where h′ = h + 1 is the height of T.

[induction4] Problem 6 Source: f94 ps3 Topics: Structural Induction (Binary Tree) Let us associate a “weight” w(x) = 2^{−d} with each leaf of depth d in a binary tree T. Use the structural induction definition of a binary tree on page 94 of Handout clrchap5 to prove the Kraft Inequality: ∑_{x} w(x) ≤ 1, where the sum is taken over all leaves x in T. (Beware of “build-up error” [MR, p. 173].) Solution not done yet.

Problem 7 [10 points] Source: s97 ps3

Topics: Fibonnacci Numbers, Strong Induction

Show that the Fibonnacci number f_{n} satisfy f_{n} ≤ 2^{n} using strong induction.

[[[Nancy additions: I suggest this problem as a candidate for a structured proof problem, where we provide the proof and they fill in the reasons, line by line (or, some selected reasons).

E.g.:

Let P (n) = F_{n} ≤ 2^{n} Prove: ∀n ≥ 0(P (n))

1. (Base) P (0) F_{0} = 0 ≤ 2^{0}

2. (Base) P (1) F_{1} = 1 ≤ 2^{1}

3. (Inductive step) ∀n ≥ 1[(∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] 1. Fix n ≥ 1

2. (∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)

1. Assume ∀i, 0 ≤ i ≤ n(P (i))

2. P (n + 1) 1. F_{n} ≤ 2^{n} Inductive hypothesis 3.2.1

2. F_{n−1} ≤ 2^{n−1} Inductive hypothesis 3.2.1
3. F_{n+1} = F_{n} + F_{n−1} Definition of Fibonacci numbers
4. F_{n+1} ≤ 2^{n} + 2^{n−1} Plug the inequalities into the equation
5. F_{n+1} ≤ 2^{n+1}

1. 2^{n−1} ≤ 2^{n} Algebra

2. 2^{n} + 2^{n−1} ≤ 2^{n+1} Algebra

3. QED Algebra (3.3.4 and 3.3.5.2)

6. QED Definition of P (n + 1)

3. QED Implication

3. QED UG

4. QED Strong induction

]]]

Solution not done yet.

Problem 8 Source: s97 ps3

Topics: Fibonnacci Numbers, Well Ordering, Strong Induction

What quantities of money can be formed from just dimes and quarters?

Solution : Answer A. The answer is 10 and all multiples of five greater then or equal to 20.

We can prove this by strong induction on n where n = 5k for k = 2 and k ≥ 4.

: Answer B. First of all notice that if we can make n cents using dimes and quarters then n = 10a + 25b = 5(2a + 5b) for some a and b, and therefore n must be a multiple of 5. We can make 10 cents using one dime, and we cannot make neither 5 nor 15 cents. We claim that we can make any other quantities n such that n ≥ 20 and 5|n. In other words, we can make 20 + 5k cents for all k ≥ 0. We will prove this statement first by strong induction and then by well-ordering.

(a) Prove by strong induction that these and no other quantities can be formed.

Solution : Answer A. Base Cases: As base cases we take all n ≤ 25. Clearly, if n ≤ 25 then we can make 10 from one dime, 20 from two dimes, and 25 from one quarter.

Inductive Step: Let n ≥ 25 and assume that for all 25 < m < n we can make m cents out of dimes and quarters. Show that we can make n cents out of dimes and quarters.

If n > 25 then we know that n − 10 > 15 and by the base cases and the inductive hypothesis, we know that we can make n − 10 cents using only dimes or quarters. we can therefore make n cents by adding a dime, so we can make n cents out of dimes and quarters.

This completes the inductive step, so we know we can make n cents out of dimes and quarters where n = 10 or n ≥ 20 and n is a multiple of 5.

Now, we need to show that we cannot make any other amounts using only dimes or quarters. Take first the case of 5 cents: We clearly cannot make 5 cents because dimes and quarters are both larger than 5 cents. We also cannot make 15 cents, by inspection.

We cannot make amounts that are not divisible by 5 because any combination of dimes, d, and quarters, q, will give us c = 10d + 25q = 5(2d + 5q), which is clearly a multiple of 5 when d and q are natural numbers.

: Answer B. We prove that we can make 20 + 5k cents using dimes and quarters by strong induction on k.

Base cases (k = 0, 1) We can make 20 and 25 cents using two dimes and using one quarter respectively.

Inductive Step (k ≥ 2): Assume we can make 20 + 5h cents for all h < k. In particular we can make 20+5(k−2) cents using dimes and quarters. Using one more dime, we can also make 20+5(k−2)+10 = 20+5k cents, completing the induction proof.

(b) Prove the same thing by well ordering

Solution : Answer A. Let’s now prove the same thing using well-ordering.

To make the statement of the problem clearer we introduce some notation. Let P (n) be the predicate “(n = 10) ∨ (5|n ∧ n ≥ 20)′′, and let Q(n) be the predicate “we can make n cents using dimes and quarters”.

We claim that for all n, P (n) ↔ Q(n), i.e., we can make n cents if and only if n is 10 or a multiple of 5 not smaller then 20.

This time we will prove ∀n.P (n) → Q(n) and ∀n.Q(n) → P (n) separately.

We first prove that ∀n.P (n) → Q(n). Let S be the set of all n such that P (n) and ¬Q(n). We will show that S is empty. Assume for contradiction that S is not empty. By the well-ordering axiom, S has a minimum element m. Since P (m) is true, m is a multiple of 5, but we cannot make m cents using dimes and quarters. Notice that m must be greater then or equal to 30 because 10, 20 and 25 cents can be made using respectively 1, 2 dimes or a quarter. Let n = m−10. We cannot make n cents using dimes and quarters because otherwise we could also make m = n+10 cents using one more dime. So, Q(n) is false. Moreover, m ≥ 30 and therefore n ≥ 20. Since n is a multiple of 5, P (n) is true and n is in the set S contradicting the fact that m was the minimum element.

We now prove that ∀n.Q(n) → P (n). Let T be the set of all n such that Q(n) and ¬P (n). We will show that T is empty. Assume for contradiction that T is not empty. By the well-ordering axiom, T has a minimum element m. We have Q(m), so we can make m cents using dimes and quarters. We distinguish two cases:

• if we used at least one dime to make m, then we can also make n = m − 10 cents using one less dime, i.e., Q(n). Moreover, ¬P (n) because otherwise also m = n + 10 satisfies ≠ P (m) (if we add 10 to a multiple of 5 it will still be a multiple of 5). So, n ∈ T contradicting that m is minimum.

• if we didn’t use any dime to make m, then m = 25h and P (m) which contradicts m ∈ T.

: Answer B. We prove that we can make 20+5k cents using dimes and quarters by well-ordering. Let S be the set of all k such that we cannot make 20+5k cents using dimes and quarters and assume for contradiction that S is not empty. By well-ordering, S has a minimum element m. m cannot be 0 or 1 because we can make 20 and 25 cents. Therefore, m ≥ 2 and m − 2 ≥ 0. We claim that m − 2 is in S. To prove this, notice that if we could make 20 + 5(m − 2) = 20 + 5m − 10 cents using dimes and quarters, then we could make also 20 + 5m cents using one more dime. But, this is impossible because m ∈ S. So, m − 2 ∈ S and m is not the minimum.

Problem 9 [12 points] Source: s97 ps3

Topics: False Proofs, Well Ordering, Induction

Find the flaws in the following “proofs.”

(a) CLAIM: a^{n} = 1 for all nonnegative integers n, whenever a is a nonzero real number.

BASIS STEP: a^{0} = 1 is true by the definition of a^{0}.

INDUCTIVE STEP: Assume that a^{k} = 1 for all nonnegative integers k with k ≤ n. Then note that a^{n+1} = \frac{a^{n}·a^{n}}{a^{n−1}} = \frac{1·1}{1} = 1.

Solution The flaw is that we should prove both n = 0 and n = 1 as bases cases because the inductive step uses the previous two values of n. Clearly a^{1} = 1 is not true, unless a = 1, and therefore the proof is wrong.

(b) CLAIM: \sqrt{2} is rational.

PROOF: Well-ordering. Let S be the set of all rational numbers greater than or equal to \sqrt{2}. This set contains a least element r by well-ordering. If this element is not \sqrt{2}, then there is another rational element between \sqrt{2} and r (by denseness of the rationals), implying r is not the smallest, a contradiction. Thus we must have r = \sqrt{2}.

Solution The flaw is that the well-ordering principle does not hold for the rationals, so we cannot use it to conclude that the above set has a minimum.

(c) CLAIM: every number can be described in a phrase of less than eighty characters.

PROOF: Well-ordering. Let S be the set of numbers that cannot be described in a phrase of less than eighty characters. If it is nonempty, it contains a smallest element. This is “The smallest number that cannot be described in less than eighty chracters.” This is a description of that number in less than eighty characters, a contradiction. Since the assumption that S was nonempty yields a contradiction, S must be empty and the claim is proved.

Solution The flaw in the above proof is that the set of numbers that can be described in less than eighty characters, is not a well-defined set.

Problem 10 Source: f99 ps4

Topics: Posets, well ordering

Let R be the lexicographic ordering of strings of symbols from a totally ordered alphabet as defined in Rosen p. 417.

(a) Prove that R is a total order.

Solution We first show that R is a partial order. Reflexivity is clear from the definition. To show antisymmetry, suppose that a_{1} … a_{m} < b_{1} … b_{n}, and let t = min(m, n). This means that either a_{1} … a_{t} = b_{1} … b_{t} and m < n, so that b_{1} … b_{n} ≮ a_{1} … a_{m}, or else a_{1} … a_{t} < b_{1} … b_{t}, so that b_{1} … b_{t} ≮ a_{1} … a_{t} and hence again b_{1} … b_{n} ≮ a_{1} … a_{m}. Finally for transitivity, suppose that a_{1} … a_{m} < b_{1} … b_{n} < c_{1} … c_{p} . Let t = min(m, n), r = min(n, p), s = min(m, p), and l = min(m, n, p). Now if a_{1} … a_{l} < b_{1} … b_{l} < c_{1} … c_{l} then clearly a_{1} … a_{m} < c_{1} … c_{p}. Otherwise, without loss of generality we may assume that a_{1} … a_{l} = b_{1} … b_{l}. If l = t then m < n and m ≤ p. Furthermore, either b_{1} … b_{r} < c_{1} … c_{r} or b_{1} … b_{r} = c_{1} … c_{r} and n < p. In the former case, if r > l, then since p > m we have a_{1} … a_{m} < c_{1} … c_{p}, whereas if r = l then a_{1} … a_{l} < c_{1} … c_{l}. In the latter case, a_{1} … a_{s} = c_{1} … c_{s} and m < p, so again a_{1} … a_{m} < c_{1} … c_{p}. If l < t, then we must have b_{1} … b_{l} < c_{1} … c_{l}, whence a_{1} … a_{l} < c_{1} … c_{l}. Finally, the fact that R is a total order follows trivially from the definition of a lexicographic order and noticing that the strings of symbols are taken from a totally ordered alphabet.

(b) Prove that neither R nor R^{−1} is a well-ordering.

Solution Consider the alphabet {a, b} with a ⪯ b. Then R is not a well ordering since {b, ab, aab, aaab, aaaab, … } has no least element. Moreover, R^{−1} is not a well-ordering since {a, aa, aaa, aaaa, … } has no least element.

[wellordering1]

Problem 11 Source: f95 ps3

Topics: Well Ordering (gcd, lcm)

The least common multiple of two natural numbers, m and n is defined to be the smallest natural number k such that m|k and n|k. It is denoted by lcm(m, n). Prove that every pair of natural numbers has a least common multiple. Using unique factorization, show that a · b = gcd(a, b) · lcm(a, b).

Solution Let m and n be any two natural numbers. Let M be the set of multiples of m and N the multiples of n. Consider M ∩ N. It is nonempty since it contains mn. By the well-ordering principle it contains a least element which is the least common multiple of m and n. Hence every pair of natural numbers has a least common multiple.

Let a = ∏_{i}p_{i}^{α_{i}} and b = ∏_{i}p_{i}^{β_{i}} where p_{1}, p_{2} … are the primes in increasing order. Following Theorem 7.12

in Handout 13, Notes 4, it was shown that gcd(a, b) = ∏_{i}p_{i}^{min(α_{i},β_{i})}. By an identical argument it can be seen

that lcm(a, b) = ∏_{i}p_{i}^{max(α_{i},β_{i})}. Now, from the fact that for any α and β, α + β = max(α, β) + min(α, β), it follows that a · b = gcd(a, b) · lcm(a, b).

Problem 12 Source: f94 ps3 Topics: Graphs, Well Ordering Prove that the vertices of an undirected graph can be colored either red or blue such that at least half of the neighbors of every red vertex are blue and at least half of the neighbors of every blue vertex are red. ( Hint: Associate a value with each coloring, and use well ordering on the set of possible values.) [[[I can’t figure this one out after 5 minutes...]]] [wellordering3] Problem 13 Source: f94 ps3 Topics: Recursive Definitions, Strong Induction, Well Ordering, Weak Induction Define u_{n} recursively by

u_{0} = 2, u_{1} = 3, u_{n} = 3u_{n−1} − 2u_{n−2} for n ≥ 2 .

Prove that u_{n} = 2^{n} + 1 using

(a) strong induction,

(b) well ordering,

(c) weak induction. Of course, the algebra in each of these three proofs will be similar, but the logic will differ. Do not use the fact that these three induction methods are equivalent.

Problem 14 Source: s98 ps3

Topics: Simple Graphs, Induction, Well Ordering, Graph Coloring

Definition: A simple graph, G, has inherited degree d ≥ 0 if and only if

(i) every vertex of G has degree ≤ d, or (ii) there is a vertex v ∈ G of degree ≤ d, and the subgraph of G obtained by removing v has inherited degree ≤ d.

(a) Prove that W_{n} has inherited degree 3.

Solution We use the induction on n. Let P (n)::= W_{n} has inherited degree 3.

Base Case: W_{3} has four vertices of degree 3 and it has inherited degree 3 by definition (i).

Inductive Step: Assume P (n) is true, we need to prove P (n + 1). W_{n+1} has n + 1 vertices of degree 3 and 1 vertex of degree n + 1. The graph G obtained by removing a vertex of degree 3 has n − 2 vertices of degree 3, 2 vertices of degree 2 and 1 vertex of degree n. We can also obtain G by removing a edge between two vertices of degree 3 in W_{n}. Since W_{n} has inherited degree 3 by inductive hypothesis and removing an edge does not increase the degree of vertices, G has inherited degree 3. Then, by definition (ii), W_{n+1} has inherited degree 3.

Therefore, we prove that W_{n} has inherited degree 3 for ∀n ≥ 3.

(b) Prove that a tree has inherited degree 1.

We use the definition of tree in Rosen, 8.1: a tree is a connected undirected graph with no simple circuits. Also, we only consider trees with a finite number of vertices.

Solution We need to prove two facts here. First we have to prove that every tree with at least two vertices has a leaf (a leaf is a vertex of degree one). Then we need to show that the subgraph constructed by removing one leaf is still a tree.

First, let’s prove that every tree with at least two vertices has a leaf. Let T be a tree, and let P be a longest simple path in T. In a finite graph, a path of length greater than or equal to the the number of vertices must visit some vertex more than once. So a simple path must be shorter than the number of vertices. Therefore in any finite graph there must be longest simple path. (We’re using the Well-ordering principle here, taking the least element of {|V | − k : k is the length of a simple path}.)

Suppose P = (v_{1}, v_{2} …, v_{k}), we claim that v_{1} is a leaf. For if not, there will be an edge {v, v_{1}} in T where v ≠ v_{2}. The vertex v cannot occur in P, for otherwise this creates a cycle, which contradicts that the graph is a tree. Therefore, P′ = (v, v_{1}, v_{2} …, v_{k}) is also a simple path in the tree and P′ is longer than P. But this is a contradiction because we have assumed that P is the longest path in the tree. As a result, a tree with 2 or more vertices has to have a leaf.

Second, let’s prove that the subgraph constructed by removing one leaf is still a tree. From the definition given in the book (cf. Rosen p531), a tree is a connected undirected graph with no simple circuits. Removing a leaf from a tree does not create any circuit. Also, since the leaf has degree 1, it is not connecting any other two vertices in the tree. Therefore, after removing the leaf, no vertices get disconnected. In other words, the subgraph is still connected. Since the subgraph is a connected undirected graph with no simple circuits, it is also a tree.

Since every tree has a leaf(vertex with degree 1) and the subgraph is still a tree after removing a leaf, we can apply the same method in the previous part to show that a tree has inherited degree 1.

(c) Prove that if a graph has inherited degree d, then it is (d + 1)-colorable.

Solution We use induction on the number of vertices in a graph to prove this fact.

Let P (n)::= “∀d > 0, any n-vertex graphs with inherited degree d is (d + 1) colorable.”

Base Case: n = 1. There is only one 1-vertex graph. And it is obviously (d + 1) colorable (∀d > 0).

Inductive Step: Assume that P (n) is true, we need to prove P (n + 1) is true. Given any (n + 1)-vertex graph G with inherited degree d for any d > 0, there are 2 possible cases:

1. All vertices in G has degree ≤ d. Then it is (d + 1)-colorable, as proved in the lecture.

2. There is a vertex v ∈ G of degree ≤ d, and the subgraph G′ obtained by removing v has inherited degree d. Since G′ has n nodes and has inherited degree d, by inductive hypothesis G′ is (d + 1) colorable. Now consider the vertex v. Since it has degree ≤ d, it has at most d neighbors and therefore it can be colored with the (d + 1)^{st} color which is different from all of its neighbors.

Therefore, by induction, every graph with inherited degree d is (d + 1)-colorable.

(d) For every n > 0, describe an example of a graph which does not have inherited degree n, but which is 2-colorable.

Solution An example would be K_{n+1,n+1}. Every vertex in K_{n+1,n+1} has degree n + 1. Therefore, it does not have inherited degree n. However, it is 2-colorable since every complete bipartite graph is 2-colorable.

[pigeonhole1]

Problem 15 [10 points] Source: Kyle’s brain, inspired by a trip to the Galleria

Topics: Pigeonhole principle

For their annual convention, the members of the MIT Antisocial League rent out the cafeteria at the CambridgeSide Galleria. The cafeteria is an n × n grid, with exactly one table and a single associated chair at each point. A chair can be positioned around its table to face in one of four directions, corresponding to the axes of the grid.

Due to space considerations, every attendee must sit at a chair. But, since this is the Antisocial League, no seated person can directly face another occupied table (i.e., there can be no one sitting at a table in a person’s direct line of sight). Prove that this must occur if 4n + 1 members attend.

Solution We use the pigeonhole principle to prove the theorem. Orient a representation of the grid in some canonical way with one axis pointing left-right, and the other pointing up-down.

There are four directions in which people can face. As a result, by the generalized pigeonhole principle, at least n + 1 people must be facing in some direction. Without loss of generality, assume this is downwards.

Create n pigeonholes from the columns of the grid. By the PP, if there are n+1 attendees facing downwards, at least two must be in the same column, so clearly one must be directly facing another occupied table.

It is likely that equality is not achieved (which would be proved by demonstrating an arrangement of 4n people in which no one directly faced another occupied table). This suggests a stronger theorem can be proven. The best we can do so far is 4n − 4; try to figure out such a solution.

[[[Students can get stuck on the problem above if they don’t see the trick. It would be nice to at least tell them to use pigeonhole. But then they can still get stuck if they don’t think of first using the 4 directions as the holes (I tried to use the rows or columns). Wouldn’t it be nice to give out hints in return for points...]]] [counting1] Problem 16 Source: Nancy/Carl/Victor Topics: Counting, Injections, Surjections Which of the following is the cardinality of the set of all surjections from a set A, where |A| = n, and B, where |B| = m.

(a) m^{n}

(b) \frac{m!}{(m−n)!}

(c) \binom{n}{m}m^{n−m}m!

(d) None of the above. Solution (d) None of the above.

[counting2]

Problem 17 Source: Nancy/Carl Topics: Counting Suppose you have a collection of 41 balls, of which you know that 40 have normal weight and one is abnormal — either heavy or light, but you don’t know which. Is there a way to determine which ball is abnormal with 4 weighings? If so, demonstrate the approach, otherwise prove that it is impossible.

Solution No. The 4 weighings can only generate 81 distinct outcomes. However, any of the 41 balls can be the abnormal one and the abnormal one can be either light or heavy, i.e., 82 distinct outcomes.

[summations1]

Problem 18 Source: Kyle’s brain, modified from PS6 n4

Topics: Summations, asymptotics

Prove that the “average” number of perfect square^{1} divisors of a number of size n is bounded from above by a constant. More formally, let t(n) be the number of divisors of the number n that are themselves perfect squares, and let

T (n) = \frac{1}{n} ∑_{j=1}^{n} t(j)

be the average number of perfect square divisors of all numbers less than or equal to n. Show that there exists a constant c such that for all n, T (n) ≤ c.

Hint: Let the function f(i, j) = 1 if i^{2} is a divisor of j, and 0 otherwise. What do the row and column sums of f(i, j) mean?

Solution Consider the image of the function f(i, j) as a matrix whose rows and columns correspond to values of i and j respectively; that is, element (i, j) of the matrix denotes whether or not i^{2} divides j.

j
f(i, j) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
i 2 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 ⋯
3  0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
⋮  ⋮

Notice that the sum of each column j corresponds to the number of perfect square divisors of the number j and the sum of each row i corresponds to the number of multiples of the number i^{2}. As a result, the number of multiples of i^{2} between 1 and n can be compactly represented as ⌊n/i^{2}⌋.

It follows that

T (n) = \frac{1}{n} ∑_{j=1}^{n} t(j)

= \frac{1}{n} ∑_{i=1}^{⌊\sqrt{n}⌋} ∑_{j=1}^{n} f(i, j)

= \frac{1}{n} ∑_{i=1}^{⌊\sqrt{n}⌋} ⌊\frac{n}{i^{2}} ⌋

1x is a perfect square if there is some natural number y such that y^{2} = x.

T (n) can then be bounded from above as follows:

T (n) ≤ \frac{1}{n} ∑_{i=1}^{⌊\sqrt{n}⌋} \frac{n}{i^{2}}

= ∑_{i=1}^{⌊\sqrt{n}⌋} \frac{1}{i^{2}}

≤ 1 + ∫_{1}^{√\overline{n}} \frac{1}{x^{2}} dx
= 1 + \frac{\sqrt{n} − 1}{\sqrt{n}} ≤ 2

[recurrences1] Problem 19 Source: Carl... Topics: Recurrences and summations

(a) Solve the following homogeneous recurrence, assuming that T (0) = 1 and T (1) = 1.

T (n) = T (n − 1) − \frac{1}{4}T (n − 2)

Solution I think the answer here is:

T (n) = (1/2)^{n} + n · (1/2)^{n}

(b) Find a closed-form solution for the infinite sum:

∑_{n=0}^{∞} T (n)

Solution we just sum the terms and get 4.

[recurrences2] Problem 20 [12 points] Source: Kyle Topics: Recurrences

(a) [3 points] Iterate the following recurrence to find a pattern:

T (n) = a_{0}T (n/b_{0}) + a_{1}T (n/b_{1}) + f(n)

where T (n/(b_{0}^{i}b_{1}^{m−i})) = c for all i ∈ {1, …, m} with a_{{0,1}}, b_{{0,1}}, and c all constant. Demonstrate a non-recurrent formula that may have summations in it. Solution Denote g(x) = T (n/x), so g(b_{0}^{i}b_{1}^{m−i}) = c. Then:

T (n) = a_{0}g(b_{0}) + a_{1}g(b_{1}) + f(n)
= a_{0}^{2}g(b_{0}^{2}) + 2a_{0}a_{1}g(b_{0}b_{1}) + a_{1}^{2}g(b_{1}^{2})

+f(n) + [a_{0}f(n/b_{0}) + a_{1}f(n/b_{1})]

= a_{0}^{3}g(b_{0}^{3}) + 3a_{0}^{2}a_{1}g(b_{0}^{2}b_{1}) + 3a_{0}a_{1}^{2}g(b_{0}b_{1}^{2}) + a_{1}^{3}g(b_{1}^{3})

+f(n) + [a_{0}f(n/b_{0}) + a_{1}f(n/b_{1})] + [a_{0}^{2}f(n/a_{0}^{2}) + 2a_{0}a_{1}f(n/(b_{0}b_{1})) + a_{1}^{2}f(n/a_{1}^{2})] ⋮

= ∑_{i=0}^{m} (\binom{m}{i}a_{0}^{i}a_{1}^{m−i}g(b_{0}^{i}b_{1}^{m−i}))

+ ∑_{j=0}^{m} ∑_{i=0}^{j} (\binom{j}{i}a_{0}^{i}a_{1}^{j−i}f(n/(b_{0}^{i}b_{1}^{j−i})))

= c(a_{0} + a_{1})^{m}

+ ∑_{j=0}^{m} ∑_{i=0}^{j} (\binom{j}{i}a_{0}^{i}a_{1}^{j−i}f(n/(b_{0}^{i}b_{1}^{j−i})))

(b) [3 points] Find asymptotically tight bounds for the following recurrence:

T (n) = 8T (n/2) + n^{3} (log n)^{2}

given that T (1) = 1. You may assume n is a power of 2. Note that the master theorem does not apply to this recurrence. Solution Use the first part, with a_{0} = 4, a_{1} = 4, b_{0} = b_{1} = 2, m = log n, c = 1, and f(n) = n^{3} log^{2} n. (Note that we can’t take a_{0} = 0 or a_{1} = 0, since 0^{0} is indeterminate; we could, however, have used any other a_{0} and a_{1} such that a_{0} + a_{1} = 8.)

Plugging and chugging:

T (n) = 4T (n/2) + 4T (n/2) + n^{3} log^{2} n
= 1(4 + 4)^{log n} + ∑_{j=0}^{log n} ∑_{i=0}^{j} (\binom{j}{i}4^{j}(n/2^{j})^{3} log^{2}(n/2^{j}))
= n^{3} + ∑_{j=0}^{log n} (8^{j}(n/2^{j})^{3} log^{2}(n/2^{j}))
= n^{3} + n^{3} ∑_{j=0}^{log n} (log^{2}(n/2^{j}))
= n^{3} + n^{3} ∑_{j=0}^{log n} (log^{2} n − 2j log n + j^{2})
= n^{3} + n^{3} (log^{3} n + log^{2} n) − 2n^{3} log n ∑_{j=0}^{log n} j + n^{3} ∑_{j=0}^{log n} j^{2}
= n^{3} + n^{3} (log^{3} n + log^{2} n) − n^{3} (log^{3} n + log^{2} n) + n^{3} ∑_{j=0}^{log n} j^{2}
= n^{3} + n^{3} ∑_{j=0}^{log n} j^{2}

We must bound the last part, ∑_{x=0}^{log n} x^{2}, by the integral method:

∑_{x=0}^{Y} x^{2} ≤ ∫_{0}^{Y} (x + 1)^{2}dx
= \frac{1}{3}(x + 1)^{3}|_{0}^{Y}
= \frac{1}{3}(Y + 1)^{3} − \frac{1}{3}

and

∑_{x=0}^{Y} x^{2} ≥ ∫_{0}^{Y} x^{2}dx
= \frac{1}{3}x^{3}|_{0}^{Y}
= \frac{1}{3}Y^{3}

so the last term is asymptotally bounded by n^{3} log^{3} n; thus, the entire summation is Θ(n^{3} log^{3} n).

(c) Find a good lower bound for the following recurrence:

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

in terms of m and n, given that T (n/(2^{i}4^{m−i})) = T (n/(2^{2m−i})) = 1. Hint: Recall that ∑_{i=0}^{n} ix^{i} = (x − (n + 1)x^{n+1} + nx^{n+2})/(1 − x)^{2}.

Solution We use the first part, with c = 1, a_{0} = 2, a_{1} = 3, b_{0} = 2, and b_{1} = 4.

T (n) = 5^{m} + ∑_{j=0}^{m} ∑_{i=0}^{j} (\binom{j}{i}2^{i}3^{j−i} log(n/(2^{i}4^{j−i})))
= 5^{m} + ∑_{j=0}^{m} ∑_{i=0}^{j} (\binom{j}{i}2^{i}3^{j−i} (log n − log (2^{j}2^{j−i})))
= 5^{m} + ∑_{j=0}^{m} (5^{j} log n − ∑_{i=0}^{j} (\binom{j}{i}2^{i}3^{j−i} (j + j − i)))
≥ 5^{m} + ∑_{j=0}^{m} (5^{j} log n − ∑_{i=0}^{j} (\binom{j}{i}2^{i}3^{j−i} · 2j))
= 5^{m} + ∑_{j=0}^{m} (5^{j} log n − 5^{j} · 2j)
= 5^{m} + \frac{5^{m+1} − 1}{4} log n − 2 · \frac{5 − (m + 1)5^{m+1} + m · 5^{m+2}}{16}

(d) From the first part, extrapolate a formula (not necessarily a closed form) for the following recurrence: T (n) = a_{0}T (n/b_{0}) + a_{1}T (n/b_{1}) + ⋯ + a_{k}T (n/b_{k}) + f(n)

where T (n/(b_{0}^{i_{0}}b_{1}^{i_{1}} ⋯ b_{k}^{i_{k}})) = c for all ∑_{j=0}^{k} i_{j} = m with a_{{0,1,... ,k}}, b_{{0,1,... ,k}}, and c all constant.

[recurrences3]

Problem 21 [14 points] Source: Kyle

Topics: Homogeneous/inhomogeneous LDE

One of the top ore-cum-food firms, Amalgamated Steel and Spice, has been receiving complaints based on the spreading rumor that one of its products—Happy-O’s with Nuts—actually has rusting iron filings instead of pecan shavings.

During the time in which the X-Files were closed, Mulder and Scully were sent in to investigate. With the help of (the suave) Langley and (the mighty) Frohike, they were able to gather enormous amounts of data concerning a conspiracy against the American people to hide the Truth behind this supposed “mistake.”

(a) [2 points] Our heroes find that a new complaint on any particular day generates one new complaint on the following day and six new complaints on the day after that. Write a recurrence T (n) that represents the number of new complaints on day n.

Solution T (n) = T (n − 1) + 6T (n − 2)

(b) [6 points] On day 1, 0 complaints are generated; on day 2, 30 complaints are generated (i.e., T (1) = 0 and T (2) = 30). Find a closed form for the recurrence in the previous part.

Solution The characteristic equation is x^{2} − x − 6 = 0, whose roots are 3 and −2. The general solution is then of the form T (n) = A3^{n} +B(−2)^{n}. Now we solve for the constants by plugging in the initial conditions: 0 = 3A−2B and 30 = 9A+4B imply that A = 2 and B = 3. So, the final solution is T (n) = 2·3^{n} +3(−2)^{n}.

(c) [6 points] Scully does some more digging and notices that 6n new complaints are filed spontaneously on day n for n ≥ 1. Find new initial conditions based on this new information, show an inhomogeneous recurrence, and find a closed-form solution to it.

Solution The general solution to the inhomogeneous part remains as before; now, however, we have the initial conditions T (1) = 6 and T (2) = 42, and an inhomogeneous part n. We guess a linear solution an + b, and plug in the initial conditions:

an + b = an + b + 6(an + b) + 6n
0 = (6a + 6)n + 6b

So 6a + 1 = 0 ⇒ a = −1 and 6b = 0 ⇒ b = 0 for our particular solution −n. So, we plug in and solve for the constants:

T (1) = 6 = 3A − 2B − 1
T (2) = 42 = 9A + 4B − 2

The solutions to this system are A = 58/15 and B = 23/10. So, our complete solution is T (n) = (58/15)3^{n} + (23/10)(−2)^{n} − n.

[relations1] Problem 22 Source: kdmc Topics: Relations Let the relations R and S be binary relations on the set ℕ of natural numbers. Define R as follows: ∀(a, b) ∈ ℕ×ℕ(a, b) ∈ Riffamod4 = bmod4. Define S as follows: ∀(a, b) ∈ ℕ×ℕ(a, b) ∈ Riff2^{a} = b∧b ≤ 15.

(a) Prove that R is transitive.

Solution ∀ not done yet

(b) Prove that R is symmetric.

Solution ∀a ∈ ℕ we have that amod4 = amod4, as modulo is a defined to be a function (same input yields same output). Thus, ∀a ∈ ℕ(a, a) ∈ R.

(c) Suppose T = R ∩ S. Fully define the relation T.

Solution T = R ∩ S = ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ T iffamod4 = bmod4 = 0 ∧ b ≤ 15.

(d) Let W = S ∘ R. Prove that W is antisymmetric.

Solution We know that ∀(a, c) ∈ W c ≤ 15. Thus, we can define a set B = {1, 2, 4, 8} where ∀b ∈ ℕb ∈ Biffb ≤ 15 ∧ b = 2forsomen ∈ ℕ. We can now say that W ⊆ ℕ × B ⊆ ℕ × ℕ. Thus, ∀x ∈ ℕ∀y ∈ ℕxW y ∧ yW xiffx ∈ B ∧ y ∈ B. But there is no such (x, y) pair in W. The statement ∀x ∈ ℕ∀y ∈ ℕ (xW y ∧ yW x), so the requirement for antisymmetry is vacuously true.

(e) Find R ∘ S.

[relations2]

Solution Let us define the set M_{i} ⊆ ℕ as {x|xmod4 = i}. Then, clearly there are 4 such sets, namely M_{0}, M_{1}, M_{2}, and M_{3}. Let (x, y) ∈ Z = R ∘Siff(x = 0∧y ∈ M_{1})∨(x = 1∧y ∈ M_{2})∨(x = 2∨x = 3)∧y ∈ M_{0} Problem 23 Source: s98 ps3 Topics: Relations, Adjacency Matrix, Recursive Definitions The graphs C_{n}, Q_{n}, W_{n}, and K_{n,m} are defined in Rosen 7.2.

(a) Describe the adjacency matrix for C_{n}. For C_{n}, we label the vertices so that the cycle goes v_{1}, v_{2}, …, v_{n}, v_{1}. Then the matrix has 1’s on the diagonals just above and below the main diagonal and in positions (1, n) and (n, 1), and 0’s everywhere else.

(\begin{matrix}0 & 1 & 0 & 0 & … & 0 & 1 \\ 1 & 0 & 1 & 0 & … & 0 & 0 \\ 0 & 1 & 0 & 1 & … & 0 & 0 \\ 0 & 0 & 1 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & … & 0 & 1 \\ 1 & 0 & 0 & 0 & … & 1 & 0 \end{matrix})

(b) Describe the adjacency matrix for K_{n,m}. Vertices of K_{n,m} are partitioned into a group of n vertices and a group of m vertices. In this graph, an edge is present between two vertices if and only if the two vertices are from different groups. Therefore, the adjacency matrix of K_{n,m} consists of four sub-matrices. The top left and the bottom right matrices consist of 0’s with size n ∗ n and m ∗ m respectively. The top right and the bottom left matrices consist of 1’s with size of n ∗ m and m ∗ n respectively.

(\begin{matrix}0 & … & 0 & 1 & … & 1 \\ ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & … & 0 & 1 & … & 1 \\ 1 & … & 1 & 0 & … & 0 \\ ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 1 & … & 1 & 0 & … & 0 \end{matrix})

(c) Give a simple recursive definition of the adjacency matrix for the graph Q_{n+1}. Hint: Use the matrix of Q_{n} and suitable identity matrices. The base case is,

Q_{1} = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})

Then, every Q_{n+1} (n ≥ 1) is defined inductively. The size of Q_{n+1} is 2^{n+1} ∗ 2^{n+1} and the left top and right bottom quarter of the matrix are Q_{n}, which correspond to the two subgraphs Q_{n} in Q_{n+1}. The right top and left bottom quarter of the matrix are identity matrices of size 2^{n} ∗ 2^{n}(I_{2^{n}}), which correspond to the edges connecting vertices k and k + 2^{n} for 0 ≤ k < 2^{n}, which differ by the most significant bit only.

Q_{n+1} = (\begin{matrix}Q_{n} & I_{2^{n}} \\ I_{2^{n}} & Q_{n} \end{matrix})

[relations3] Problem 24 Source: H10-tut3, not used Topics: Relations and Closures Let R be any relation. Prove that any relation that contains R and is reflexive (resp. symmetric, transitive) contains the reflexive (resp. symmetric, transitive) closure of R. This means the closure is the ”smallest” containing set that has the property. Solution Problem 25 [10 points] Source: f96 ps3 Topics: Equivalence Relations Each bead on a bracelet with three beads is either red, white, or blue as illustrated in the example shown. Define the relation R between bracelets as follows: (B_{1}, B_{2}), where B_{1} and B_{2} are bracelets, belongs to R if and only if B_{2} can be obtained from B_{1} by rotating it or rotating it and then reflecting it.

• Show that R is an equivalence relation.

• What are the equivalence classes of R?

Problem 26 Source: f97 ps3

Topics: Equivalence Relations, Equivalence Classes

Definition: Let S be a set. Let R be a subset of S ×S. R is an equivalence relation if it satisfies the following properties

1. ∀a ∈ S, (a, a) ∈ R (reflexivity).

2. If (a, b) ∈ R, then (b, a) ∈ R (symmetry).

3. If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R (transitivity).

Definition: Let R be an equivalence relation on S. For a ∈ S, we define the equivalence class of a to be the set [a]_{R} = {b ∈ S|(a, b) ∈ R}.

For example, the relation R defined by (a, b) ∈ R if a ≡ b mod 4 is an equivalence relation on ℤ. There are four equivalence classes for this relation, namely:

• [0]_{R} = {z ∈ ℤ|z ≡ 0 mod 4}

• [1]_{R} = {z ∈ ℤ|z ≡ 1 mod 4}

• [2]_{R} = {z ∈ ℤ|z ≡ 2 mod 4}

• [3]_{R} = {z ∈ ℤ|z ≡ 3 mod 4}

(a) Let G be a simple graph. Define a relation R on the set of vertices V of G by (v, u) ∈ R, if there is a path connecting u to v.

Verify that R is an equivalence relation.

Solution

• Reflexivity:

R is reflexive because trivially every vertex is connected to itself.

• Symmetry:

Suppose there is a path (u, x_{1}), (x_{1}, x_{2}), …, (x_{n}, v) connecting u to v. Then, the path (v, x_{n}), …, (x_{1}, u) connects v to u. Therefore, R is symmetric.

• Transitivity:

Let the path (u, x_{1}), (x_{1}, x_{2}), …, (x_{n}, v) connect u to v, and the path

(v, y_{1}), (y_{1}, y_{2}), …, (y_{m}, w) connect v to w.

Then the path (u, x_{1}), …, (x_{n}, v), (v, y_{1}), …, (y_{m}, w) connects u to v.

Therefore R is transitive.

(b) What are the equivalence classes of R?

Solution The equivalence classes of R are the connected components of G. 33 [relations6] Problem 27 Source: f98 ps3 Topics: Relations, Basic Properties A relation R on a set A is weakly transitive if for all a, b, c, d ∈ A, the relations aRb, bRc, and cRd imply the relation aRd. Prove or disprove the following statements.

(a) Every symmetric, weakly transitive relation is transitive. Solution The claim is false. The diagram below shows a counterexample.

(b) Every reflexive, symmetric, weakly transitive relation is an equivalence relation. Solution Proof. The relation R is an equivalence relation if it is reflexive, symmetric, and transitive. The first two properties hold by assumption; all that remains is to show that R is a transitive relation. Suppose that the relations aRb and bRc hold. Because R is reflexive, the relation aRa also holds. Because R is weakly transtive, the relations aRa, aRb, and bRc imply the relation aRc. Therefore, R is transitive.

[statemachines1]

Problem 28 [15 points] Source: nancy Topics: state machines Consider a state machine whose state is a digraph with the 5-element vertex set V = {1, 2, 3, 4, 5}, initially the ”linear graph” as depicted below: 1 —¿ 2 —¿ 3 —¿ 4 —¿ 5 The transitions allowed by the state machine are the following:

– remove(a,b): Can occur if there is an edge from a to b. Effect is to remove the edge.

– add-out(a,b) (distinct): Can occur if a has no incoming edges. Effect is to add the edge a —¿ b.

– add-in(a,b): Can occur if a has no outgoing edges. Effect is to add the edge b —¿ a.

– reverse(a): Can occur if either all edges incident upon a are incoming, or all are outgoing. Effect is to reverse the direction of all edges incident on a.

– trans(a,b,c) (all three distinct): Can occur if a —¿ b and b —¿ c. Effect is to add the edge a —¿ c. Say whether each of the following digraphs is reachable. If it is, then describe an execution that reaches it. If not, then state an invariant that can be used to show that the state cannot be reached. Your invariant must be provable by induction (or the Invariant Theorem).

(a) The graph that is the same as the line graph above but with the additional edge 5 —¿ 1. Ans: Not reachable. Invariant is that the graph in the state is always acyclic.

(b) The line graph in the opposite direction: 1 ¡— 2 ¡— 3 ¡— 4 ¡— 5 Ans: Reachable. Can do, e.g., by reverse(1) reverse(2) reverse(1) reverse(3) reverse(2) reverse(1) reverse(4) reverse(3) reverse(2) reverse(1) (Potential here for wasting too much time if they don’t see the trick??) Now suppose we have the same state machine, but without the remove and reverse transitions. We want to prove that eventually, a transitively closed graph is produced. Assume that we are considering a ”live” execution, that doesn’t stop as long as any transition is enabled.

(c) Define a termination function that can be used to prove this eventuality property. Argue the key properties (It should have a natural number value, and decrease with every transition. Also, when no step is enabled, the graph should be transitively closed.) Ans: n(n-1) minus number of edges should work. Each transition decreases this because it adds an edge. When no step is enabled, the graph must be transitively closed, because we have an explicit transitive closure step.

Actually, I was playing with a more interesting version of the problem, where the reverse isn’t disabled. We’re still guaranteed to eventually end up with a transitively closed graph, but we must assume a stronger kind of liveness. That is, we need to ensure that the aggregate of add and trans steps gets to keep taking steps as long as anything is enabled, regardless of what removes occur. But I can’t think of a way to say this simply.

[relations7] Problem 29 Source: kdmc Topics: Relations Let the relations R and S be binary relations on the set ℕ of natural numbers. Define R as follows: ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ Riffamod4 = bmod4. Define S as follows: ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ Riff2^{a} = b.

(a) Prove that R is transitive.

(b) Prove that R is symmetric.

(c) Find R ∩ S.

(d) Let T = S ∘ R.

Problem 30 Source: Nancy

Topics: State machines, graphs

[15 points] Consider a state machine whose state is a directed graph with the 5-element vertex set V = {1, 2, 3, 4, 5}. Initially, the state is that of the “linear graph” (1 ⟶ 2 ⟶ 3 ⟶ 4 ⟶ 5). The transitions allowed by the state machine are the following:

• remove(a,b):

Can occur if there is an edge from a to b.

Effect is to remove the edge.

• add-out(a,b) (a,b distinct): Can occur if a has no incoming edges. Effect is to add the edge a⟶ b.

• add-in(a,b):

Can occur if a has no outgoing edges. Effect is to add the edge b⟶ a.

• reverse(a):

Can occur if either all the edges incident upon a are incoming, or all are outgoing. Effect is to reverse the direction of all edges incident on a.

• trans(a,b,c) (a,b,c distinct): Can occur if there is an edge from a to b. Effect is to remove the edge.

State whether each of the following digraphs is reachable. If it is, then describe an execution that reaches it; otherwise, state an invariant that can be used to show that the state cannot be reached. Such an invariant must be provable by induction (or the Invariant Theorem). Instead of giving a proof of the invariant, just state key reasons.

(a) The graph that is the same as the line graph above, but with the additional edge 5⟶ 1.

Solution Not reachable. The invariant is that the graph in the state is always acyclic.

(b) The line graph in the opposite direction (1 ⟵ 2 ⟵ 3 ⟵ 4 ⟵ 5).

Solution Reachable: reverse(1), reverse(2), reverse(1), reverse(3), reverse(2), reverse(1), reverse(4), reverse(3), reverse(2), reverse(1).

(c) Now suppose we have the same state machine, but without the remove and reverse transitions. We want to prove that, eventually, a transitively closed graph is produced. Assume that we are considering a “live” execution, i.e. one that does not stop as long as any transition is possible.

Define a termination function that can be used to prove this eventuality property. Argue that it satisfies the properties of a termination function.

Solution f(n) = n(n − 1) − #edges is such a termination function. Without remove and reverse, every transition adds an edge to the graph, decreasing this function. When no transition is possible, the graph must be transitively closed, because we have an explicit transitive-closure step.

[combinatorics1]

Problem 31 [10 points] Source: Nancy’s brain

Topics: Combinatorics

Prove combinatorially that the number of even-sized subsets of a set S ≠ ∅ is equal to the number of oddsized subsets. Formally, denoting by E the even-sized subsets of S and by O the odd-sized subsets of S, construct a bijection between E and O.

Hint: Although there is a natural bijection that works for all S, you may find it clearer to divide the bijection into one that works for even-sized S and one that works for odd-sized S.

Solution Our mapping f : E → O complements the presence of some arbitrary element in the input set; i.e., choose some element e ∈ S so that f(X) = X ∪ {e} if e ∉ X, or f(X) = X − {e} if e ∈ X. We must prove the function is defined on its domain, is one-to-one, and is onto.

|X| even-sized ⇒ |f(X)| odd-sized. Clearly |f(X)| = |X| ± 1, so if X is even-sized, then f(X) is odd-sized.

f one-to-one. Assume f(X) = f(Y). If e ∉ f(X) and e ∉ f(Y), then X = f(X) ∪ {e} and Y = f(Y) ∪ {e}, so X = Y; otherwise, if e ∈ f(X) and e ∈ f(Y), then X = f(X) − {e} and Y = f(Y) − {e}, so again X = Y.

f onto. Consider an odd-sized set Y: if e ∉ Y, then |Y ∪ {e} | is even-sized, so f(Y ∪ {e}) = Y; otherwise, if e ∈ Y, then |Y − {e} | is even-sized, so f(Y − {e}) = Y.

[combinatorics2] Problem 32 Source: David Gries’ book, Eg. 16.36 Topics: Combinatorics, permutations w/limited repetition of a multiset Let n = 2k, for some k ≥ 0.

(a) Prove combinatorially that n!/2^{k} is an integer. Solution Consider a multiset with two of each of k distinct elements. The number of permutations with limited repetition of this set is n!/(\underbrace{2!2! ⋯ 2!}_{k}) = n!/2^{k}, which must be an integer.

(b) Prove the same theorem algebraically. Solution n! = (2k)! = (\underbrace{2k}_{even})(\underbrace{2k − 1}_{odd})(\underbrace{2k − 2}_{even})(\underbrace{2k − 3}_{odd}) ⋯ (2)(1). There are k even factors, so 2^{k}|n!.

Problem 33 Source: Kyle’s brain

Topics: Combinatorics, binomials, product rule

Theorem.

2^{n−3} ∏_{i=1}^{n−3} 2^{i} = 2^{\binom{n}{2}−n}

(a) Give a combinatorial proof of the theorem.

Hint: Consider a graph represented by a circle of n nodes where there are no edges between directly adjacent nodes.

Solution Consider the RHS: there are \binom{n}{2} edges between nodes in a complete graph, but only \binom{n}{2} − n when the edges forming the outside of the circle are not considered. Thus, there are 2^{\binom{n}{2}−n} such possible graphs on n nodes.

Now, consider the LHS: number the nodes in some way, and start with the first two. Each has n − 3 possible edges to other nodes: not to itself, and not to either of its two neighbors. So, there are 2^{n−3} possible subsets of the edges from each of these two nodes. The third node has n − 4 edges that don’t intersect with the first two sets: not to itself, not to either of its two neighbors, and not to the first node; thus, there are 2^{n−4} possible edge subsets. The fourth node has n − 5 edges that don’t intersect with the first three sets: not to itself, not to either of its two neighbors, not to the first node, and not to the second node; so 2^{n−5} possible edge subsets. And so on.

By the product rule, this is 2^{n−3} · 2^{n−3}2^{n−4}2^{n−5} ⋯ = 2^{n−3} ∏_{i=1}^{n−3} 2^{i}.

(b) Give an algebraic proof of the theorem.

Solution

2^{n−3} ∏_{i=1}^{n−3} 2^{i} = 2^{n−3+∑_{i=1}^{n−3} i}
= 2^{n−3+(n−3)(n−2)/2}
= 2^{(2n−6+n^{2}−5n+6)/2}
= 2^{(n^{2}−3n)/2}
= 2^{(n(n−1))/2−n}
= 2^{\binom{n}{2}−n}

[combinatorics4] Problem 34 [14 points] Source: Kyle’s brain Topics: Combinatorics, basic probability, product rule Theorem. Let 0 ≤ p_{i} ≤ 1 for all i ∈ {1, …, n}. Then,

∑_{S⊆{1,... ,n}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j}))) = 1

Note that ∑_{S⊆T} means to sum over all possible subsets S of T.

(a) [6 points] Give a combinatorial proof of the theorem. Hint: Consider choosing an element from {a_{1}, b_{1}} × {a_{2}, b_{2}} × {a_{3}, b_{3}} × ⋯ × {a_{n}, b_{n}} where we have a probability p_{i} of choosing a_{i} for the i^{th} element of the tuple. Solution Use the hint given. For a given subset S of the indices {1, …, n}, the summand is the probability of choosing a_{i} for the indices in S and b_{i} for the indices not in S. Since this covers exactly the possible ways of choosing a tuple given these probabilities, the total probability must be 1.

(b) [8 points] Give an algebraic proof of the theorem. Hint: Use induction. Solution Base case: When n = 1, we have

p_{i} + (1 − p_{i}) = 1

Inductive case: Assume the theorem for all n ≤ N. Now we must prove it for N + 1.

∑_{S⊆{1,... ,N+1}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j}))) = ∑_{S⊆{1,... ,N}} ((p_{N+1} ∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j})))

+ ∑_{S⊆{1,... ,N}} ((∏_{j∈S} p_{j}) ((1 − p_{N+1}) ∏_{j∉S}(1 − p_{j})))

= p_{N+1} ∑_{S⊆{1,... ,N}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j})))

+(1 − p_{N+1}) ∑_{S⊆{1,... ,N}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j})))

= p_{N+1} · 1 + (1 − p_{N+1}) · 1
= 1

Problem 35 Source: nancy The following is a true identity for binomial coefficients: Σ_{k=1}^{n}k\binom{n}{k} = n2^{n−2}.

kyle says we’ve already used this one. maybe just give part (c), then

(a) Give a combinatorial proof of this identity. Ans: Committee of any size plus a chairman.

(b) Give an analytical proof. Ans: Starting with the sum, expand the binomial coefficient factor, pull out the n from the sum, and re-express the sum as Σ_{k=1}^{n}\binom{n−1}{k−1}. This is the same as Σ_{k=0}^{n} − 1\binom{n−1}{k}. Binomial theorem says that’s just 2^{n−1}.

[expectation1]

(c) Using an extension of your combinatorial reasoning in (a), can you give a closed-form expression for Σ_{k=1}^{n}k^{2}\binom{n}{k} ? Ans: Think of this as the number of different committees (of any size) with two distinguished members (president and vp), but where both offices can be held by the same person. Can break this down into two terms: the number of such configurations having both officers the same: n2^{n−1} (same as above). plus the number of such configurations having different officers: n(n − 1)2^{n−2} Problem 36 [12 points]Source: Nancy’s brain

Topics: Expectation, linearity of expectation, expected number of events that occur, binomial distribution, counting permutations

Each of 5 students in 6.042 chooses a natural number in the range [1, …, 5], randomly and independently, using the uniform distribution on [1, …, 5].

(a) [3 points] What is the expected number of people who choose the number that gives their position in alphabetical order?

Solution 1

(b) [3 points] Give an expression representing the probability that exactly the expected number of people (as given by your answer to the previous part) choose their correct positions.

Solution \underbrace{\binom{5}{1}\frac{1}{5}}_{Winner} \underbrace{(\frac{4}{5})^{4}}_{Losers}

Now suppose the 5 students are all assigned numbers in the range [1, …, 5] by a course TA, who chooses randomly from the uniform distribution on permutations of [1, …, 5].

(c) [3 points] Now what is the expected number of people who are assigned the number that gives their position in alphabetical order?

Solution 1

(d) [3 points] Give an expression for the probability that exactly the expected number of people (as given by your answer to the previous part) are assigned their correct positions.

Solution This is more complicated, and a little too ad hoc for my taste. Maybe need hints?

I calculate that there are 45 5-permutations in which exactly one guy is a ”fixed point”, which gives a probability of 45/120, or 3/8. To get the 45, I figure 5 choices for the fixed point, then 9 4-perms with no fixed point. But, to figure out that there are exactly 9 4-perms with no fixed point, I used slightly ad hoc arguments: 3 possibilities for who gets the number 1; then for each of these, say the guy with rank i, three possibilities for who gets the number i; after these two are assigned, it turns out that the final assignments have only one possibility.

In trying to generalize this, I got a somewhat messy recurrence. So I’m inclined just to leave it as an ad hoc calculation. OK since the numbers are very small. Or, we can give them the 9 as a hint.

I was hoping to get a comparison between these two experiments, but don’t see anything nice here. Is it clear which of the two kinds of experiments should yield the higher probability of getting exactly one fixed point? Here, the probability is higher in the case of the first experiment (.4096 vs. .375). In general?

[expectation2] Problem 37 [10 points]Source: Nancy Topics: Expectation 100 students enter a cafeteria with very large tables, one at a time. As each students enters, he or she looks around to see if any of his friends are already there. If so, he/she joins one of his friends’ tables. If not, he/she starts a new table. Assume that, for each pair of students, the probability that they are friends is p. Moreover, all these pair probabilities are independent.

(a) For the i^{th} person to enter the cafeteria, what is the probability he/she starts a new table? Solution (1 − p)^{i−1}

(b) What is the expected number of occupied tables after everyone has entered? Solution Add this from i = 1 to n.

[expectation3] Problem 38 Source: David R’s Brain Topics: Expectation, product rule There is a casino in St. Petersburg where you have the choice of betting any portion of your wealth on either of two games: in the first game, you either receive 3 times what you bet or lose it all with equal probability. In the second game the casino gives you 1.4 times what you bet with probability 1 (this casino is understandably very popular). Each trial of the two games are played simultaneously.

(a) Call S_{1} and S_{2} the fraction of your wealth you bet on the two games (notice S_{1} +S_{2} ≤ 1). What values of S_{1} and S_{2} maximize the expected value of your wealth after 1 trial? What is the maximum expected value of your wealth? Solution S_{1} = 1, max is 1.5

(b) What strategy maximizes your expected wealth after n trials? Solution Always have S_{1} = 1

(c) Using that strategy, what is the probability that after 10 trials, you have more money than you started with? Solution 1 − 2^{−10}

(d) After 2n trials, what is the most likely number of trials in game one that are wins. And what is the probability that this occurs? Solution n, f_{2n,0.5}(n) ≈

(e) What fraction of your wealth should you bet on each trial of the two games, if you want to maximize your wealth after 2n trials in the most likely case that you found above? (i.e. suppose that there are that number of wins over the course of the 2n trials). Assume that it is in your interest to have S_{1} + S_{2} = 1. Solution Maximize (1.4 + 1.6S_{1})^{0.5}(1.4 − 1.4S_{1})^{0.5} over S_{1}. S_{1} = 0.0625.

Problem 39 [10 points]Source: Nancy Topics: Wald thm. The number of students that will enter LaVerde’s to buy junk food on Tuesday night of finals week is a random variable taking on an integer value from {0, …, 100} uniformly. Each student who enters picks at least one kind of junk food. After choosing each kind of junk food, a student is equally likely to continue choosing more kinds of junk food or to quit and go pay at the checkout register. Students’ decisions to continue buying are mutually independent. The checkout clerk throws a fair die for each item and then charges the number of dollars that shows up. What is the expected number of dollars spent by students on junk food at LaVerde’s on Tuesday night?

[wald1]

Problem 40 Source: victor Topics: Wald’s theorem A miner, lost in some abandoned mine, finds himself in a room containing three doors. Door 1 leads him to freedom after two hours travel; door 2 returns him to the same room after four hours travel, and door 3 returns him to the room after eight hours travel. Each time he finds himself in the room, the miner picks a door with equal probability. Let T denote the time until he finds the exit.

(a) Define a sequence of iid random variables X_{i} and a stopping rule N such that

T = ∑_{i=1}^{N} X_{i}

Solution We view this as an experiment where at each step we make a choice between three equiprobable outcomes. Let X_{i} = number of hours to return to room on ith step. Let N = number of steps until good door is selected. Then N is geometrically distributed with probability 1/3.

(b) Use Wald’s Identity to find Ex[T]

Solution Pr(X_{i} = 2) = 1/3 Pr(X_{i} = 4) = 1/3 Pr(X_{i} = 8) = 1/3 Ex[X_{i}] = 14/3 Ex[N] = 3 By Wald’s Identity

Ex[∑_{i=1}^{N} X_{i}] = 14

[markov1] Problem 41 [16 points]Source: Nancy Topics: Markov and Chebyshev Bounds The average IQ of all MIT faculty is known to be exactly 150.

(a) Give a tight upper bound on the probability that a random MIT faculty member’s IQ is 175 or more. Solution Use Markov, get ≤ 150/175 = 6/7

(b) Give an example distribution of weights showing that your bound in the first part is tight. Solution 6 faculty members with IQ 175, one with IQ 0. Now assume also that the standard deviation of IQs of MIT faculty members is 25.

(c) Give a tight upper bound on the probability that a random MIT faculty member’s IQ is 175 or more, taking this new information into account. Solution Use one-sided Chebyshev

(d) Give an example distribution of weights showing that your bound in the previous part is tight. Solution LTTR [markov2] Problem 42 Source: victor Topics: Markov and Chebyshev bounds There are sixty people in a basketball league. No one is shorter than 5’6”, nor is anyone taller than 6’6”. The average height is 5’10”.

(a) Without any other information, what is the best possible upper bound for the number of people taller than 6’4”? Solution Use Markov’s bound. The answer is 40%, I believe, so twenty-four people.

(b) Without any other information, what is the best possible upper bound for the number of people who are 5’6”? Solution Markov again, this time flipping the variable. I believe the answer is 8/12 = 2/3, so forty people.

(c) You are now told that the standard deviation of the heights of these sixty people is 2”. What is the best upper bound you can give now for the two previous parts? Solution Use one-sided Chebyshev inequality: Pr(H − 5′10′′ > 6′′) ≤ \frac{Var[H]}{Var[H]+6^{2}} = 2/38 = 1/19. So at most ⌊60/19⌋ = 3 people who are at least 6’4”. Pr(5′10 − H > 4′′) ≤ \frac{Var[H]}{Var[H]+4^{2}} = 2/18 = 1/9. So at most ⌊60/9⌋ = 6 people who are 5’6”.

[pmethod1] Problem 43 [12 points] Source: Nancy Topics: Probabilistic Method Consider n players in a round-robin tournament. We are going to consider the question of whether there exists a possible tournament outcome (that is, a tournament digraph) in which every player wins at least two matches (that is, every node in the digraph has at least two outgoing edges). We would like you to use the probabilistic method to show that such an outcome exists, for certain values of n.

(a) Say a match between two players—a and b—is won by a with probability 1/2 and by b with probability 1/2. What is the probability that a particular player wins no more than one game? Solution \frac{n}{2^{n−1}} , since there are n ways to win no more than one game—1 way to win zero, n − 1 ways to win 1 versus n − 1 opponents—out of 2^{n−1} possible ways to win/lose n − 1 games.

(b) Now, upper bound the probability that some player wins no more than one game. Solution By the union bound, this is just \frac{n^{2}}{2^{n−1}} .

(c) Lower bound the probability that all players win at least two games. Solution This is just the complement of the previous part, so 1 − \frac{n^{2}}{2^{n−1}} .

(d) Show a condition implying a positive probability of all players winning at least two games. Solution 1 − \frac{n^{2}}{2^{n−1}} > 0.

(e) Explain briefly why your condition implies the existence of such a tournament. Solution If there is a non-zero probability of such an event occuring, then there must be a configuration in which that event occurs.