Problem 1.

The Drunken Professor has a class of 34 students. He wants to divide them into seventeen pairs of partners for a project. He does so uniformly at random, with every possible division as likely as every other.

a) How many different ways are there to divide up the students?
(Example to avoid confusion: If there were six students, then the answer would be 15: AB/CD/EF,
AB/CE/DF, AB/CF/DE, AC/BD/EF, AC/BE/DF, AC/BF/DE, AD/BC/EF, AD/BE/CF,
AD/BF/CE, AE/BC/DF, AE/BD/CF, AE/BF/CD, AF/BC/DE, AF/BD/CE, AF/BE/CD.)

b) Two of the students are Alice and Betsy. What is the probability that they will be partners?

c) Suppose that the Drunken Professor has two projects (one before the midterm and one after). He divides up the class into pairs for each project, independently. Let X be the number of people who have the same partner for both projects. Compute the expected value of X.

Problem 2.

I have two ordinary decks of cards (4 suits, 13 denominations, the usual); the two decks have different back designs, so I can easily tell which is which. I shuffle all the cards together and, without looking, take two cards uniformly at random and put them in my pocket. Let E be the event that my two cards came from the same deck, and let F be the event that my two cards are the same suit (whether they came from the same deck or not).

a) Compute P(E|F).
b) Compute P(F |E).
c) Are the events E, F independent? Why or why not?

Problem 3.

There is a row of n chairs, each containing a student. Let an be the number of ways to reassign seats so that each student either stays in place or moves only one chair to the left or right. For example, if n=3, and the people are ABC in that order, then the legal seat assignments are ABC (we do count the case where no one moves), ACB, and BCA. So a3=3.

a) Use a combinatorial argument to show that a_n = a_n-1 + a_n-2 for a ≥ 3. (Hint: what happens to a person on the end of the row?)
b) Prove that an is a Fibonacci number for every n.

Problem 4.

There are 1000 natural numbers a₁, a₂,...., a1000. Prove that of the numbers 3^a₁, 3^a₂,...., 3^{a₁₀₀₀}, there must be 56 of them which have the same remainder when divided by 19.
(Hint: this is not a misprint. If the best you can do is prove the statement with 56 replaced by 53, then you're missing something.)

Problem 5.

A group of twelve people want to sit around a round table with twelve seats. We don't care who is facing what direction, so if two seating arrangements differ only by a rotation of the whole table, we don't count them as different.

a) How many different ways can the group seat themselves?
b) Suppose that the group consists of six men and six women. How many different ways can the group seat themselves, if we insist that each man sit between two women and each woman sit between two men?
c) Suppose that the group consists of six men and six women. How many different ways can the group seat themselves, if we insist that each person sit between a man and a woman?

Problem 6.

Prove, for each positive integer n, the number n! can be written as a sum of n terms n!=a₁+a₂+a₃+.....+a_n, where 1=a₁2<n and all the numbers a₁, a₂,....., a_n are factors of n!. (Hint: induction, naturally.)

Problem 7.

Alice has a ten-day vacation from school, and she wants to spend some of it reading. Beside her favorite comfy chair is a selection of 30 books. She will read exactly one of these books each day, for a total of ten different books. She is planning out what she will read each day.

a) How many different ways can she decide which book to read on each day?
b) Suppose that three of the books form a trilogy, so Alice wants to either read all three of them, in that order (but not necessarily on consecutive days), or not read any of them. Now how many different ways can she decide which book to read on each day?
c) Suppose that ten of the books are fiction, ten are non-fiction, and ten are poetry, and Alice wants to read at least one book of each type. Now how many different ways can she decide which book to read on each day?

Problem 8.

In the (fictional) dice game Piracy, a player begins a turn by rolling a handful of 13 (fair, independent, six-sided, standard) dice.

a) The order of the dice doesn't matter for gameplay. All that matters is how many of each number is rolled. How many different rolls are possible?
b) What is the probability of rolling 2 ones, 1 two, 4 threes, 3 fours, 2 fives, and 1 six?
c) What is the probability that there will be at least three dice showing the same number?