Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers

Spring 2000
6:00 - 8:50 pm Tuesday STV 332
Dr. Roger Day (day@math.ilstu.edu)



Possible Solutions: Test #1


 

1.

Pizza Hut is offering customers opportunity to create for themselves a unique music CD when they log on to the Pizza Hut website and use an appropriate code number. The Pizza Hut ad claims customers can make a 6-song CD by selecting from 200 different song titles.

(a) How many different sets of 6 songs could be selected by a customer? (2 points)

We seek the number of 6-song subsets from a set of 200 songs, where order or arrangement is not important. The solution is the number of combinations of 6 items selected from 200, or C(200,6)=(200!)/(194!*6!)=82,408,626,300.


(b) How many unique 6-song arrangements could a customer create? (2 points)

We seek the number of 6-song arrangements from a set of 200 songs, where order is important. The solution is the number of permutations of 6 items selected from 200, or P(200,6)=(200!)/(194!)=59,334,210,936,000.


Suppose that the 200 songs are listed in the following categories: Pop (44), Rock & Roll (52), Rythem and Blues (18), Jazz (21), Classical (36), and Show Tunes (29), with each song listed in one and only one category. The numbers in parentheses above indicate how many songs are listed in each category.

(c) If a customer selects one song from each category, how many sets of 6 songs could be selected by the customer? (3 points)

We use the multiplication principle because we want one from each category to create a 6-song set. The wording of the problem ("sets of 6 songs could be selected") implies that order is not important. The solution is 44*52*18*21*36*29=902,918,016.


(d) Pat refuses to consider any Rock & Roll titles for her CD. How many 6-song CD arrangements does Pat have to choose from? (3 points)

We seek the number of 6-song arrangements from a set of only 148 songs (200 total songs less 52 R & R songs). The wording of the problem ("6-song CD arrangements") implies that order is important. The solution is the number of permutations of 6 items selected from 148, or P(148,6)=(148!)/(142!)=9,484,150,515,840.

.

2.

Three friends each have a red, a white, a yellow, a blue, and a green T-shirt.

(a) If each chooses a shirt to wear, how many unique 3-shirt sets could they be seen wearing? (5 points)

We use the multiplication principle because we want one shirt on each person in order to create a 3-shirt set. There are 5 ways for each person to choose a shirt, and the choice one person makes does not alter the choice of anyone else. The solution is 5*5*5=125 unique 3-shirt sets.


(b) If each chooses a shirt to wear, how many ways are there for each of them to all choose different colors? (5 points)

We again use the multiplication principle because we want one shirt on each person in order to create a 3-shirt set. This time, there are 5 ways for the first person to choose a shirt, 4 for the next, and 3 for the third person. The number of choice diminishes because the second and third persons cannot choose a color that has already been chosen. The solution is 5*4*3=60 unique 3-shirt sets with each shirt a different color.

.

3.

Consider the letters in the word QUADRILLIONTHS.

(a) How many unique arrangements are there for the letters in this word? (2points)

There are 14! ways to arrange the 14 letters in the word, but two of the letters appear twice each. We account for the duplication of these letters by dividing by 2!*2!. The solution is (14!)/(2!2!1!1!1!1!1!1!1!1!1!1!)=(14!)/(2!2!)=21,794,572,800.


(b) How many arrangements exist if the four-letter sequence QUAD must be kept together in the order it now appears? (2 points)

Consider the chunk QUAD as one unit. We now have 11 units to permute.

There are 11! ways to arrange the 11 units in the word, but two of the letters appear twice each. We account for the duplication of these letters by dividing by 2!*2!. The solution is (11!)/(2!2!1!1!1!1!1!1!1!1!1!1!)=(11!)/(2!2!)=9,979,200.


(c) Considering only unique letters (no repetition), how many 10-letter subsets could be created from these letters? (3 points)

There are 12 unique letters, so we seek the number of 10-letter subsets that can be created from a set of 12 elements. Order is not important. This is just a combination of 10 from 12, which is C(12,10)=(12!)/(2!*10!)=66.


(d) How many arrangements exist if each must begin and end with a vowel? (3 points)

Within the 14 places for letters, place the first and last to assure they are vowels. There are 5 vowels to choose from for the first and 4 for the last. This is P(5,2)=5*4.

Now place the remaining 12 letters. This can be done in P(12,12)=12! ways.

Because each of the P(5,2) possible first-last vowel arrangements can be matched with the P(12,12) ways to place the remaining letters, we multiple the two results.

