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)ⁿ, where p is prime, exactly how many vectors in (ℤ_p)ⁿ are orthogonal to x?

1.1. Solution

Fix some nonzero x, and let k be any index for which x_k ≠ 0. We will show that for any chose of p^n-1 values for all y_i where i ≠ k, we have exactly one choice for y_k that makes y⋅x = 0. Recall that y⋅x = ∑ y_ix_i = ∑_i≠k y_ix_i + y_kx_k. If we fix all y_i for i≠k and require y⋅x = 0, this gives us an equation of the form a + y_kx_k = 0 (mod p), where a and x_k are constants and x_k in particular is nonzero. There is a unique solution y_k = (x_k)^-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 p^n-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 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.

2.1. Solution

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

$\begin{align*} \sum_{k=0}^{n} \binom{n}{k} 2^k, \end{align*}$

because we have (n choose k) ways to pick the k prize-winners and 2^k 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:

$\begin{align*} \sum_{k=0}^{n} \binom{n}{k} 2^k (-1)^k \end{align*}$

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

$\begin{align*} \sum_{k=0}^{n} \binom{n}{k} 2^k (-1)^k &= \sum_{k=0}^{n} \binom{n}{k} (-2)^k 1^{n-k} \\ &= (-2+1)^n \\ &= (-1)^n. \end{align*}$

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:

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

3.1. Solution

Rule (3) implies that each PIN is a 4-permutation, so there are 10⋅9⋅8⋅7 = 5040 PINs left after applying it. Any PIN excluded by rules (1), (2), or (4) is also a 4-permutation, so we can subtract them from these 5040 to obtain the final count. A complication is that while no PIN is excluded by both rules (1) and (2), there may be overlap with rule (4).

Let S be the set of all 4-permutations of digits. Let A1 be the set of increasing permutations forbidden by rule (1), A2 the set of decreasing permutations forbidden by rule (2), and A4 the set of scrambled consecutive permutations forbidden by rule (4).

We want to compute |S-(A1∪A2∪A4)| = |S| - |A1∪A2∪A4|. We already have |S| = 5040. To compute |A1∪A2∪A4|, expand it as |A1∪A2| + |A4| - |(A1∪A2)∩A4|. Since A1 and A2 are disjoint, we can compute |A1∪A2| = |A1|+|A2|. We can find an element of A1 (or A2) by choosing any 4-subset of the possible digits and ordering them in increasing or decreasing order. This gives |A1| = |A2| = (10 choose 4) = 10⋅9⋅8⋅7/4! = 5040/24 = 210. We can find an element of A4 by choosing the smallest digit (in the range 0..6) and then considering all 4! = 24 permutations; this gives |A4| = 7⋅24 = 168. To compute the size of (A1∪A2)∩A4, observe that for each of the 7 choices for 4 consecutive digits, exactly one ordering is increasing and exactly one is decreasing, giving a total of 7⋅2 = 14 elements in the intersection. So we have |A1∪A2∪A4| = 210 + 210 + 168 - 14 = 574. Subtracting this from 5040 gives 4466 permitted PINs.

(This can be confirmed by running this program.)