\documentclass[12pt]{exam}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[left=1in, right=1in, top=1in, bottom=1in]{geometry}
\newcommand\Q[1]{\question{\large{\textbf{#1}}}}
\newcommand\modulo{\ \texttt{\%}\ }
\newcommand\lshift{\ \texttt{<<}\ }
\newcommand\rshift{\ \texttt{>>}\ }
\newcommand\cgeq{\ \texttt{>=}\ }
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{5.65in}
\vspace{#1}
\end{framed}}
\pagestyle{head}
\headrule \header{\textbf{15-251 Assignment 3}}{}{\textbf{Page
\thepage\ of \numpages}}
\pointsinmargin \printanswers
\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\begin{document}
\addpoints
\begin{center}
\textbf{\large{15-251 : Great Theoretical Ideas In Computer Science
\\ \vspace{0.2in} Fall 2014
\\ \vspace{0.2in} Assignment 3
}}
\vspace{0.2in}
\large{Due: Thursday, Sep. 18, 2014 11:59 PM}
\end{center}
\vspace{0.5in}
\hbox to \textwidth{Name:\enspace\hrulefill}
\vspace{0.2in}
\hbox to \textwidth{Andrew ID:\enspace\hrulefill}
\vspace{0.2in}
% End title box
\vspace{0.5in}
\vspace*{1in}
\begin{center}
\gradetable[h][questions]
\end{center}
\begin{questions}
\setcounter{question}{-1}
\setcounter{numquestions}{-1}
\newpage\Q{Warmup}
\begin{parts}
\part{Suppose there are 170 CS majors, 80 ECE majors and 50 math majors in a class. Of these, 30 are
double majors in CS and ECE, 10 are double majors in ECE and math. If five students are triple
majors and there are 250 total students, how many of the students are double majors in CS and
math?}
\vspace{0.5in}
\part{How many ways can 6 pirates split 50 gold pieces if the first pirate needs at least 10 pieces, the
second needs at least 8, the third needs at least 6, the fourth needs at least 4, and the fifth needs
at least 2, and the sixth didn't really help with the plundering, so he can get any amount?
}
\vspace{0.5in}
\part{We have $n$ sandwiches to give out to some kittens. Each kitten is going to be assigned 2 sandwiches, and every sandwich can be assigned to multiple kittens. How many kittens do we need to in order to guarantee that there will be two kittens which are assigned the same 2 sandwiches?}
\vspace{0.5in}
\part{How many distinguishable ways are there to rearrange the letters in \\``OHMYGODIMONFIRE'' ?
}
\vspace{0.5in}
\part{Explain why \[\binom{3n}{3} = 3 \binom{n}{3} + 6 \binom{n}{2} n + n^3\] by counting in two ways. Come up with a set that both of these expressions count. (Hint: Start with the simpler side)}
\end{parts}
\newpage\Q{More Problems Than You Can Count}
\begin{parts}
\part[10] Klaas loves painting, and he wanted to include Peter in his hobby, so he challenged him to a painting game. Klaas will paint 29 points in the plane such that for any 3 points, at least two of them are at a distance less than one unit from each other. Then, if Peter could draw a unit circle around at least 15 of the points, he would win. If not, then Klaas wins. \\
Assuming that Klaas and Peter both play optimally, who will win this game? Prove your answer.
\begin{solution}
\end{solution}
\vspace{0.5 in}
\part[10] When you place an order at Razzy Fresh, you must choose either vanilla or chocolate frozen yogurt. Also, you must choose EXACTLY 2 toppings. There are 10 to choose from, 4 of which contain nuts, and 6 of which do not. An order consists of both a flavor and a choice of toppings.\\
Patrick decides to send his students on a field trip. There are 15,251 students, 7,625 or whom are female and 7,626 of whom are male. Every student will choose one of 250 Razzy locations in Pittsburgh to visit, with the restriction that the number of boys and girls in each Razzy store must differ by at most 1. In each restaurant, the students group into as many male/female couples as possible. Each couple will then place one order for the two of them to share. Since they want to feel special, every couple must choose a different order than all the other couples in their own restaurant. (If there is a single person left over, they can order whatever they want). \\
However, you are worried because every male student is allergic to nuts, and will die if they eat any. Patrick believes that there is a way for everyone to follow these rules and eat their frozen yogurt without anyone dying. Is he correct? Prove your answer.
\begin{solution}
\end{solution}
\end{parts}
\newpage\Q{Why Can't I Count All These Arrangements?}
\bigskip
\begin{parts}
\part[10] In lecture, we showed that the number of ways to divide 20 pieces of gold amongst 5 pirates is $\binom{24}{4}$ by counting all strings with $20$ G's and $4$ /'s. \\ \\
The following alternate method was suggested to count such strings: \\
Write down 20 G's. Each of the $4$ /'s can go to $21$ places, for a total of $21^4$ possibilities. The /'s are ``indistinguishable'', so their odering does not matter. Thus, we divide by $4!$ since we could have placed the $4$ /'s in any order. So the answer must be \[ \frac{21^4}{4!} \]
However, this is certainly not correct as it is not equivalent to our answer $\binom{24}{4}$, and in fact it is not even an integer! \\
Explain carefully and concisely what is wrong with this approach. In particular, does it overcount or undercount? Why?
\begin{solution}
\end{solution}
\vspace{0.5 in}
\part[15] David and Taehoon are making shishkebabs. Together, they have $b$ pieces of beef and $o$ pieces of onion, and
they will each get one shishkebab. A shishkebab is some non-empty sequence of pieces of onion and pieces of
beef, but neither person wants two pieces of beef next to each other. Also, they want to use up all of the pieces of beef and onion that they have. In how many ways can they create and choose their two shishkebabs? \\
For example, with $b=3, o=2$, there are 10 possible ways.
$(B, BOBO), (B, OBOB), (B, BOOB), (BO, BOB), (OB, BOB), \\
(BOB, BO), (BOB, OB), (BOBO, B), (OBOB, B), (BOOB, B)$
\begin{solution}
\end{solution}
\end{parts}
\newpage\Q{Counting Identities} \\
\begin{parts}
\part[15] Show that \\
\[\sum_{i=0}^{m}{ \binom{n-i}{m-i} \binom{k+i}{i}} = \binom{n+k+1}{m} \] \\
by making a combinatorial argument, i.e. counting in two ways. You should assume that $n \ge m$.
\begin{solution}
\end{solution}
\vspace{0.5 in}
\part[15] The binomial theorem \[(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^ky^{n-k} \] can be related to many problems in combinatorics. Use the binomial theorem to prove the following identity. \\
\[ \sum_{i=k}^{n}{\binom{i}{k}\binom{n}{i}} = \binom{n}{k}2^{n-k} \]
\begin{solution}
\end{solution}
\end{parts}
\newpage\Q{Counting to 251}
\begin{parts}
\part[3] Andy has tennis balls labeled $1 \dots 251$ in a pile that he wants to break apart. At each step, he chooses a pile with at least $2$ balls in it and splits it into two non-empty piles, not necessarily of equal size. He repeats this process until all the piles are of size $1$. \\
How many steps will this process take? \\
\begin{solution}
\end{solution}
\part[12]
Prove that the number of ways for Andy to carry out the process from part (a) is
\[\binom{251}{2}\binom{250}{2}\binom{249}{2} \cdots \binom{2}{2} \]
For two ways to be considered identical, they must split the same set and create the same two subsets at every single step in the process.
\begin{solution}
\end{solution}
\vspace{0.5 in}
\part[10] Victor and Venkat are helping their students to form homework groups, so they have every student fill out a form listing all of the other students who they would be willing to work with. \\
There are 251 students in the class, and every student lists exactly 168 other students who they would be willing to work with. For any two students in the class, if student A puts student B on their list, then student B will also have student A on their list. \\
Show that there must be some group of 4 students who are all willing to work with one another.
\begin{solution}
\end{solution}
\end{parts}
\end{questions}
\end{document}