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 3n outcomes in general. Show that if we exclude the case where all participants get chocolate, the remaining 3n-1 cases split evenly into (3n-1)/2 cases where an odd number of participants get prizes, and (3n-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.)