Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 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?

## 1.1. Solution

Fix some nonzero x, and let k be any index for which xk ≠ 0. We will show that for any chose of pn-1 values for all yi where i ≠ k, we have exactly one choice for yk that makes y⋅x = 0. Recall that y⋅x = ∑ yixi = ∑i≠k yixi + ykxk. If we fix all yi for i≠k and require y⋅x = 0, this gives us an equation of the form a + ykxk = 0 (mod p), where a and xk are constants and xk in particular is nonzero. There is a unique solution yk = (xk)-1 (-a) (mod p) to this equation. It follows that having fixed the first n-1 values, we have exactly one choice for the last one, giving a total of pn-1 vectors orthogonal to x.

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

# 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.

## 2.1. Solution

First notice that the number of ways to give out k prizes is exactly

because we have (n choose k) ways to pick the k prize-winners and 2k choices of prizes once we have picked them.

Now let us subtract the odd-k cases from the even-k cases, which we can do by multiplying each case by (-1)k:

This doesn't quite match the binomial theorem, since we have k's in both exponents. But we can use xkyk = (xy)k to combine the two factors and then tack on the usual 1n-k to supply the other exponent:

If this were zero, we'd get that the odd and even cases match exactly. Instead, we have an extra even case when n is even and an extra odd case when n is odd. But subtracting off the all-chocolate case removes this leftover, giving an exact match between the remaining even and odd cases.

# 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.)