\documentclass[letterpaper,11pt]{article}

\newcommand{\removefromfile}[1]{}

\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage[most]{tcolorbox}
\renewcommand{\theenumi}{\alph{enumi}}
\begin{document}
\title{{\bf Problem Set 2 Solutions} }
\author{Name: TODO}

\date{}
\maketitle

\section*{Collaborators}
\begin{tcolorbox}
    List collaborators, if any. 
\end{tcolorbox}

\section*{Use of 312 Learning Assistant}
\begin{tcolorbox}
    List which problems you used the 312 Learning Assistant on.
\end{tcolorbox}

\newpage
\section{Pigeonhole practice (10 points)}

In the following problem assume that every year has exactly 365 days and, of course, 12 months.
Ignore leap years and ignore year of birth.
\begin{enumerate}
    \item (3 points) Show that if there are 200 people registered for CSE 312, then there is some month such that at least 17 people were born in that month (again, ignore year of birth).
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}

    \item For each of the following properties a group of people might possess, either give the minimum number of people that must be in a group to ensure that the property holds, or else indicate that the property need not hold even for arbitrarily large groups of people.
    In either case, justify your answer. 
    \begin{enumerate}
        \item[(i)] (2 points) At least 3 people were born on the same day of the week.
        \begin{tcolorbox}
            TODO: Your solution here.
        \end{tcolorbox}

        \item[(ii)] (2 points) At least 4 people were born in the same month.
        \begin{tcolorbox}
            TODO: Your solution here.
        \end{tcolorbox}

        \item[(iii)] (3 points) At least 2 people were born exactly one week apart.
        \begin{tcolorbox}
            TODO: Your solution here.
        \end{tcolorbox}
    \end{enumerate}
\end{enumerate}

\newpage
\section{Thinking Combinatorially (10 points)}
We saw in Lecture 2 that combinatorial proofs can be more elegant than algebraic proofs and also provide insights into an equation that goes beyond algebra. Here's your opportunity to try your hand at this.
Prove the following identity using a \emph{combinatorial argument};
an algebraic solution will be marked substantially incorrect.

\[\textup{For all integer }a\geq b\geq 0,\qquad \binom{a}{b}2^{a-b} = \displaystyle\sum_{i=b}^a{\binom{a}{i}\binom{i}{b}}\]

{\bf Hint:} The following hint provides one possible way to think about the problem; you are welcome to use a different approach if you prefer.
    \begin{itemize}[nosep]
        \item For the left hand side: Think about how you can apply the product rule so that for the first step there are  $\binom{a}{b}$ choices and for the second step there are  $2^{a-b}$ choices.
        \item For the right hand side, first figure out what counting scenario gives $\binom{a}{i}\binom{i}{b}$. After that, think about how you can modify the scenario to include all possible values of $i$; your result will use the sum rule.
    \end{itemize}

\begin{enumerate}
    \item[(i)] (5 points) Provide a counting scenario where the number of choices is equal to the left hand side of the equation. Explain your reasoning.
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}

    \item[(ii)] (5 points) Find another way to count the same quantity that gives the expression on the right hand side. Use the two different ways of counting to justify the identity.  
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
\end{enumerate}

\newpage

\section{How many ways? (8 points)}

\begin{enumerate}
    \item (4 points) 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.)
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}

    \item (4 points) 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.)
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
\end{enumerate}

\newpage
\section{Principle of Inclusion and Exclusion (10 points)}
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{Sample Spaces and Probabilities (20 points)}
\begin{tcolorbox}
    Do the tasks on gradescope. Nothing to write for this question.
\end{tcolorbox}

\newpage\section{Random Questions (16 points)}

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 compute the event size and conclude with the probability.
\begin{enumerate}
    \item (4 points) You flip a fair coin 50 times.  What is the probability of exactly 20 heads?
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
    
    \item  (4 points) 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?
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
    
    \item  (4 points) Suppose you randomly permute the numbers $1, 2, \ldots, 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.)
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
    
    \item  (4 points) 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.)
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
\end{enumerate}

\end{document}


