\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\newcounter{theproblem} \setcounter{theproblem}{1}
\newcommand{\N}{\mathbb{N}}
\newcommand{\st}{{\text{\huge {.}}}\;}
\newenvironment{problem}[1][]
{\noindent{{\color{blue}\large\bf
\arabic{theproblem}. #1} \stepcounter{theproblem}\vspace{0.3cm}}\\}
{\vspace{0.5cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}\newpage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\noindent{\color{blue}{\Large\bf Homework 10 \hfill 21-127 Concepts of Math \hfill due 12.06.2012}\\
\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Assignment begins here! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\color{blue}\large\bf Name:} % WRITE YOUR NAME HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Andrew ID:} % WRITE YOUR ANDREW ID HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Section:} % WRITE YOUR RECITATION SECTION HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Collaborators:} % LIST ANYONE YOU WORKED WITH HERE
\vspace{0.3cm}\\
{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
\begin{problem}[Can You Take This To The Bank? (15 pts)]
Consider the following claim and proof. Is the proof correct? If not, what is wrong?\vspace{0.2cm}\\
Furthermore, is the claim correct? If not, fix it!
\begin{quote}
Consider 4 buckets of coins: one bucket contains pennies, one contains nickels, one contains dimes, and one contains quarters. There are over 50 coins in each bucket (so we don't have to worry about running out of any type of coin).\vspace{0.2cm}\\
We want to select 50 coins from these buckets; we want to make sure that we select at least 10 pennies and at least 10 nickels but at most 10 dimes and at most 10 quarters.\vspace{0.2cm}\\
{\bf Claim:} The number of ways to do this is
\[ \binom{53}{3}-\binom{11}{3}=23261\]
{\it Proof:} Consider the total number of ways to select 50 coins from 4 types, with no added restrictions. This is selecting $k=50$ objects from $n=4$ types, so there are $\binom{53}{3}$ ways to do this.\vspace{0.2cm}\\
Now, we want to remove from this total the number of ways to select the coins where we do pick at least 10 pennies and at least 10 nickels but also at least 11 dimes and at least 11 quarters. To count these selections, we just want to actually select all of those coins (there are 42 total) and then select 8 more from all four types. We know there are $\binom{11}{3}$ ways to choose $k=8$ objects from $n=4$ types.\vspace{0.2cm}\\
Subtracting the second number from the first, we get the number given in the claim.
\end{quote}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Share Share Share, Share Your Booty (30 pts)]
Suppose we have 10 pirates who need to divvy up 100 pieces of gold.\vspace{0.2cm}\\
Suppose Captains Redbeard and Blackbeard are among the 10 pirates.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item How many ways are there to divvy the gold so that Redbeard gets at least 5 pieces of gold but Blackbeard gets at most 5 pieces?
\item How many ways are there to divvy the gold so that Redbeard gets at least 10 pieces of gold but Blackbeard gets somewhere between 5 and 15 (inclusive) pieces of gold?
\item How many ways are there to divvy the gold so that Redbeard gets somewhere between 0 and 10 (inclusive) pieces of gold and Blackbeard gets somewhere between 10 and 20 (inclusive) pieces of gold?\vspace{0.2cm}\\
(Hint: Use Inclusion/Exclusion. Consider the sets of outcomes where Redbeard gets at least 11, where Blackbeard gets at most 9, and where Blackbeard gets at least 21. Do these sets overlap?)
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Induction? We Don't Need No Stinking Induction (30 pts)]
In this problem, you will prove the following summation formula that you proved by induction weeks ago!
\[ \forall n\in\N\st\quad \sum_{k=1}^n k^3 = \left(\dfrac{n(n+1)}{2}\right)^2 \]
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Prove the following equality by {\it evaluating} the binomial coefficients. (This is easy algebra. Free points!)
\[ \forall k\in\N\st\quad k^3 = 6\binom{k}{3}+6\binom{k}{2}+\binom{k}{1} \]
\item Prove the equality in part {\bf\color{blue}(a)} by a {\it counting in two ways} argument.\vspace{0.2cm}\\
({\bf Hint:} Maybe consider words of length 3.)
\item Use the {\bf Summation Identity} (proven in lecture) and the equality you just proved in {\bf\color{blue}(a)} and {\bf\color{blue}(b)} to prove the claim given above in the problem statement!
\item {\bf\color{blue}Bonus:} Find and prove a formula for $\sum_{k=1}^n k^4$ using a method like this one.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Five! I Mean, Fore! (25 pts)]
Suppose we have a square park with dimensions 1 km $\times$ 1 km. We want to build a golf course on the park, but we only have space for 5 holes. In particular, for safety reasons, we need to consider the distance between the locations of the actual cups (the holes in the ground).\vspace{0.2cm}\\
Prove that no matter how we place 5 holes, there must exist two holes that are separated by a distance $d$ that satisfies $d\leq\frac{\sqrt{2}}{2}$ km. (Note: $\frac{\sqrt{2}}{2}\approx 0.707$)\vspace{0.2cm}\\
(Hint: Use the Pigeonhole Principle. It's up to you to identify the ``pigeonholes'' in this case. Also, note that we are allowed to place a hole on the boundary of the park.)\vspace{0.2cm}\\
Next, prove that this bound is {\it optimal}; that is, show me a way to place 5 holes on the park grounds (again, the boundary is allowed) such that the distance between any two holes is greater than or equal to $\frac{\sqrt{2}}{2}$ km.
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\end{document}