\documentclass[12pt]{exam}
\usepackage{amsmath,amsfonts}
\usepackage{gensymb}
\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}

\begin{document}
\addpoints
\begin{center}
\textbf{\large{15-251 : Great Theoretical Ideas In Computer Science
 \\ \vspace{0.2in} Fall 2013
\\  \vspace{0.2in} Assignment 3 (The Awesome Homework)
}}

 \vspace{0.2in}

 \large{Due: Thursday, Sep. 19, 2013  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}

\newpage\Q{An Awesome Counting Competition} \\
Mr. Awesome has an awesome family that enjoys doing awesome things together. One day there was a huge storm, which ruined the Awesomes' plan to go climb Mt. Everest. Instead, Mr. and Mrs. Awesome had a competition counting random things that little Tommy Awesome came up with. They finished at the exact same time, but came up with different looking answers! Prove that Mr. and Mrs. Awesome are equally awesome by proving that their two results are the same. {\bfseries You must prove these by counting in two ways, just like Mr. and Mrs. Awesome did.}
\begin{parts}
\part[10]

Prove that $$\binom{x+n+1}{n} = \sum_{k=0}^n  \binom{x+k}{k}$$

\begin{solution}
\end{solution}

\part[10]

Prove that $$\binom{n}{k}2^{n-k} = \sum_{i=k}^n \binom{i}{k}\binom{n}{i}$$

\begin{solution}
\end{solution}

\end{parts}


\newpage\Q{The Awesome Family Performance}

\begin{parts}
\part[15]

The Awesomes are putting on an awesome performance and everyone is invited! The performance is divided into $k$ acts. To make the performance really awesome, each act needs to be at least as awesome as the previous act. The awesomeness of any act can be represented by a natural number between $1$ and $n$, where $n$ is the highest level of awesomeness. There is no restriction on the number of acts for each level of awesomeness. How many sequences of awesomeness levels are there that might describe the $k$ acts in the performance?

\begin{solution}

\end{solution}

\medskip
\part[15]

On the $45^{th}$ annual performance, the Awesomes change the rules completely. There are going to be just three acts. To attract more people, they want to keep the awesomeness of the first act (any integer that is) at least $2$. The awesomeness of the other two acts are (any integers that are) at least $1$. There is no limit to the awesomeness of individual acts, but to make things more awesome, the Awesomes want to keep the total awesomeness of all three acts exactly equal to $45$. How many different sequences of awesomeness of the three acts can there be?

\begin{solution}

\end{solution}
\end{parts}

\newpage\Q{The Awesome Family Dinner}

Suzy Awesome needs to get bread for the Awesome family dinner. Her neighborhood consists of $1 \times 1$ blocks, and can be considered as a grid where you can only move from $(x,y)$ to $(x+1, y)$, $(x-1,y)$, $(x, y+1)$, or $(x, y-1)$. The bread store is located at $(n,n)$, and her house is at $(0,0)$. The southeast section of town is not as awesome as the rest, so Suzy wants to avoid ever passing into it. In particular, she never wants to enter any $(x,y)$ with $x > y$. Let $A$ be the set of shortest paths Suzy can take to get to the store that avoids this area. \\

Back at the Awesome family dinner, there are $2n$ seats on a circular table, labeled $1$ through $2n$. Each seat is also marked either leader or follower. $n$ seats are to be marked as leader and $n$ seats are to be marked as follower. To give more preference to leaders, the family has decided that for any $i$, there should be at least as many leaders as followers in seats $1$ through $i$. They call such a labeling a valid labeling. Let $B$ be the set of valid labelings. 

\begin{parts}
\part[20]
The Awesome family wants to know the size of each of $A$ and $B$. This, however, proved quite difficult. Instead, prove that the sizes of $A$ and $B$ are the same by showing an explicit bijection between them.

\begin{solution}

\end{solution}

\end{parts}

\newpage\Q{Counting Subsets}

\begin{parts}
\part[15]

The Awesome family has 50 pets, one of each size $i$ for $i \in \mathbb{N}$ with $1 \leq i \leq 50$. The pets like to fight, but are smart enough to only fight the animals whose size is close to their own -- that is, of size 1 away from their size. The Awesomes want to take a family trip, but will only take a subset of pets where none will fight any other. How many ways can they choose a set of pets to bring?

\begin{solution}

\end{solution}

\part[15]

One day, the pets get bored of fighting the others that are similar to their size. Instead, they only fight those that have size exactly 2 away from their own size. How many ways can the Awesomes choose a set of pets to bring on their trip now?

\begin{solution}

\end{solution}

\end{parts}



\newpage\Q{Bonus Question}

Now the pets of the Awesome family have (fortunately!) stopped fighting, and they have acquired $n$ pets now (sizes do not matter for this question). They want to start the trips again. But Mr. Awesome has another constraint in mind. He will only call a collection of trips valid if in any two of the trips (not necessarily consecutive ones), there is at least one pet in each trip that is not part of the other trip. Mrs. Awesome is worried that this will greatly limit the number of trips that they can make. Mr. Awesome thinks otherwise. Your job is to find the maximum number of trips that they can make under this constraint.

\begin{parts}

\part[2]
Show that the collection of trips consisting of all $\lfloor n/2 \rfloor$-size subsets of pets is valid, and of size $\binom{n}{\lfloor n/2 \rfloor}$. 

\begin{solution}

\end{solution}

\part[4]
Mrs. Awesome, however, claims that this is the best they can do. She suggests the following argument. Starting from any valid collection of trips, and create a new valid collection as follows. Let $d$ be the maximum size of the subset of pets in any trip in the collection. If $d > \lfloor n/2 \rfloor$, then remove all trips with subsets of size $d$, and replace each of them with trips containing all their distinct subsets of size $d-1$. Remove duplicate trips, i.e., do not count any subset of pets more than once. She claims that this new collection is also valid and at least as large as the original one. Explain why Mrs. Awesome is right. 

\begin{solution}

\end{solution}

\part[4]
Mrs. Awesome says that you can continue reducing the sizes of the subsets as shown above until you only have subsets of size $\lfloor n/2 \rfloor$. Mr. Awesome is still not convinced. He argues that there are still subsets of size less than $\lfloor n/2 \rfloor$. 

From any valid collection containing trips with subsets of size at most $\lfloor n/2 \rfloor$, show how to create a new valid collection containing trips with subsets of size exactly $\lfloor n/2 \rfloor$ that is at least as large as the original collection. Use this to complete the argument that $\binom{n}{\lfloor n/2 \rfloor}$ is indeed the maximum number of trips that they can make.

\begin{solution}

\end{solution}
\end{parts}
\end{questions}
\end{document}
