# 1. Right angles gone bad

If x is a nonzero vector in (ℤ_{p})^{n}, where p is prime, exactly how many vectors in (ℤ_{p})^{n} are orthogonal to x?

# 2. Some must have prizes

Suppose we have n participants in a psychological experiment. Some subset of the n participants receive prizes, and may choose between receiving an ice-cream sandwich (`I`) or a chocolate bar (`C`). The experimenters record a sequence of symbols indicating which prize if any each participant got. If no prize is recorded as `-`, for n=3 there are 27 possible outcomes:

--- --I --C -I- -II -IC -C- -CI -CC I-- I-I I-C II- III IIC IC- ICI ICC C-- C-I C-C CI- CII CIC CC- CCI CCC

It is easy to see that we expect 3^{n} outcomes in general. Show that if we exclude the case where all participants get chocolate, the remaining 3^{n}-1 cases split evenly into (3^{n}-1)/2 cases where an odd number of participants get prizes, and (3^{n}-1)/2 cases where an even number of participants get prizes.

Hint (added 2010-11-09): First think about the difference between the odd and even cases without worrying about the all-chocolate case.

# 3. For your convenience, the unique password allowed by these rules is printed on the front of your customer information pamphlet

A bank requires each of its customers to choose a 4-digit PIN. As a security measure, the following classes of PINs are forbidden:

- PINs consisting of an increasing sequence of digits.
- PINs consisting of a decreasing sequence of digits.
- PINs in which the same digit appears more than once, in any position.
- PINs consisting of 4 consecutive digits, in any order.

For example, the first rule excludes 1234, 0356, and 3789; the second excludes 9874, 5431, and 8430; the third excludes 1351, 2776, and 1212; and the fourth excludes 5876, 3120, and 9867. (Many other PINs are also excluded by one or more of these rules.)

How many PINs are left? (Justify your answer.)