\documentclass[letterpaper,11pt]{article}
\newcommand{\removefromfile}[1]{}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{graphicx}
\begin{document}
\title{{\bf Problem Set 2 Solutions} }
\author{insert your name here}
\date{}
\maketitle
\section*{Problem 1 (Combinatorial Identities) Solution}
Prove each of the following identities using a \emph{combinatorial argument}; an algebraic solution will be marked substantially incorrect. (Note that $a \choose b$ is 0 if $b > a$.)
\begin{enumerate}[label=(\alph*)]
\item $\displaystyle\sum_{k=0}^\infty{\binom{m}{k}\binom{n}{k}} = \binom{m+n}{n}$.\\
\textbf{Solution:}
\item $\displaystyle\sum_{k=0}^\infty{\binom{n}{k}\binom{k}{m}} = \binom{n}{m}2^{n-m}$.\\
\textbf{Solution:}
\end{enumerate}
\section*{Problem 2 (Rotating the table) Solution}
At a dinner party, all of the $n$ people present are to be seated at a circular table. Suppose there is a nametag at each place at the table and suppose that nobody sits down in their correct place. Use the pigeon-hole principle to show that it is possible to rotate the table so that at least two people are sitting in the correct place. Be sure to specify precisely what the pigeons are, precisely what the pigeonholes are, and precisely what the mapping of pigeons to pigeonholes is.\\
\textbf{Solution:}
\section*{Problem 3 (Stuff into stuff) Solution}
\begin{enumerate}[label=(\alph*)]
\item We have 10 people and 30 rooms. How many different ways are there to assign the (distinguishable) people to the (distinguishable) rooms? (Any number of people can go into any of the 30 rooms.)\\
\textbf{Solution:}
\item We have 20 identical (indistinguishable) apples. How many different ways are there to place the apples into 30 (distinguishable) boxes? (Any number of apples can go into any of the boxes.)\\
\textbf{Solution:}
\item We have 30 identical (indistinguishable) apples. How many different ways are there to place the apples into 8 (distinguishable) boxes, if each box is required to have at least two apples in it.?\\
\textbf{Solution:}
\end{enumerate}
\section*{Problem 4 (Sample Spaces and Probabilities) Solution}
For each of the following scenarios first describe the sample space and indicate how big it is (i.e., what its cardinality is) and then answer the question.
\begin{enumerate}[label=(\alph*)]
\item You flip a fair coin 50 times. What is the probability of exactly 20 heads?\\
\textbf{Solution:}
\item You roll 2 fair 6-sided dice, one red and one blue. What is the probability that the sum of the two values showing is 4?\\
\textbf{Solution:}
\item You are given a random 5 card poker hand (selected from a single deck). What is the probability you have a full-house (3 cards of one rank and 2 cards of another rank)?\\
\textbf{Solution:}
\item 20 labeled balls are placed into 10 labeled bins (with each placement equally likely). What is the probability that bin 1 contains exactly 3 balls?\\
\textbf{Solution:}
\item There are 30 psychiatrists and 24 psychologists attending a certain conference. Three of these 54 people are randomly chosen to take part in a panel discussion. What is the probability that at least one psychologist is chosen? What is the probability that exactly three psychologists are chosen?\\
\textbf{Solution:}
\item You buy ten cupcakes choosing from 3 different types (chocolate, vanilla and caramel). Cupcakes of the same type are indistinguishable. What is the probability that you have at least one of each type?\\
\textbf{Solution:}
\end{enumerate}
\section*{Problem 5 (Miscounting) Solution}
Consider the question: what is the probability of getting a \textbf{7-card} poker hand (order doesn't matter) that contains at least two 3-of-a-kind (3-of-a-kind means three cards of the same rank). For example, this would be a valid hand: ace of hearts, ace of diamonds, ace of spaces, 7 of clubs, 7 of spades, 7 of hearts and queen of clubs. (Note that a hand consisting of all 4 aces and three of the 7s is also valid.)
Here is how we might compute this:
\begin{quote} Each of the $52 \choose 7 $ hands is equally likely.
Let $E$ be the event that the hand selected contains at least two 3-of-a-kinds.
Then $$\Pr(E) = \frac{|E|}{{52 \choose 7}}$$
To compute $|E|$, apply the product rule. First pick two ranks that have a 3-of-a-kind (e.g. ace and 7 in the example above). For the lower rank of these, pick the suits of the three cards. Then for the higher rank of these, pick the suits of the three cards. Then out of the remaining $52-6 = 46$ cards, pick one. Therefore $$|E|= {13 \choose 2} \cdot {4 \choose 3}\cdot {4 \choose 3} \cdot {46 \choose 1} \quad \quad \text{ and hence }
\quad\quad \Pr(E) = \frac{{13 \choose 2}\cdot 4^2 \cdot 46}{{52 \choose 7}}.$$
\end{quote}
Explain what is wrong with this solution. If there is over-counting in $|E|$, characterize all hands that are counted more than once, and how many times each such hand is counted. If there is under-counting in $|E|$, explain which hands are not counted.
Also, give the correct answer for $\Pr(E)$.
\textbf{Solution:}
\section*{Problem 6 (Random Questions) Solution}
\begin{enumerate}[label=(\alph*)]
\item What is the probability that the digit 1 doesn't appear among $n$ digits where each digit is one of (0-9) and all sequences are equally likely?\\
\textbf{Solution:}
\item Suppose you randomly permute the numbers $1, 2, \ldots, n$, (where $n > 500$).
That is, you select a permutation uniformly at random. What is the probability
that the number $3$ ends up in the $130$-th position in the resulting permutation? (For example, in the permutation $1,3,2,5,4$ of the numbers $1\ldots 5$, the number 2 is in the 3rd position in the permutation and the number 4 is in the 5th position.)
\textbf{Solution:}
\item A fair coin is flipped $n$ times (each outcome in $\{H, T\}^n$ is equally likely). What is the probability that all heads occur at the end of the sequence? (The case that there are no heads is a special case of having all heads at the end of the sequence, i.e. 0 heads.)\\
\textbf{Solution:}
\end{enumerate}
\section*{Problem 7 (Ping Pong) Solution}
You can copy and paste this part of the template into a different PDF if you'd like. Any written or image components of the coding can be put here.\\
% TODO: This won't show anything until you give it path to a real file
\includegraphics[width=0.95\textwidth]{path/to/image.png}
\end{document}