\bigskip
\textit{\textbf{Note:} This homework consists of two parts. The first part (questions 1-4) will be graded and will determine your score for this homework. The second part (questions 5-6) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare.}
\rule{6in}{2px}
\begin{center}
For each problem, justify all your answers unless otherwise specified.
\end{center}
\section*{Part 1: Required Problems}
\bigskip
\Question{Counting Boot Camp}
Let's get some practice with counting!
For this problem, you do not need to show work that justifies your answers.
You may also leave your answer as an expression (rather than
trying to evaluate it to get a specific number).
\begin{Parts}
\Part How many sequences of 15 coin-flips are there that contain exactly 4 heads?
\Part How many ways are there to arrange $n$ heads and $k$ tails into a sequence?
\Part How many 99-coin-flip sequences are there that contain more heads than
tails?
\Part
A poker hand contains 5 cards from a standard
52-card deck. The order of the cards in a poker hand is
irrelevant. How many different 5-card poker hands are there?
\Part How many different 5-card poker hands are there that contain
no aces?
\Part How many different 5-card poker hands are there that contain
all four aces?
\Part How many different 5-card poker hands are there that contain
exactly 3 spades?
\Part An anagram of HALLOWEEN is any re-ordering of the letters of HALLOWEEN, i.e., any
string made up of the letters H, A, L, L, O, W, E, E, N in any order.
The anagram does not have to be an English word. \\
How many different anagrams of HALLOWEEN are there?
%\Part If we have a standard 52-card deck, how many ways are there to
% order these 52 cards?
\Part How many solutions does $y_0 + y_1 + \cdots + y_k = n$ have, if each $y$ must be a non-negative integer?
\Part How many solutions does $y_0 + y_1 = n$ have, if each $y$ must be a positive integer?
\Part How many solutions does $y_0 + y_1 + \cdots + y_k = n$ have, if each $y$ must be a positive integer?
% \Part Let (1, 1) be the bottom-left corner and (8, 8) be the upper-right
% corner of a chessboard. If you are allowed to move one square at a time and
% can only move up or right, what is the number of ways to go from the bottom-left corner to
% the upper-right corner?
% \Part What is the number of ways to go from the bottom-left corner to
% the upper-right corner of the chesssboard, if you must pass through the square
% (6, 2), where $(i, j)$ represents the square in the $i$th row from the
% bottom and the $j$th column from the left? (Again, you are only allowed to move up or right.)
\end{Parts}
\Question{That's Numberwang!}
Congratulations! You've earned a spot on the game show "Numberwang".
\begin{Parts}
\Part How many permutations of NUMBERWANG contain "GAME" as a substring? How about as a subsequence (meaning the letters of "GAME" have to appear in that order, but not necessarily next to each other)?
\nosolspace{2cm}
% \Part In round 1 of Numberwang, a positive integer is worth 1 point if it is divisible by 2, 3, or 5, and it is worth 0 points otherwise. In total, how many points are the first 100 positive integers worth? (\textbf{Hint: } Use Inclusion-Exclusion.)
% \nosolspace{2cm}
\Part In round 1 of Numberwang, each player chooses an ordered sequence of 5 digits. A valid sequence must have the property that it is non-increasing when read from left to right. For example, 99621 is a valid sequence, but 43212 is not. How many choices of valid sequences are there? (\textbf{Hint: } Relate the problem to balls and bins.)
\nosolspace{2cm}
\Part To win round 2 of Numberwang, a contestant must 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}$. How many ways are there to pick a winning set of integers?
\nosolspace{2cm}
\end{Parts}
\Question{Shipping Crates}
A widget factory has four loading docks for storing crates of ready-to-ship widgets. Any time a loading dock contains at least 5 crates, a truck picks up 5 crates from that dock and ships them away (e.g., if 6 crates are sent to a loading dock, the truck removes 5, leaving 1 leftover crate still in the dock).
Suppose the factory produces $8$ indistinguishable crates of widgets and sends each crate to one of the four loading docks. After all the shipping has been done, how many possible configurations of leftover crates in loading docks are there? (We consider two configurations to be the same if, for every loading dock, the two configurations have the same number of leftover crates in that dock.)
\nosolspace{2cm}
\Question{Picking Teams}
\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 25 students in CS 70 have a strange way of picking a study group. Each person is given a distinct number 1 through 25 based on random chance, and participants may form a group as long of the sum of their numbers is \textbf{at most} 162.
(The TAs are afraid of the number 162 for some reason...)
How many different study groups are possible? That is, how many different subsets of students are there, which are allowable under the ranking rule? (\textbf{Hint:} $162 = [(\sum_{i=1}^{25} i) - 1]/2)$)
\item UC Berkeley is forming a new, $n$-person robotics team. There are $2n$ interested students: $n$ mechanical engineers and $n$ programmers. (Assume that no student is both a mechanical engineer and a programmer.)
Find the number of distinct $n$-person teams.
\item Suppose that all robotics teams must also name a team captain who is a mechanical engineer. Find the number of ways to pick an $n$-person team with a mechanical engineer as the captain.
\nosolspace{2cm}
\end{enumerate}
\bigskip
\textit{\textbf{Note:} This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare.}
\rule{6in}{2px}
\bigskip
\section*{Part 2: Optional Problems}
\bigskip
\Question{Maze}
Let's assume that Tom is located at the bottom left corner of the $9 \times 9$ maze below,
and Jerry is located at the top right corner. Tom of course wants to get to
Jerry by the shortest path possible.
\begin{figure}[H]
\centering
\includegraphics[width=0.5\linewidth]{src/problems/counting/resources/figures/maze.png}
\end{figure}
\begin{Parts}
\Part How many such shortest paths exist?
\nosolspace{1in}
\Part How many shortest paths pass through the edge labeled $X$?
\nosolspace{1in}
\Part The edge labeled $Y$? Both the edges $X$ and $Y$? Neither edge $X$ nor edge $Y$?
\nosolspace{1in}
\Part How many shortest paths pass through the vertex labeled $Z$? The vertex labeled $W$? Both the vertices $Z$ and $W$? Neither vertex $Z$ nor vertex $W$?
\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}