Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers

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



Possible Solutions: Test #1


 

1.

A bus filled with a high school music group stopped at Blaise's Bistro. The director, a budding mathematician, noticed the menu board at the Bistro and quickly assured her assistant that at least one of the 8 sodas listed on the board would be ordered at least 4 times by the student musicians. Naturally, the director assumed that each student would order exactly one soda from the list.

What is the minimum number of students that must be in this music group?

Suppose that none of the 8 sodas is ordered four times or more. It is possible that all 8 varieties were ordered three times each, requiring 24 students. A 25th student, however, would force the fourth order of one of the sodas, by the Pigeonhole Principle. Therefore, the minimum number of students in the group is 25.

.

2.

North American radio stations must adhere to specific guidelines when selecting the call letters for the station name.

  • The name must contain either three or four letters of the alphabet.
  • The name must begin with a W or a K.

How many different radio station names are possible under these restrictions?

Consider two disjoint cases.

Case I: 3 letters in the name

In this case, there are 2 choices for the first letter and 26 choices for each of the second and third letters. Each choice is independent so by the multiplication principle, there are 2*26*26 possible 3-letter names.

Case II: 4 letters in the name

In this case, there are 2 choices for the first letter and 26 choices for each of the second, third, and fourth letters. Each choice is independent so by the multiplication principle, there are 2*26*26*26 possible 4-letter names.

Because the cases are disjoint, we add the results of the two cases to determine the total number of names that are possible.

2*26*26 +  2*26*26*26 = 1352 + 35,152 = 36,504

.

3.

Consider the letters in the word SIMULATE.

(a) How many rearrangements are there of these letters?
 

P(8,8) = 8!

(b) How many rearrangements exist if the three-letter sequence SIM must be kept together as it appears?
 

Consider the chunk SIM as one unit. We now have 6 units to permute. This is just P(6,6)=6!

(c) How many rearrangements exist if each must begin and end with a vowel?
 

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

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

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

This results in P(4,2)*P(6,6) ways to rearrange the letters with a vowel in the first place and a vowel in the last place.

(d) From the 8-letter set, how many 5-letter subsets exist?
 

This is just a combination of 5 from 8: C(8,5).

.

4.

Using the set {A,B,C}, what fraction of all 5-letter words that can be created contain exactly one A?

There are a total of 3*3*3*3*3 = 243 5-letter words that can be made.

To determine the number of words with exactly one A, we note that there are 5 places for the one A. That is, an A can and must be placed in one of the five positions in the word. There remain 4 places and for each there are two choices. This results in 5*2*2*2*2 or 80 possible 5-letter words that contain exactly one A.

This results in 80/243 as the fraction of all 5-letter words, from the set {A,B,C}, that contain exactly one A.

.

5.

Al and Bobbie are in a group of 12 students. Three teams of 4 students are to be created from the group of 12. Among all possible three-team sets, how many ways exist for Al and Bobbie to be on different teams?

There are 3*2 = 6 ways to place Al (A) and Bobbie (B) onto two different teams from the three teams being created. Although not necessary, you can think of the teams with names RED, BLUE, and GREEN, and count the possible ways A and B could be placed onto two different teams.

Now that each of A and B are in a designated team, choose from the remaining students to fill out the teams. From the 10 remaining students, choose 3 to fill out the team A is on. This can be done in C(10,3) ways. Now from the 7 remaining students, choose 3 to fill out the team B is on. This can be done in C(7,3) ways. Finally, place the remaining 4 students on the third team, the one that neither A nor B is on.

This results in 6*C(10,3)*C(7,3) ways to meet the conditions of the problem.

.

6.

Complete ONE of the two problems listed below.

I. Show an algebraic proof that C(a,c)*C(a-c,b-c) = C(a,b)*C(b,c) for a>=b>=c.

The strategy to use here is to represent each combination expression using factorial notation and through simplification, show that the left-side product is equivalent to the right-side product.

The final expressions in [1] and [2] above are equivalent, thereby showing that C(a,c)*C(a-c,b-c) = C(a,b)*C(b,c). This completes the required algebraic proof.

II. Determine the smallest natural number n that assures

We have shown in class that , so our goal is to determine the smallest natural number n so that . We first manipulate the inequality:

Using conventional methods for solving equations (complete the square or use the quadratic formula on [4], carry out a guess-and-test on [3], graph the expression on the LS of [4] and look for x-axis intercepts, use a CAS SOLVE routine, and so on), we determine that the required natural number n is 1414.

.

 

 

 

 

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