\documentclass[11pt, letter]{article}
\usepackage[inner=1.5cm,outer=1.5cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage{enumitem}
\usepackage[most]{tcolorbox}
\usepackage{amsmath}
\usepackage{hyperref}
\setcounter{section}{-1} 

\begin{document}
    \textbf{Submission instructions are in the homework handout. The handout is the final source of truth for instructions and question statements over this template file, which exists only for your convenience.}

    \section{Collaborators}
    \begin{tcolorbox}
        TODO: Add collaborators here.
    \end{tcolorbox}

    \newpage
    \section{Combinatorial Identities [16 points]}
    Prove each of the following identities using a \emph{combinatorial argument} (i.e., an argument that counts two different ways); an algebraic solution will be marked substantially incorrect. 
    \newline \newline
    For the purposes of these problems, using commutativity of multiplication and addition (i.e. $ab=ba$, $a+b=b+a$), and distributivity/factoring ($a(b+c)=ab+ac$) are allowed as part of a combinatorial argument. Any other algebra facts (e.g. Pascal's Rule about combinations, the definition of combinations/permutations in terms of factorials, canceling numbers that appear in numerators and denominators) would make it an algebraic solution, not a combinatorial one. 

    \begin{enumerate}[label=(\alph*)]
        \item $\displaystyle\sum_{k=0}^m {\binom{m}{k}\binom{n}{k}} = \binom{m+n}{m}$. You may assume that $n \geq m \geq 0$. Hint: Start with the right-hand side and imagine you are choosing a team of $m$ people from a group of people consisting of $n$ Americans and $m$ Canadians. (8 points)
        
        \item
        $\displaystyle\sum_{k=m}^n {\binom{n}{k}\binom{k}{m}} = \binom{n}{m}2^{n-m}$. Assume that $n \geq m \geq 0$.
        Hint: Think about choosing a committee from n people of which some subset are leaders. (8 points)
    \end{enumerate}
        
    \begin{tcolorbox}
        \begin{enumerate}[label=(\alph*)]
            \item TODO: Your solution here
            \item TODO: Your solution here
        \end{enumerate}
    \end{tcolorbox}

\newpage
\section{Feeling Squabished [10 points]}
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 pigeonhole 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{Club Sandwich [12 points]}

\begin{enumerate}[label=(\alph*)]
    \item We have 10 distinguishable clubs and 55 distinguishable students. How many different ways are there to assign the students to the clubs? (Any number of students can be a member of any of the 10 clubs.) (4 points)

    \item We have 42 identical (indistinguishable) sandwiches. How many different ways are there to place the sandwiches into 12 (distinguishable) boxes? (Any number of sandwiches can go into any of the boxes.) (4 points)

    \item We have 42 identical (indistinguishable) sandwiches. How many different ways are there to place the sandwiches into 7 (distinguishable) boxes, if each box is required to have at least three sandwiches in it? (4 points)
\end{enumerate}

    \begin{tcolorbox}
\begin{enumerate}[label=(\alph*)]
        \item TODO: Your solution here
    \item TODO: Your solution here
    \item TODO: Your solution here
  \end{enumerate}
    \end{tcolorbox}

    \newpage
    \section{In PIE We Crust [10 points]}
A router in the network has three paths along which it can send packets. It has 185 distinct packets that need to be randomly routed along one of the three paths, independently. In how many ways can the packets be distributed so that all of the paths have at least 1 packet traversing them, assuming the order of the packets distributed on one path doesn't matter?
\begin{tcolorbox}
    TODO: Your solution here
    \end{tcolorbox}

    \newpage
    \section{What are the Odds? [18 points]}
For each of the following scenarios,
\begin{center}
\begin{enumerate}[label=(\roman*)]\centering
    \item describe the sample space,
    \item indicate how big it is (i.e., what its cardinality is),
    \item and answer the probability question.
\end{enumerate}
\end{center}

\vspace{0.15in}
\begin{enumerate}[label=(\alph*)]
    \item You flip a fair coin 60 times.  What is the probability of exactly 25 heads? (3 points)

    \item You roll two fair 6-sided dice, one red and one blue. What is the probability that the sum of the two values showing is 5? (3 points)

    \item You are given a random 5 card poker hand (selected from a single deck with 52 cards with 13 ranks and 4 suits). What is the probability you have a full-house (3 cards of one rank and 2 cards of another rank)? (3 points)

    \item 25 labeled balls are placed into 12 labeled bins (with each placement equally likely).  What is the probability that bin 1 contains exactly 3 balls? (3 points)

    \item There are 25 computer scientists and 42 statisticians attending a certain conference. 3 of these 67 people are randomly chosen to take part in a panel discussion. What is the probability that at least one computer scientist is chosen? (3 points)

    \item You buy 12 donuts choosing from 3 different flavors (glazed, jelly, and chocolate). Donuts of the same type are indistinguishable. For this problem, each distinguishable collection of donuts is equally likely (for example, the probability of getting 12 chocolate donuts is equal to the probability of getting 4 glazed, 6 jelly, and 2 chocolate donuts in any order). What is the probability that you have at least one donut of each type? (3 points)
\end{enumerate}

    \begin{tcolorbox}
        \begin{enumerate}[label=(\alph*)]
            \item TODO: Your solution here
            \item TODO: Your solution here
            \item TODO: Your solution here
            \item TODO: Your solution here
            \item TODO: Your solution here
            \item TODO: Your solution here
        \end{enumerate}
    \end{tcolorbox}

    \newpage
    \section{Miscounting [14 points]}
Consider the question:  How many \textbf{7-card} poker hands (order doesn't matter) are there that contain at least two 3-of-a-kinds (3-of-a-kind means three cards of the same value)? 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.) 
\newline \newline
Here is how we might compute this:

\begin{quote} To compute the number of hands, apply the product rule using the following sequential process. 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 there are  \[\binom{13}{2} \cdot \binom{4}{3}\cdot \binom{4}{3} \cdot \binom{46}{1} \] hands.
\end{quote}
\newline
In this problem, you will find what is wrong with this solution. 
\begin{enumerate}[label=(\alph*)]
    \item Is there overcounting in the solution? That is, is there a hand that can be produced by multiple outcomes of the sequential process? If there is, give one concrete example of such a hand and two outcomes of the process that produce it. If there is not, briefly (1-2 sentences) explain why there isn't. (4 points)
    \item Is there undercounting in the problem? That is, is there a hand that cannot be produced by any outcomes of the sequential process? If there is, give one concrete example of such a hand and briefly explain why no outcome produces it. If there is no such hand, briefly explain why all hands are produced at least once. (3 points)
    \item Correct the calculation -- in this part you should produce a correct overall formula by subtracting/dividing out any errors that would fit in (a) and adding/multiplying in any errors that would fit in (b). (3 points)
    \item Find the answer differently -- take a different approach to counting this problem (e.g. use a different sequential process). Verify that you get the same number (via a different formula) than the last part. (4 points)
\end{enumerate}
\begin{tcolorbox}
        \begin{enumerate}[label=(\alph*)]
            \item TODO: Your solution here
            \item TODO: Your solution here
            \item TODO: Your solution here
            \item TODO: Your solution here
        \end{enumerate}
    \end{tcolorbox}

    \newpage
\section{The Probability of Coincidences [5 points]}
How many times have you bumped into someone who you know somewhere you didn't expect to see them and thought - what are the chances? In this section, we'll take a look at exactly what the chances are using our knowledge of probability to do a back-of-the-napkin calculation.
\newline \newline
You decide to check out the U-District Street Fair over the weekend. There are around $50,000$ people from the university visiting the fair. You can recognize around $50$ people from the university. Throughout the day, you see $200$ visitors, a subset of all visitors to the fair. Suppose that every size-200 subset of the population is equally likely to be seen. What are the odds that you see at least 1 person you know? Are the chances as low as you thought?
\begin{tcolorbox}
    TODO: Your solution here
    \end{tcolorbox}

    \newpage 
    \section{Is this a pigeon? [Extra Credit]}
The pigeonhole principle is surprisingly powerful and can be used to prove a variety of things -- find one application of the principle that interests you (it can be CS-related or not, serious or not -- my only requirements are that (a) you must find it interesting and (b) we shouldn't have proved it already in this course) and explain the proof to us. Make sure to clearly relate your proof to the theorem definition from lecture - what are the pigeons, what are the pigeonholes and what does the theorem tell us about them? (For this question only, you can feel free to Google without limits, as long as you cite your sources).
\begin{tcolorbox}
    OPTIONAL: Your solution here
    \end{tcolorbox}
\end{document}