\documentclass[12pt]{article}
\usepackage{comment}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amssymb}

\begin{document}

\centerline{\bf Homework 8 MORALLY Due Apr 11 at 9:00AM}
\newcommand{\MOD}{{\rm MOD}}
\newcommand{\PRIMES}{{\rm PRIMES}}
\newcommand{\NSQ}{{\rm NSQ}}
\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}^+}

\newcommand{\NCU}{{\rm NCU}}
\newcommand{\NCUZ}{{\rm NCUZ}}

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


\centerline{\bf WARNING: THIS HW IS FOUR PAGES LONG!!!!!!!!!!!!!!!!!}

\begin{enumerate}

\item 
(0 points but please DO IT)
What is your name?

\item
(40 points)
For this problem when I ask you to SHOW something, give
a combinatorial proof (NOT algebraic, NOT by induction).

\begin{enumerate}
\item
(0 points) 
Let  $n=n_1+n_2$. How many ways can you form a word from $n_1$ $a$'s and $n_2$ $b$'s. 


\item 
(10 points) 
Show if $n=n_1+n_2$ then

$$\frac{n!}{n_1! n_2!} = \frac{(n-1)!}{(n_1-1)!n_2!} + \frac{(n-1)!}{n_1!(n_2-1)!}$$

\item
(10 points) 
Show if $n=n_1+n_2+n_3$ then

$$\frac{n!}{n_1! n_2! n_3!} = \frac{(n-1)!}{(n_1-1)!n_2!n_3!} + \frac{(n-1)!}{n_1!(n_2-1)!n_3!}+\frac{(n-1)!}{n_1!n_2!(n_3-1)!}$$

\item
(10 points) 
Assume $n=n_1 + \cdots + n_k$. 
Write down an expression for 
$$\frac{n!}{\prod_{i=1}^k n_i!}$$

 similar to those above. DO NOT use $\cdots$. 

\item
(10 points) 
Prove the statement made in the last part.
\end{enumerate}

\ifshowsoln

{\bf SOLUTION}

1) If the $a$'s and $b$'s were all distinguished (e.g., use $a_1, a_2, \ldots a_{n_1}, b_1, \ldots, b_{n_2}$)
then the answer would be $n!$. But we overcounted in a very precise way! YADA YADA YADA

$\frac{n!}{n_1! n_2!}$

2) Consider the problem in part 1. Lets solve it a different way! 

The number of words that begin with $a$ is the same problem but with $n_1-1$ $a$'s and $n_2$ $b$'s, so the answer is

$\frac{(n-1)!}{(n_1-1) ! n_2!}$

The number of words that begin with $b$ is the same problem but with $n_1$ $a'$'s and $n_2-1$ $b$'s.
so the answer is

$\frac{(n-1)!}{(n_1) ! (n_2-1)!}$

Hence the answer to the problem is the sum. 

3) and 4) similar. 

{\bf END OF SOLUTION}

\fi 

\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage

\item
(20 points)
Bill just finished admissions for his REU program! There were four projects:
Markets (MA), Ramsey Theory (RA), Bias in ML (BI), and Computational Geometry (CG).
Students who applied could indicate which set of projects they would be happy to be assigned to.

(The next four statements say the number of students who are happy with, say, MA; however, those students
might like other projects as well.) 

27 were happy with MA

12 were happy with RA

20 were happy with BI

29 were happy with CG

\bigskip

1 was happy with both MA and RA

13 were happy with both MA and BI

7 were happy with both MA and CG

2 were happy with both BI and CG

\bigskip

1 was happy with MA and RA and BI

1 was happy with MA and RA and CG

1 was happy with MA and BI and CG

1 was happy with RA and BI and CG

\bigskip

1 was happy with MA or RA or BI or CG


\begin{enumerate}
\item
(20 points) How many applied to the program? Show work. 
\item
(0 points) There is something else you can deduce from this data. What is it?
(This question might not have a unique answer which is why its worth 0 points). 
\end{enumerate}


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(20 points- 4 points each)
Bill makes his Darling a lunch every day!
The lunch is
\begin{itemize}
\item
{\bf Main Part} Sumatran Elephant's ear on a bun OR Leatherback Turtle Soup OR Western Lowland Gorilla in Sloppy-Joe style OR 
Fried Panda (from Panda Express). 
\item
{\bf Fruit} Apple OR Pomegranate OR Coconut.
\item 
{\bf Desert} Applesauce OR Ice cream.
\end{itemize}

