\Question{Kolmogorov Complexity}
Compression of a bit string $x$ of length $n$ involves creating a program shorter than $n$ bits that
returns $x$. The Kolmogorov complexity of a string $K(x)$ is the length of shortest program that
returns $x$ (i.e. the length of a maximally compressed version of $x$).
\begin{Parts}
\Part
Explain why "the smallest positive integer not definable in under 100 characters" is paradoxical.
\nosolspace{0.5in}
\Part
Prove that for any length $n$, there must be at least one bit string that cannot be compressed to fewer than $n$ bits.
\nosolspace{0.5in}
\Part
Imagine you had the program $K$, which outputs the Kolmogorov complexity of string. Design a program
$P$ that when given integer $n$ outputs the bit string of length $n$ with the highest Kolmogorov
complexity. If there are multiple strings with the highest complexity, output the lexicographically
first (i.e. the one that would come first in a dictionary).
\nosolspace{1in}
\Part
Suppose the program $P$ you just wrote can be written in $m$ bits. Show that $P$
and by extension, K, cannot exist, for a sufficiently large input $n$.
\nosolspace{1in}
%\Part
%Consider the program $I$, which can be written in $m$ bits, that when given any input string $x$
%returns true if $x$ is incompressible and returns false otherwise. Show that such a program
%cannot exist.
%\nosolspace{1in}
\end{Parts}
\Question{Rubik's Cube Scrambles}
We wish to count the number of ways to scramble a $2\times2\times2$ Rubik's Cube,
and take a quick look at the $3\times3\times3$ cube. Leave your answer as an
expression (rather than trying to evaluate it to get a specific number).
\begin{Parts}
\Part The $2\times2\times2$ Rubik's Cube is assembled from 8 "corner pieces" arranged in a
$2\times2\times2$ cube. How many ways can we assign all the corner pieces a position?
\Part Each corner piece has three distinct colors on it, and so can also be oriented three
different ways once it is assigned a position (see figure below). How many ways can we
\emph{assemble} (assign each piece a position and orientation) a $2\times2\times2$ Rubik's Cube?
\begin{figure}[H]
\centering
\includegraphics[width=0.5\linewidth]{./src/problems/counting/resources/figures/rubiks-cube.PNG}\\
\textit{Three orientations of a corner piece}
\end{figure}
\Part The previous part assumed we can take apart pieces and assemble them as we wish.
But certain configurations are unreachable if we restrict ourselves to just turning the
sides of the cube. What this means for us is that if the orientations of 7 out of 8 of the corner
pieces are determined, there is only 1 valid orientation for the eighth piece. Given this, how
many ways are there to \emph{scramble} (as opposed to \emph{assemble}) a $2\times2\times2$ Rubik's Cube?
\Part We decide to treat scrambles that differ only in overall positioning (in other words, the entire cube is flipped
upside-down or rotated but otherwise unaltered) as the same scramble. Then we overcounted
in the previous part! How does this new condition change your answer to the previous part?
\Part Now consider the $3\times3\times3$ Rubik's Cube. In addition to 8 corner pieces, we
now have 12 "edge" pieces, each of which can take 2 orientations. How many ways can we
\emph{assemble} a $3\times3\times3$ Rubik's Cube?
% \Part Explain why we don't need to worry about overcounting overall positioning for a
% $3\times3\times3$ Rubik's Cube like we did in part (d). (\emph{Hint: unlike the $2\times2\times2$
% case, each face of the $3\times3\times3$ cube has a unique center square color})
\end{Parts}
\Question{The Count}
\begin{enumerate}[(a)]
% \item The Count wants to place a basket of candy outside his front door for trick-or-treaters to enjoy. He checked his storage of candy and found that he has 11 identical candy canes, 12 identical bars of chocolate, and 660 identical jellybeans. How many possible baskets of candy could he choose to put out?
% \item The Count decides that candy is too unhealthy for trick-or-treaters, and that numbers are much better for you. He finds that he has the first 25 positive integers in his pantry, and wants to put out some subset of them for the trick-or-treaters. However, he doesn't want to give out too many of his precious numbers, so he decides that the sum of the numbers that he puts out shouldn't exceed 162. How many possible subsets of numbers can he choose? (Hint: Construct a bijection)
\item How many permutations of COSTUME contain "COME" as a substring? How about as a subsequence (meaning the letters of "COME" have to appear in that order, but not necessarily next to each other)?
\nosolspace{2cm}
\item How many of the first 100 positive integers are divisible by 2, 3, or 5?
\nosolspace{2cm}
\item How many ways are there to choose five nonnegative integers $x_0, x_1, x_2, x_3, x_4$ such that $x_0+x_1+x_2+x_3+x_4=100$, and $x_i \equiv i\pmod{5}$?
\nosolspace{2cm}
\item The Count is trying to choose his new 7-digit phone number. Since he is picky about his numbers, he wants it to have the property that the digits are non-increasing when read from left to right. For example, 9973220 is a valid phone number, but 9876545 is not. How many choices for a new phone number does he have?
\nosolspace{2cm}
\end{enumerate}
\Question{Binomial Beads}
\begin{Parts}
\Part
Satish is making school spirit keychains, which consist of a sequence of $n$ beads on a string. He has blue beads and gold beads. How many unique keychains can he make with exactly $k \leq n$ blue beads?
\Part
Satish decides to sell his keychains! He decides on the following pricing scheme:
\begin{itemize}
\item Blue beads have a value of $x$
\item Gold beads have a value of $y$
\item The price of a keychain is the product of the values of all of its beads.
\end{itemize}
What is the price of a keychain with exactly $k \leq n$ blue beads?
\Part
Satish decides to make exactly one of every possible unique keychain. If he sells every keychain he creates, how much revenue will he make? Use parts (a) and (b), and leave your answer in summation form.
\Part Draw a connection between part (c) and the binomial theorem.
$$(x+y)^n = \sum_{k=0}^n {n \choose k} x^ky^{n-k}$$
\end{Parts}
\textit{Hint: How do you calculate the product (x + y)(x + y)?}
\Question{Probability Practice}
\begin{Parts}
\Part If we put 5 math, 6 biology, 8 engineering, and 3 physics books on a bookshelf at random, what is the probability that all the math books are together?
\nosolspace{1cm}
% Problem originally written by Sridhar for Fall 2011 midterm 2; not all parts were used on that midterm
\Part A message source $M$ of a digital communication system outputs a word of length 8 characters, with the characters drawn from the ternary alphabet $\{0,1,2\}$, and all such words are equally probable. What is the probability that $M$ produces a word that looks like a byte (\textit{i.e.}, no appearance of `2')?
\nosolspace{1cm}
\Part If five numbers are selected at random from the set $\{1,2,3,\ldots,20\}$, what is the probability that their minimum is larger than 5?
(A number can be chosen more than once, and the order in which you select the numbers matters)
\nosolspace{1cm}
\end{Parts}
\Question{Shooting Range}
You and your friend are at a shooting range. You ran out of bullets. Your friend still has two bullets left but magically lost his gun.
Somehow you both agree to put the two bullets into your six-chambered revolver in successive order, spin the revolver, and then take turns shooting.
Your first shot was a blank. You want your friend to shoot a blank too; should you spin the revolver again before you hand it to your friend?
\Question{Cliques in Random Graphs}
Consider a graph $G = (V,E)$ on $n$ vertices which is generated by the following random process: for each pair of vertices $u$ and $v$, we flip a fair coin and place an (undirected) edge between $u$ and $v$ if and only if the coin comes up heads. So for example if $n = 2$, then with probability $1/2$, $G = (V,E)$ is the graph consisting of two vertices connected by an edge, and with probability $1/2$ it is the graph consisting of two isolated vertices.
\begin{Parts}
\Part What is the size of the sample space?
\Part A $k$-clique in graph is a set of $k$ vertices which are pairwise adjacent (every pair of vertices is connected by an edge). For example a $3$-clique is a triangle. What is the probability that a particular
set of $k$ vertices forms a $k$-clique?
%\Part Prove that ${n \choose k} \le n^k$.
%\textit{Optional:} Can you come up with a combinatorial proof? Of course, an algebraic proof would also get full credit.
\Part Prove that the probability that the graph contains a $k$-clique, for $k \geq 4{\log n}+1$, is at most
$1/n$. (The log is taken base 2).
\textit{Hint:} Apply the union bound and part (c).
\end{Parts}