\documentclass[letterpaper,11pt]{article}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage[most]{tcolorbox}
\usepackage[margin=1in]{geometry}
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\theenumi)}
\renewcommand{\theenumii}{\roman{enumii}}
\renewcommand{\labelenumii}{(\theenumii)}
\begin{document}
\title{{\bf Problem Set 2 Solutions} }
\author{Name: TODO}
\date{}
\maketitle
\section*{Collaborators}
TODO: List collaborators, if any.
\newpage
\section*{Problem 1 (Thinking Combinatorially) Solution}
We saw in Lecture 3 that combinatorial proofs can be more elegant than algebraic proofs and also provide insights into an equation that goes beyond algebra. In this task, our goal is to develop the skill and intuition for such proofs.
To this end, prove each of the following identities using a \emph{combinatorial argument}; an algebraic solution will be marked substantially incorrect. (Note that $\binom{a}{b}$ is 0 if $b > a$.)
\begin{enumerate}
\item (8 points) $$\displaystyle\sum_{k=0}^\infty{\binom{m}{k}\binom{n}{k}} = \binom{m+n}{n}.$$
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item (7 points) $$\displaystyle\sum_{k=0}^\infty{\binom{n}{k}\binom{k}{m}} = \binom{n}{m}2^{n-m}.$$
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}
\newpage
\section*{Problem 2 (Pigeons in Pigeonholes) 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.
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\newpage
\section*{Problem 3 (Stars and bars) Solution}
\begin{enumerate}
\item We have 12 people and 36 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 36 rooms.)
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item We have 30 identical (indistinguishable) apples. How many different ways are there to place the apples into 20 (distinguishable) boxes? (Any number of apples can go into any of the boxes.)
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item We have 20 identical (indistinguishable) apples. How many different ways are there to place the apples into 6 (distinguishable) boxes, if each box is required to have at least two apples in it.?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}
\newpage
\section*{Problem 4 (Principle of Inclusion and Exclusion) Solution}
How many positive integers are there less than 1000 that are relatively prime to 100, i.e., have no common factor with 100?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\newpage
\section*{Problem 5 (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}
\item You flip a fair coin 100 times. What is the probability of exactly 30 heads?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\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 5?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item You are given a random 5 card poker hand (selected from a single deck, order doesn't matter). What is the probability you have a full-house (3 cards of one rank and 2 cards of another rank)?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item 10 labeled balls are placed into 20 labeled bins (with each placement equally likely). What is the probability that bin 1 contains exactly 3 balls?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item There are 24 psychiatrists and 30 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?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item You buy 12 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?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}
\newpage
\section*{Problem 6 (Random Questions) Solution}
\begin{enumerate}
\item
What is the probability that the digit 7 doesn't appear among
100 digits where each digit is one of (0-9) and all sequences are equally likely?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item Suppose you randomly permute the numbers $1, 2, \ldots, 100$.
That is, you select a permutation uniformly at random. What is the probability
that the number $75$ ends up in the $45$-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.)
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item A fair coin is flipped $100$ times (each outcome in $\{H, T\}^{100}$ 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.)
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}
\newpage
\section*{Problem 7 (Ping Pong [coding + written]) Solution}
We'll finally answer the long-awaited question: what's the probability you win a ping pong game up to $n$ points, when your probability of winning each point is $p$ (and your friend wins the point with probability $1-p$)? Assume you have to win by (at least) 2; for example, if $n=21$ and the score is $21-20$, the game isn't over yet.
\noindent Write your code for the following parts in the provided file: \href{https://edstem.org/us/courses/32027/lessons/51247/slides/286992}{\tt{cse312\_pset2\_pingpong.py}}.
\begin{enumerate}
\item (5 points) Implement the function {\tt{part\_a}}.
\item (15 points) Implement the function {\tt{part\_b}}. This function will NOT be autograded but you will still submit it; you should use the space here to generate the plot asked of you below.
\begin{enumerate}
\item Generate a plot similar to the one shown below in Python (without the watermarks). Details on how to construct it are in the starter code. Attach your plot in your written submission for this part. Your plot should:
\begin{itemize}
\item contain plot and axis titles,
\item have the same shape as the plot below,
\item use three different colors,
\item use three different line styles,
\item and a legend for the three lines.
\begin{tcolorbox}
TODO: Your plot (plot.png) here.
\begin{figure}[H]
\centering
\caption{Your plot.}
\includegraphics[width=0.95\textwidth]{plot.png}
\end{figure}
\end{tcolorbox}
\end{itemize}
\item Write AT MOST 2-3 sentences identifying the interesting pattern you notice when $n$ gets larger (regarding the steepness of the curve). Try to explain why it makes sense. (Later in the course, we will see why more formally.)
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item Each curve you make for different values of $n$ always (approximately) passes through 3 points. Give the three points $(x_1,y_1),(x_2,y_2),(x_3,y_3)$, and explain why intuitively this happens in AT MOST 2-3 sentences.
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}
\end{enumerate}
\end{document}