CS 70 Discrete Mathematics and Probability Theory
(Optional) HW 7
Due: Saturday 10/16, 4:00 PM Grace period until Saturday 10/16, 5:59 PM
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
Counting on Graphs + Symmetry
How many distinct undirected graphs are there with n labeled vertices? Assume that there can be at most one edge between any two vertices, and there are no edges from a vertex to itself. The graphs do not have to be connected.
How many distinct cycles are there in a complete graph Kn with n vertices? Assume that cycles cannot have duplicated edges. Two cycles are considered the same if they are rotations or inversions of each other (e.g. (v1,v2,v3,v1), (v2,v3,v1,v2) and (v1,v3,v2,v1) all count as the same cycle).
How many ways are there to color a bracelet with n beads using n colors, such that each bead has a different color? Note: two colorings are considered the same if one of them can be obtained by rotating the other.
How many ways are there to color the faces of a cube using exactly 6 colors, such that each face has a different color? Note: two colorings are considered the same if one can be obtained from the other by rotating the cube in any way.
School Carpool
n males and n females apply to EECS within UC Berkeley. The EECS department only has n seats available. In how many ways can it admit students? Use the above story for a combina- torial argument to prove the following identity:
2n n2 n2 n2 n = 0 + 1 +···+ n
CS 70, Fall 2021, (Optional) HW 7
Among the n admitted students, there is at least one male and at least one female. On the first day, the admitted students decide to carpool to school. The male(s) get in one car, and the female(s) get in another car. Use the above story for a combinatorial argument to prove the following identity:
n−1 n2 2n − 2 ∑k·(n−k)· k =n2· n−2
(Hint: Consider the ways that students are admitted. Also, each car has a driver!)
Proofs of the Combinatorial Variety
Prove each of the following identities using a combinatorial proof.
For every positive integer n > 1,
∑k· k =n·∑ k .
n n n−1n−1 k=0 k=0
For each positive integer m and each positive integer n > m, n n n 3n
∑a·b·c=m. a+b+c=m
(Notation: the sum on the left is taken over all triples of nonnegative integers (a, b, c) such that a+b+c = m.)
Unions and Intersections
• A is a countable, non-empty set. For all i ∈ A, Si is an uncountable set.
• B is an uncountable set. For all i ∈ B, Qi is a countable set.
For each of the following, decide if the expression is “Always Countable”, “Always Uncountable”,
“Sometimes Countable, Sometimes Uncountable”.
For the “Always” cases, prove your claim. For the “Sometimes” case, provide two examples – one where the expression is countable, and one where the expression is uncountable.
(a) A∩B (b) A∪B (c) i∈ASi
CS 70, Fall 2021, (Optional) HW 7 2
(d) i∈ASi (e) i∈BQi (f) i∈BQi
5 Count It!
For each of the following collections, determine and briefly explain whether it is finite, countably infinite (like the natural numbers), or uncountably infinite (like the reals):
(a) The integers which divide 8.
(b) The integers which 8 divides.
(c) The functions from N to N.
(d) The set of strings over the English alphabet. (Note that the strings may be arbitrarily long, but each string has finite length. Also the strings need not be real English words.)
(e) Computer programs that halt. Hint: How can we represent a computer program?
(f) The set of finite-length strings drawn from a countably infinite alphabet, A .
(g) The set of infinite-length strings over the English alphabet.
6 Countability Proof Practice
(a) A disk is a 2D region of the form {(x,y) ∈ R2 : (x−x0)2 +(y−y0)2 ≤ r2}, for some x0,y0,r ∈ R, r > 0. Say you have a set of disks in R2 such that none of the disks overlap. Is this set always countable, or potentially uncountable?
(Hint: Attempt to relate it to a set that we know is countable, such as Q × Q)
(b) A circle is a subset of the plane of the form {(x,y) ∈ R2 : (x−x0)2 +(y−y0)2 = r2} for some x0,y0,r ∈ R, r > 0. Now say you have a set of circles in R2 such that none of the circles overlap. Is this set always countable, or potentially uncountable?
(Hint: The difference between a circle and a disk is that a disk contains all of the points in its interior, whereas a circle does not.)
(c) Is the set containing all increasing functions f : N → N (i.e., if x ≥ y, then f (x) ≥ f (y)) count- able or uncountable? Prove your answer.
(d) Is the set containing all decreasing functions f : N → N (i.e., if x ≥ y, then f (x) ≤ f (y)) countable or uncountable? Prove your answer.
CS 70, Fall 2021, (Optional) HW 7 3
7 Unprogrammable Programs
Prove whether the programs described below can exist or not.
A program P(F,x,y) that returns true if the program F outputs y when given x as input (i.e. F(x) = y) and false otherwise.
A program P that takes two programs F and G as arguments, and returns true if F and G halt on the same set of inputs (or false otherwise).
Kolmogorov Complexity
Compressing a bit string x of length n can be interpreted as the task of creating a program of fewer than n bits that returns x. The Kolmogorov complexity of a string K(x) is the length of an optimally-compressed copy of x; that is, K(x) is the length of shortest program that returns x.
(a) Explain why the notion of the “smallest positive integer that cannot be defined in under 280 characters” is paradoxical.
(b) Prove that for any length n, there is at least one string of bits that cannot be compressed to less than n bits.
(c) Say you have a program K that outputs the Kolmogorov complexity of any input string. Under the assumption that you can use such a program K as a subroutine, design another program P that takes an integer n as input, and outputs the length-n binary string with the highest Kolmogorov complexity. If there is more than one string with the highest complexity, output the one that comes first lexicographically.
(d) Let’s say you compile the program P you just wrote and get an m bit executable, for some m ∈ N (i.e. the program P can be represented in m bits). Prove that the program P (and consequently the program K) cannot exist.
(Hint: Consider what happens when P is given a very large input n.)
CS 70, Fall 2021, (Optional) HW 7 4