And NOW for our problem.

\begin{enumerate}
\item
How many ways can Bill make Darling lunch?
\item
One morning Darling skips breakfast so she asks Bill to give her TWO main parts and TWO fruits. 
NOW how many ways can Bill make Darling lunch? 
\item 
Now things are back to normal (one from each category). 
Darling says {\it Precious Bill- I do not like having Apples AND Applesauce}.
NOW how many ways can Bill make Darling Lunch?
\item 
Another morning Darling skips breakfast so she asks Bill to give her TWO main parts and TWO fruits. 
AND do NOT have both an apple and applesauce. 
NOW how many ways can Bill make Darling lunch? 
\item
Darling says {\it Precious Bill, I do not want to eat an endangered species, but its okay to have
apples and applesauce}. NOW how many ways can Bill make Darling Lunch?
(You will need to look up which of the animals Darling likes to eat are endangered. 
Assume Pandas are an endangered species---there is some debate about that.
\end{enumerate}


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(20 points--5 points each)
The Vorlons play card games with a cards that have ranks in the set $\{1,2,\ldots,30\}$
and suites in the set $\{1,\ldots,10\}$. 
In Vorlon Poker, each player gets 7 cards. 
\begin{enumerate}
\item
A {\it Prime Hand} is a hand where all of the cards have a prime rank.
(e.g., 
$$\{(2,1), (2,4), (3,2), (3,4), (5,1), (17,8), (19,2) \}.$$

What is the probability of getting a Prime Hand?

\ifshowsoln
{\bf SOL}

The total number of hands is $\binom{300}{7}$.

The cards with prime rank have (rank,suite) in

$$\{2,3,5,7,11,13,17,19,23,29\} \times \{1,\ldots,10\}$$

so thats $10\times 10=100$. 

Hence the number of prime hands is $\binom{100}{7}$. 
Hence the answer is

$$\frac{\binom{100}{7}}{\binom{300}{7}}$$

{\bf END OF SOL}
\fi 

\item
A {\it Distinct Prime Hand} is a hand where all of the cards have a prime rank.
(e.g., 
$$\{(2,1), (3,4), (5,2), (7,4), (11,8), (17,1), (19,2) \}.$$

What is the probability of getting a Distinct Prime Hand? 

\ifshowsoln
{\bf SOL}

The total number of hands is $\binom{300}{7}$.

The cards with prime rank have (rank,suite) in

$$\{2,3,5,7,11,13,17,19,23,29\} \times \{1,\ldots,10\}$$

The number of ways of choosing 7 different primes out of the 10 is
$\binom{10}{7}$.  

Once you have the primes you then assign each one a suite. 
That can be done in $10^7$ ways. 

Hence the number of distinct-prime hands is 

$\binom{10}{7}10^7$.

So the prob of getting a distinct-prime hand is 

$$\frac{\binom{10}{7}10^7}{\binom{300}{7}}$$

{\bf END OF SOL}
\fi 


\item
A {\it Royal Prime Hand} is when all of the ranks are primes,
all of the suites are primes.
(e.g.,
$$\{ (2,2), (2,3), (5,5), (5,2), (11,3), (13,5), (23,2) \}.$$
)

What is the probability of getting a Royal Prime Hand? 

\ifshowsoln

{\bf SOL}

The number of cards that have prime rank and prime suites is

$$\{2,3,5,7,11,13,17,19,23,29\} \times \{2,3,5,7\}$$

so thats $10\times 4=40$. 

{\bf END OF SOL}

\fi 

\item
A {\it Royal Distinct-Prime Hand} is when all of the ranks are distinct primes,
all of the suites are primes.
(e.g.,
$$\{ (2,2), (3,3), (5,5), (7,2), (11,3), (13,5), (23,2) \}.$$
)

What is the probability of getting a Royal Distinct-Prime Hand? 

\ifshowsoln

{\bf SOL}

The total number of hands is $\binom{300}{7}$.

The number of ways of choosing 7 different primes out of the 10 is
$\binom{10}{7}$.  

Once you have the primes you then assign each one a prime suite. 
That can be done in $4^7$ ways. 

Hence the number of distinct-prime hands is 

$\binom{10}{7}4^7$.

So the prob of getting a distinct-prime hand is 

$$\frac{\binom{10}{7}4^7}{\binom{300}{7}}$$

{\bf END OF SOL}
\fi 

\end{enumerate}

\end{enumerate}
\end{document}