\documentclass[12pt,HW250,ifthen]{article}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}
\usepackage{amsmath}

\begin{document}

\centerline{Homework 7, Morally due FRI Apr 5, 5:00PM. DEAD CAT Monday Apr 8 5:00}

(NOTE- Change of when its due is so that we can go over it in rec BEFORE the exam.)

\centerline{\bf THE HW IS TWO PAGES LONG!!!!!!!!!!!!!}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(20 points)
\begin{enumerate}
\item
(10 points)
WG, Jtwitty, and K are taking the class on a field trip
to the Combinatorics Museum! There are 32 students in the class

WG will drive 18 of them.

Jtwitty will drive 7 of them.

K will drive 7 of them.

How many ways can the students choose which cars they want to be in?
\item
(15 points)
Generalize the problem as follows.
$A_1,\ldots,A_n$ are taking the class on a field trip!
There are $S$ students in the class.

$A_1$ will drive $a_1$ of them.

$\vdots$

$A_n$ will drive $a_n$ of them.

(Note that $a_1+\cdots+a_n=S$.)

How many ways can the students choose which cars they want to be in?

\end{enumerate}



\item
(25 points)
Use a combinatorial argument (NOT algebraic, NOT by induction) to show that 
if $S=a+b+c$ then

$$\frac{S!}{a! b! c!} = \frac{(S-1)!}{(a-1)! b! c!} + \frac{(S-1)!}{a! (b-1)! c!} + 
\frac{(S-1)!}{a! b! (c-1)!}$$


\centerline{\bf GOTO NEXT PAGE}

\newpage



\item
(25 points)
Fill in the blanks in the following statement. Describe your reasoning.
BLANK will be a function of $k,n$.

{\it If $A\subseteq \{1,\ldots,n\}$ and $|A|=k$ then at least BLANK subsets of
$A$ have the same SUM.}



\item
(25 points)
Show that no matter how you 3-color the $4\times 19$ grid 
there will be a monochromatic rectangle.


\end{enumerate}

\end{document}