6.1
1-There are 18 mathematics majors and 325 computer science
majors at a college.
a) In how many ways can two representatives be picked so that one is a mathematics major and the other is a computer science major?
Answer: 18 * 325 = 5850.
b) In how many ways can one representative be picked who is either mathematics major and the other is a computer science major?
Answer: 18 + 325 = 343.
2. An office building contains 27 floors and has 37 offices on each floor. How many offices are in the building?
Answer: Using the product rule: there are 27 * 37= 999.
3. A multiple-choice test contains 10 questions. There are four possible answers for each question.
a) In how many ways can a student answer the questions on the test if the student answers every question?
Answer: 4.4...4 410 1,048,576 ways.
b) In how many ways can a student answer the questions on the test if the student can leave answers blank?
Answer: There are 5 ways to answer each question 0 give any if the 4 answers or give no answer at
all 510 9,765,625 ways.
4. A particular brand of shirt comes in 12 colors, has a male version and a female version, and comes in three sizes for each sex. How many different types of this shirt are made?
Answer: 12.2.3 72 different types of shirt.
5. Six different airlines fly from New York to Denver and seven fly from Denver to San Francisco. How many different pairs of airlines can you choose on which to book a trip from New York to San Francisco via Denver, when you pick an airline for the flight to Denver and an airline for the continuation flight to San Francisco?
Answer: 6.7=42.
6. There are four major auto routes from Boston to Detroit and six from Detroit to Los Angeles.How many major auto routes are there from Boston to Los Angeles via Detroit?
Answer: 6.4=24.
7. How many different three-letter initials can people have?
Answer: 26.26.26 =7,576 different initials.
8. How many different three-letter initials with none of the letters repeated can people have?
Answer: 26.25.24=15,600 ways
9. How many different three-letter initials are there that begin with an A?
Answer: 1.26.26=676 ways
10. How many bit strings are there of length eight?
Answer: 28 =256 bit strings
11.How many bit strings of length ten both begin and end with a 1?
Answer: 1.2.2.2.2.2.2.2.2.1= 28 = 256 bit strings
12. How many bit strings are there of length six or less, not counting the empty string?
Answer: 26 25 24 23 22 21
13. How many bit strings with length not exceeding n, where n is a positive integer, consist entirely of 1s, not counting the empty string?
Answer: n
16. How many strings are there of four lowercase letters that have the letter x in them?
Answer: Number of strings of length of 4 lowercase: 264
Number of strings of length of 4 lowercase other than x: 254
264 - 254 =66,351 strings.
6.2
1. Show that in any set of six classes, each meeting regu- larly once a week on a particular day of the week, there must be two that meet on the same day, assuming that no classes are held on weekends.
Answer: Because there are six classes, but only five weekdays, the pigeonhole principle shows thatat least two classes must be held on the same day.
2. Show that if there are 30 students in a class, then at least two have last names that begin with the same letter.
Answer: Since there are 26 letters (assuming we use the Latin alphabet), there are more students (orlast names) than letters, therefore by Dirichlet’s principle (think of students as objects and letters asboxes) there is at least one letter such that at least two last names start with that letter.
3. A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.
a) How many socks must he take out to be sure that he has at least two socks of the same color?
Answer: Three. With 3 pigeons (socks) and 2 pigeonholes (sock color) we know that at least one
sock color appears at least 3 2 ⎡⎢
⎤⎥2 times for a pair of matched socks.
b) How many socks must he take out to be sure that he has at least two black socks?
Answer: We assume that there was a worst case scenario where the man pulled out 12 brown socks. He would then have to pull out 2 more.
4. A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them.
a) How many balls must she select to be sure of having at least three balls of the same color?
Answer: We have p = 2 bins (pigeonholes) and r = 3: the minimum number of balls (pigeons) in any of the bins. By the generalized pigeonhole principle, the answer is N 2 ⎡⎢⎤⎥3 , i.e., N 5.
b) How many balls must she select to be sure of having at least three blue balls?
Answer: We assume that there was a worst case scenario where she pulled out 10 black balls. She would then have to pull out 3 more.
5. Show that among any group of five (not necessarily con- secutive) integers, there are two with the same remainder when divided by 4.
Answer: There are four possible remainders when a integer is divided by 4 (these are pigeonholes here): 0, 1, 2, or 3. Therefore, by the pigeonhole principle at least two of the five given remainders (these are pigeons) must the same.
6. Let d be a positive integer. Show that among any group of d 1 (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d .
Answer: N=50.99+1=4951.
13. a) Show that if five integers are selected from the first eight positive integers, there must be a pair of these integers with a sum equal to 9.
Answer: Let A 1,2,3,4,5,6,7,8. Partition the set A into 4 subsets: {1, 8}, {2, 7}, {3, 6}, and {4, 5}, each consisting of two integers whose sum is 9. If 5 integers are selected from A, then by the Pigeonhole Principle at least two must be from the same subset. But then the sum of these two integers is 9.
b) Is the conclusion in part (a) true if four integers are selected rather than five?
Answer: No. Take 1,2,3,4