Problem 0: Complete the Canvas quiz "PSet 10 - Counting".

Problem (10 points): Kismet is a dice game similar to Yahtzee. Like Yahtzee, Kismet is played with five six-sided dice that players roll and reroll with the goal of making poker-like combinations of numbers showing on the dice. Some of the combinations in Kismet are based on the colors of the numbers: ones and sixes are black, twos and fives are red, and threes and fours are green. For example, a flush is a roll where all the dice are the same color (so all one and sixes or all twos and fives or all threes and fours).

One of the combinations is Two Pair Same Color, which earns a non-zero score if there is a pair dice showing the same number as each other, and a different pair of dice showing the same number as each other and the same color as the first pair. The two pairs may be of the same number, and the color and number of the fifth die does not matter.

Consider the following attempt to count the number of ways to roll a Two Pair Same Color on the first roll of a turn by using the multiplication rule (the count is needed as the numerator in the probability formula for equally likely events so we can calculate the probability of rolling Two Pair Same Color on the first roll of a turn): build a Two Pair Same Color roll by 1) choosing the color (3 options); 2) choosing the four dice of that color (${5 \choose 4} = 5$ options); 3) choosing which of those four dice are the first pair (${4 \choose 2} = 6$ options); 4) choosing the value of the first pair (2 options); 5) choosing the value of the second pair (2 options); 6) choosing the value of the fifth die (6 options)

• Explain why this setup is incorrect (there may be more than one reason; you only need to give one).
• Give a correct setup (using any necessary rules in addition to the multiplication rule) and compute the number of ways of rolling a Two Pair Same Color.

Problem (15 points): Chomp is a two-player game played with a chocolate bar divided into pieces arranged in a $m$-column, $n$-row grid. Each player takes turns choosing a remaining piece of chocolate and eating that piece and every remaining piece below and to the right of it. The player who eats the piece in the upper left corner loses. (Let's say that piece has a raisin in it – apparently a lot of people think raisins are gross? I like raisins, so I wouldn't mind losing.)

As a consequence of the "eat everything below and to the right" rule, the remaining pieces in a given column are always at the top of that column, and each column is at least as big the column to the right. So the shape of the remaining portion of the chocolate bar can be described as a non-increasing sequence of integers between 0 and $n$ (inclusive). For example, the third state in the example on the Wikipedia page would be written $43332$.

Consider Chomp played on a 6-column, 5-row chocolate bar.

• How many states (shapes of the remaining portion of the bar) have 5 pieces remaining in the leftmost column and 2 in the rightmost? (Hint: there need to be three steps down from 5 to 2 going from the leftmost column to the rightmost; how many ways are there of distributing those steps?)
• How many states have 3 pieces remaining in the leftmost column and 0 in the rightmost?
• How many states have the leftmost column three larger than the rightmost?

Consider Chomp played on an $m$-column, $n$-row chocolate bar.

• How many states have the leftmost column three larger than the rightmost?
• The Wikipedia page states (correctly) that the total number of states is ${m + n \choose n}$. Show that for $m \ge 2$, ${m + n \choose n} = \sum_{d=0}^{n} \left( (n+1-d)\cdot{m+d-2 \choose d} \right)$ by explaining how both the left-hand and right-hand sides count the states in $m$-by-$n$ Chomp.