Math 425-4, Fall 1997

Prof. Hochster

** EC#6 revisited** I will restate the problem, since several
people did not interpret it correctly. Given a set with n
distinguishable elements, how many ways are there to choose
three subsets, A, B, C, such that A and B are disjoint
and B and C are disjoint? For example if n= 8 and the
given set is {1, 2, 3, 4, 5, 6, 7, 8}, then one possible
choice would be A = {1,3,5,6}, B = {2,4}, C ={1,3,7}
and this counts as a different choice from A = {1,3,7},B = {2,4},
A = {1,3,5,6}. The answer is a simple formula involving n,
and your solution should contain a complete justification. Your
count should include choices where one or more of the subsets is
empty. [10/6]

** EC#13** In a perfect shuffle of a deck of cards, the cards
in the upper half of the deck, i.e., in positions 1 through 26, move
to the odd numbered positions 1 through 51 in order
(the i th card moves to the 2i-1 th position) while the cards in the
lower half of the deck, i.e.,
in positions 27 through 52, move to the even numbered positions
2 through 52 in order (i.e.,
the card in position 26+i moves to the 2i th spot for i from 1 to 26).
Suppose that you do 8 consecutive perfect shuffles of a deck of cards.
What is the expected number of cards that are in their
original position? Explain your answer. (Note: since the shuffle
has been described exactly, the number of cards in their original
positions may not be represented very well by the assumption that
the order of the cards after eight shuffles is random.)
[10/6]

** EC#14** In this problem we use C(n,k) denote the number of
k element subsets of an n element set, for typographical reasons.

Let k be a positive integer less than or equal
to the positive integer n. Suppose that a k element set is selected
from the subsets of
{1,2,...,n} (so that all k element subsets are equally
likely choices). Compute the probability that the number 1 is in the subset
chosen
by two different methods, and, by comparing the results, prove the formula
C(n,k) = (n/k)C(n-1,k-1) ** without doing any computations**.
In particular, your argument should not make use of any of the
standard formulas for binomial coefficients. Now make repeated use
of this fact to show that
C(n,k) = (n/k)(n-1/k-1) ... (n-k+1/1), the usual formula. [10/8]

** EC#15** This problem assumes familiarity with problem number
56. on p. 61 of the text. Can you construct four spinners so that each is
better
than at least one of the others and worse than at least one of the
others? (They should all contain the same odd number of regions, call
it n, of the
same size, and the regions should be numbered with positive
whole numbers, each of which occurs only once. The assumption is that
when two of the wheels are spun, there are n^2 equally likely outcomes,
and, in each case, the higher number wins.)
Can you do this in such a way that each spinner is better than two
of the others and worse than just one of the others? [10/10]