Here are the /Solutions.

Solutions to all problems should be as simple as possible. Justify your solution in each case.

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.

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.

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.

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.

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?