# 1. Presidents and vice presidents

Show that, for all n∈ℕ,

Hint: What does each side of the equation count?

## 1.1. Solution

### 1.1.1. Method 1: combinatorial proof

Here we follow the suggestion in the hint.

On the left-hand side, we consider for each k all subsets of size k of an n-element set, and for each such subset have k(k-1) possibilities. This occurs, for example, if we choose from each of the subsets two marked nodes in order without replacement. So the left-hand side counts all the ways to choose a subset of a set of n elements with two of the nodes marked with distinguishable marks.

On the right-hand side, we can imagine choosing one marked element (n choices), a second distinct element with a distinct mark (n-1) choices, and then a subset of the remaining n-2 elements. This also gives us a subset of a set of n elements with two of the nodes marked with distinguishable marks.

Since both sides count the same thing, the two quantities must be equal.

### 1.1.2. Method 2: algebraic proof

We can also solve the problem just by symbol manipulation:

# 2. Mystery chocolates

A box of n chocolates contains m in flavors that you don't like. Assuming that you choose r of the chocolates to eat uniformly at random, what is the probability that at least one of them is a flavor that you don't like?

## 2.1. Solution

There are several ways to do this. The easiest ways first compute the probability that we get no bad chocolates, and then subtract this from 1.

First method: Suppose we are choosing a subset of r chocolates all at once, with each subset having a probability of exactly of being chosen. Since there are subsets that are all likable, the probability we don't get an all-likable subset is . (Note we get the same result if we assume all ordered sequences of r chocolates are equally likely: now we have (n-m)_{r} all-good sequences out of (n)_{r} total sequences, so we again get 1-(n-m)_{r}/(n)_{r}.)

Second method: Suppose we choose chocolates one at a time, and compute the probability that we get no bad chocolates. For i in 1..r, let A_{i} be the event that the i-th chocolate is good. Then Pr[A_{1}∧A_{2}∧...A_{r}] = ∏[i=1..r] Pr[A_{i}|A_{1}∧...∧A_{i-1}]. We can compute the probability that the i-th chocolate is good conditioned on the previous chocolates being good by observing that there are n-m-i+1 good chocolates left out of n-i+1 remaining chocolates. So we have Pr[A_{1}∧...∧A_{n}] = ∏[i=1..r] (n-m-i+1)/(n-i+1) = (∏[i=1..r] (n-m-i+1))/(∏[i=1..r] (n-i+1)) = (n-m)_{r}/(n)_{r}. So again we get a probability of 1-(n-m)_{r}/(n)_{r} of choosing at least one bad chocolate.

# 3. Monochrome sets

Suppose we have a set S of n elements, and we assign each element one of r colors. Call a subset A of S **monochrome** if every element of A is assigned the same color. Given n, r, and k, show that there exists a coloring of S in which at most subsets A of size k are monochrome.

Hint: On average, how many subsets are monochrome in a random coloring?

## 3.1. Solution

Suppose we assign each element each color with probability 1/r. Then for each fixed color, the probability that every element in a subset A of size k has that color is (1/r)^{k}. So summing over all colors gives r(1/r)^{k} = r^{1-k}.

Let X_{A} be the indicator variable for the event that A is monochrome; we've just shown that E[X_{A}] = r^{1-k}. Now compute the total expected number of monochrome k-subsets by summing over all A: E[total monochrome k-subsets] = E[∑ I_{A}] = ∑ E[I_{A}] = . Since we get this value on average for a random coloring, there must be some specific coloring that is no bigger.