Foundations of Computer Science: Honors
Homework 4
Problem 1: I have twelve books.
• In how many ways can I line them up on a single shelf?
• In how many ways can I choose seven of them and line them up on a single shelf?
• In how many ways can I choose seven to take to school?
Problem 2: An ogre has n captives to eat, one captive per day. • How many ways are there to make a menu for n days?
• How many ways are there to pick k captives to freeze them for winter season?
• How many ways are there to buy n bottles of sauce for the captives, out of k kinds?
Problem 3: • An ice-cream vendor sells eleven kinds of ice-cream. In how many different ways can I buy six cones, some or even all of which could be the same?
• An ice-cream vendor sells six kinds of ice-cream. In how many different ways can I buy eleven cones, some or even all of which could be the same?
Problem 4: • There are 33 children, and they want to divide into three teams of eleven. In how many different ways can this be done?
• How many unique permutations exist for the letters in the 1980’s band ”BANANARAMA”?
Problem 5: Which number is bigger: the number of six-digit integers representable as a product of two three-digit integers, or the number of six-digit integers not representable in this form?
Problem 6: Among the number 1, 2, ..., 1010, are there more of those containing the digit 9 in their decimal notation or those with no 9?
Problem 7: Professors and Keys A group of five professors are setting a mathematics competition. When they go home at night, they leave their work in a room which has a certain number of locks on the door. Each professor has keys to some, but not all of the locks. In fact, any three professors will have enough keys between them to open the door, but any two professors will not have enough. What is the smallest number of locks needed, and how many keys will each professor have? Provide a proof or a clear explanation to get credit for this problem.
