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]