Assignment 1

In addition to correct answers, please:

  • Show how you derived your answer.
  • Make all proofs, and longer-answer questions, beautifully organized and easy to read. This includes perfect spelling and grammar.

Please see Canvas for instructions on how and when to submit this assignment.

Question 1

On an upcoming expedition to Mars, there are 16 candidate astronauts, 7 humans and 9 androids (i.e. intelligent human-like robots), to choose from, and each can fill any role in a crew.

  1. Suppose a crew consists of five roles: captain, navigator, doctor, engineer, and technician. If every role must be filled by a different astronaut, how many ways can a crew be chosen from the 16 astronauts?
  2. How many different crews have
    1. an android as captain?
    2. exactly one android on the crew?
    3. at least one android on the crew?

Question 2

Suppose 135 people enter a marathon, where the top 5 finishers each win a trophy (the order of finishing matters).

  1. How many ways can the trophies be awarded?
  2. If Steve and Darlene are runners in the race, and they finish in the top 3, how many ways can the 5 trophies be awarded?

Question 3

Suppose you have an old-fashioned computer that represents each individual character as one of 127 different possible characters (e.g. 7-bit ASCII characters). These characters include letters (upper and lower case), digits, punctuation marks, the space character, and a few other characters.

  1. How many different sequences of 35 characters are possible? Repeat characters are allowed.
  2. How many different sequences of 35 characters are possible if all pairs of consecutive characters are different? Repeat characters are allowed (as long as they are not consecutive).

Question 4

  1. How many ways can the letters in ABSQUATULATE be arranged?
  2. How many ways can the letters in ABSQUATULATE be arranged if the 3 As are all together?

Question 5

Santa has 21 different toys in his sack. How many ways can he distribute them among 4 children such that:

  1. Each child gets exactly 3 toys.
  2. The oldest gets 5, the second oldest gets 4, the third oldest gets 3, and the youngest gets 2? Assume the children are each a different age.

Question 6

Prove that, if n is a positive integer, then this equation holds:

n\binom{2n}{n} = (n+1)\binom{2n}{n+1}

Question 7

Rubik’s cube is one of the most popular toys of all time. It’s a 3x3x3 cube that appears to be made of 3 \cdot 3 \cdot 3=27 smaller cubes, called cubies. Only the faces of 26 of the cubies are visible: the cubie in the center is not seen (and in fact doesn’t exist — the mechanism for turning the cube takes up all the space).

Each visible face of a cubie has a colored sticker on it, and there are 6 different colors of stickers. When the cube is “solved”, each face of the cube has stickers of all the same colors.

  1. How many stickers are there on a 3x3x3 Rubik’s cube?

  2. If you were to remove all the stickers of a 3x3x3 Rubik’s cube, how many different ways could you put them back on? Stickers of the same color are indistinguishable.

  3. The original Rubik’s cube was created in the 1970s, and since then people have created larger versions. For example, 4x4x4, 5x5x5, and 6x6x6 have been created. At the time this question was created, the largest NxNxN Rubik’s cube ever created was a 32x32x32 one.

    Derive a formula that counts the number of stickers on an NxNxN Rubik’s cube, for any integer n > 0.

  4. If you were to remove all the stickers of an NxNxN Rubik’s cube, for N > 0, how many different ways could you put them back on? Stickers of the same color are indistinguishable.

Question 8

How many different ways can 200 pennies be distributed among 10 people so that:

  1. everyone gets 0, or more, pennies?
  2. everyone gets 5, or more, pennies?

Question 9

There are 30 identical diamonds buried on an island. You have a treasure map of the island that tells you that the diamonds are distributed among 9 different locations.

  1. What’s the maximum number of different locations that could have 0 diamonds?
  2. How many different ways could the diamonds be distributed among the locations (assuming each location has 0 or more diamonds)?
  3. Suppose you dig in the first three locations, and discover 0, 4, and 2 diamonds. How many different ways can the remaining diamonds be distributed among the remaining locations?