[FrontPage] [TitleIndex] [WordIndex

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?

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

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:

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

2014-06-17 11:57