CS 70 Discrete Mathematics and Probability Theory
Fall 2021 (Optional) HW 7
Due: Saturday 10/16, 4:00 PM
Grace period until Saturday 10/16, 5:59 PM
Sundry
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.)
1 Counting on Graphs + Symmetry
(a) 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.
(b) 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).
(c) 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.
(d) 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.
2 School Carpool
(a) 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
n
)
=
(
n
0
)2
+
(
n
1
)2
+ · · · +
(
n
n
)2
CS 70, Fall 2021, (Optional) HW 7 1
(b) 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
∑
k=1
k · (n− k) ·
(
n
k
)2
= n2 ·
(
2n−2
n−2
)
(Hint: Consider the ways that students are admitted. Also, each car has a driver!)
3 Proofs of the Combinatorial Variety
Prove each of the following identities using a combinatorial proof.
(a) For every positive integer n > 1,
n
∑
k=0
k ·
(
n
k
)
= n ·
n−1
∑
k=0
(
n−1
k
)
.
(b) For each positive integer m and each positive integer n > m,
∑
a+b+c=m
(
n
a
)
·
(
n
b
)
·
(
n
c
)
=
(
3n
m
)
.
(Notation: the sum on the left is taken over all triples of nonnegative integers (a,b,c) such that
a+b+ c = m.)
4 Unions and Intersections
Given:
• 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∈A Si
CS 70, Fall 2021, (Optional) HW 7 2
(d)
⋂
i∈A Si
(e)
⋃
i∈B Qi
(f)
⋂
i∈B Qi
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) 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.
(b) 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).
8 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
Counting on Graphs + Symmetry
School Carpool
Proofs of the Combinatorial Variety
Unions and Intersections
Count It!
Countability Proof Practice
Unprogrammable Programs
Kolmogorov Complexity