1. Pico, Fermi, Bagels

The guessing game of Pico, Fermi, Bagels starts with one player secretly choosing a three-digit number according to the following rules:

1. The first digit cannot be zero.
2. No two digits can be the same.

For example, 123 and 705 are allowed by the rules but 016 or 424 are not.

How many different three-digit numbers could the first player choose? Justify your answer.

1.1. Solution

There are 9 choices 1..9 for the first digit; whatever choice is made leaves 9 choices for the second digit and 8 for the third. Multiplying gives 9*9*8 = 648 choices.

2. Odd subsets

For each natural number n, let [n] = { 1, 2, 3, ..., n } = { x | 1 <= x <= n }.

1. Compute the number of subsets of [n] as a function of n.
2. Compute the number of subsets of [n] that contain at least one odd number.
3. Compute the number of subsets S of [n] for which |S| is odd.

2.1. Solution

1. 2ⁿ, since we can represent a subset of [n] as a sequence of n bits.

2. The easiest way to do this is to start with all 2ⁿ subsets and subtract out those that don't contain an odd number. Such a set must use the floor(n/2) even numbers in [n], so there are 2^floor(n/2) such subsets. Subtracting gives the answer 2ⁿ - 2^floor(n/2).

3. The tricky part here is to notice that exactly half of the 2ⁿ subsets have odd size. The easiest way I know to prove this is to pick some element (1, say), and set up a bijection between { S : |S| is odd } and { S : |S| is even } by the rule f(S) = S - {1} if S contains 1 and f(S) = S union {1} if S doesn't contain 1. It's easy to show that this is a bijection, since if S and S' both contain 1, then S - {1} = S' - {1} if and only if S = S', and if S and S' both don't contain 1, adding it won't make them equal either. So we have 2ⁿ = 2*(# of odd subsets) and (# of odd subsets) = 2^n-1.

3. Increasing sequences

A sequence x₁, x₂, ... x_n is increasing if x_i < x_j when i < j.

1. Compute the number of increasing sequences of length k consisting of integers in [n] as a function of n and k.
2. Compute the number of increasing sequences of length k consisting of integers where the first element of the sequence is exactly 1 and the last element is exactly n, again as a function of n and k.

3.1. Solution

1. Each increasing subsequence corresponds to exactly one set of k distinct elements of [n], and there are (n choose k) such sets.
2. Having fixed the first and last elements, we need to count how many ways to fill in the middle. But there are (n-2) elements to choose from and (k-2) to choose, giving (n-2 choose k-2) possibilities.

4. Two-to-one functions

A function f:A->B is two-to-one if for every element z of B there are exactly two distinct elements x and y of A such that f(x)=f(y)=z. Let A have 2n elements and B have n elements. Compute the number of two-to-one functions from A to B as a function of n.

4.1. Solution

Let B' be the set B x {0,1}, which has size 2n = |A|. Then there are exactly (2n)! bijections between A and B'. We can construct such a bijection in a second way by specifying a two-to-one function f and then choosing for each pair x,y with f(x)=f(y)=z which of x and y go to (z,0) and (z,1); there are two ways to do this for each of n pairs, so this gives a second way of counting the set of bijections as (# of 2-to-1 functions)*2ⁿ. Dividing gives the # of 2-to-1 functions as (2n)! 2^-n.

5. Odd hats

Each member of the International Society of Odd Hats wears a hat that consists of a red, blue, or green base trimmed with up to seven feathers each of which is also red, blue, or green. Assuming that the order and placement of feathers doesn't matter, how many members can join the Society before two end up with the same hat?

5.1. Solution

We need to count the number of distinct hats; by the PigeonholePrinciple this gives the bound on the number of members. Let's count the number of ways to feather a hat first: there are various ways to do this, but the quickest is to imagine we are distributing 7 indistinguishable "slots" among the four options red, blue, green, and missing, with no limit on how many slots we can assign to each option. There are (7+4-1 choose 4-1) = (10 choose 3) ways to do this. Multiplying by the 3 possible bases gives 3*(10 choose 3) = 3*10*9*8/6 = 360 possible hats.