Finally, we account for the duplication of two of the letters, requiring us to divide out those equivalent groups. We divide by (2!*2!) as we did in (a) and (b) above.

This results in [P(5,2)*P(12,12)]/(2!*2!)=(5*4*12!)/(2!*2!)=2,395,008,000 ways to rearrange the letters with a vowel in the first place and a vowel in the last place.

.

4.

At the Westminister Kennel Club dog show, held this month in Madison Square Garden in New York City and broadcast on the USA channel, every entrant must be assigned a unique registration number.

One suggested strategy for assigning registration numbers requires a code that has three parts to it.

  • The first digit ranges from 1 through 7, corresponding to one of the seven dog groups the entrant is classified in. These are the herding group, the sporting group, the working group, the toy group, the terrier group, the hound group, and the non-sporting group.
  • The next two digits correspond to the breed of the dog within the particular group. An English Cocker Spaniel, for instance, within the sporting group, is breed 14. No group has more than 27 breeds.
  • The final numbers in the registration code provide more information about the particular dog. The first of the final digits is a 0 or a 1, based on the sex of the dog. The second and third digits in this last set represent the age of the dog in years, starting with 00 if less than 9 months old and ranging up to 12, the oldest dog in this year's show being 12 years old. The last two digits in this final portion of the registration code represent the state of residence of the dog. Values 01 through 50 represent the 50 United States. If a dog is from outside the U.S., this number appears as 00.

(a) Without considering any other circumstances or restrictions, how many unique registration codes are possible under this scheme? (8 points)

Consider the registration number and the number of values that could occur in the various positions. We then use the multiplication principle to determine the total number of possibilities because we want values in all the positions.

This results in 7*27*2*13*51=250,614 possible registration codes.


(b) What problems in dog identification could occur under this strategy? (2 points)

One problem is that two unique dogs in the show may be assigned the same registration number. Two or more dogs may have exactly the same characteristics, as described by the different criteria in the suggested registration-number assignment scheme described above. There would be no way, by this scheme, to distinguish between the two dogs.

.

5.

In a certain leap year, the 13th of the month was a Friday three different times. What day of the week was 29 February that year? (10 points)

One way to approach this problem is to label the days of the leap years using positive integers from 1 through 366.

The table below shows the labels for the 13th day of each month for leap years. In parentheses after a 13th's label is the remainder when the label is divided by 7. Call this an index number for the 13th of each month.

Month
Leap-Year Labels and Index Numbers for 13th of Each Month
January
13 (6)
February
44 (2)
March
73 (3)
April
104 (6)
May
134 (1)
June
165 (4)
July
195 (6)
August
226 (2)
September
257 (5)
October
287 (0)
November
318 (3)
December
348 (5)

The only index number that occurs three times is 6. This means the index number 6 represents Fridays.

  • We determine which day of the week the 29th of February lands in one of several ways. One way is to move forward from the 13th of February. This has index number 2. That means the 20th of February has index number 2 as does the 27th of February. That means the 29th of February has index number 4. If index number 6 is Friday, index number 4 is two days earlier, or Wednesday.
  • Another way is to move back from the 13th of March. The 13th of March has index number 3, so the 6th of March and the 28th of February will have index number 3. The 29th of February will have index number 4, a Wednesday.
  • A third way is to use the leap-year label for the 29th of February. That label is 60 (31 days in January and 29 in February). We divide 60 by 7 and the remainder, 4, is the index number for the 29th of February. As we have already determined, index number 4 represents a Wednesday.

When a leap year has three Friday the 13ths, the 29th of February will occur on a Wednesday.

.

6.

Roberta claimed that the following equation was always true for positive integers n > 1.

(a) Is Roberta correct? (2 points)

Yes!


(b) If Roberta is correct, justify her result for the general case. If Roberta is not correct, provide an example to show she is not correct (called a counter example). (8 points)

To justify Roberta's claim in the general case, we need to show that the left side and right side of her equation are equivalent.

Here's one way to do that.

In the first line above, we have expanded n! into its factors. In the second line, we rewrite (n-2)(n-3)(n-4)...(2)(1) in its equivalent form, (n-2)!. In the third line, we expand n(n-1) to get n^2-n.

The third line is exactly the right side of Roberta's equation. Therefore, we have shown how to correctly and logically move from the left side of Roberta's equation to the right side of Roberta's equation. That shows us that the left side and right side are equivalent, which in turn justifies that the equation holds in general.

.


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes