/Solutions

1. Right angles gone bad

If x is a nonzero vector in (ℤ_p)ⁿ, where p is prime, exactly how many vectors in (ℤ_p)ⁿ 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ⁿ outcomes in general. Show that if we exclude the case where all participants get chocolate, the remaining 3ⁿ-1 cases split evenly into (3ⁿ-1)/2 cases where an odd number of participants get prizes, and (3ⁿ-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:

1. PINs consisting of an increasing sequence of digits.
2. PINs consisting of a decreasing sequence of digits.
3. PINs in which the same digit appears more than once, in any position.
4. 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.)