Description
Question 1: On Pigeons and Pigeonholes
Professor P. has an odd habit: He only buys red, green, and blue books, and he keeps
them in completely unordered stacks. However, he does keep track of the total number of
books he owns. One day he decides to get a bookshelf so that he can put all books of one
of the colors onto it. Unfortunately, when he is at the shelf store, he only knows that he
has a total of 271 books, but he does not know how many books of each color he owns.
What is the minimum number of books that the new shelf must be able to hold so that
Professor P. can be sure he can put all his books of one of the colors onto it? He does not
care which color it will be.
Question 2: Some Induction for You
Use mathematical induction to show that the equation 1 + 3 + 5 + … + (2n – 1) = n2
is
true for all positive integers.
Question 3: Rolling Five Dice
You got five dice for your birthday, and feel obligated to actually use them. So you are
playing around with them and starting to do some probability computations about the
outcomes of rolling all five dice at the same time.
a) What is the probability that none of the five dice show the number two?
b) What is the probability that all five dice show the same number?
c) Bonus: What is the probability that no two dice show the same number?
d) Bonus: What is the probability that two of the dice show the number six and the other
three show the number one?
Question 4: Recursion
Give a recursive definition of each of the following sequences (n = 1, 2, 3, …):
a) an = n + 3
b) an = 2n
c) an = (-1)n
d) an = 2n!
Question 5: Converting Back and Forth
Show every step of your computation for the following conversions:
a) Convert the decimal number 2885 into its hexadecimal expansion.
b) Convert the binary number (1101100)2 into its decimal expansion.
c) Convert the octal number (7435)8 into its hexadecimal expansion.
d) Convert the hexadecimal number (AF81)16 into its binary expansion.
Question 6: The Count and His Passwords
Count the following passwords and show how you did it. You do not have to compute the
explicit numbers but can leave expressions such as 266 + 56 as they are.
a) How many passwords of length 6 are there if all English lower- and uppercase letters
and digits are allowed?
b) How many passwords of at most length 6 are there if all English lower- and
uppercase letters and digits are allowed?
c) How many passwords of length 6 are there if all English lower- and uppercase letters
and digits are allowed and the password must contain at least one digit?
d) How many passwords of length 6 are there if all English lowercase letters and digits
are allowed but no letter or digit may occur more than once?
e) Bonus: How many passwords of length 6 are there if they have to consist of 4
English uppercase letters and 2 digits in any order?
f) Bonus: How many passwords of length 6 are there if they have to consist of 4
English uppercase letters and 2 digits, and the 2 digits cannot be next to each other?
