Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers

Spring 2001
Dr. Roger Day (day@math.ilstu.edu)



Possible Solutions: Test #1


 

1.

Four boys and five girls, all of differing heights, stood in line for a palm reading. If all the boys stand next to each other in line, how many different linear arrangements exist for the nine people?

Solution: 4!*6!

The four boys, standing next to each other, can be arranged in P(4,4)=4! ways. Now treat them as one unit, because they cannot be separated. This gives us six units to permute for possible linear arrangements, carried out in P(6,6)=6! ways.

.

2.

A local fast-food outlet offered a variety of meal combinations. Every meal combination included a sandwich, an order of French fries, and a soft drink. Suppose there are 6 different sandwiches, 3 different sizes for French fries orders, and 8 different soft drinks to choose from.

(a) How many meal combo orders must be placed to assure that at least one meal combo is ordered twice? (4 points)

Solution: (6*3*8)+1=144+1=145

Use the multiplication principle to determine there are 6*3*8=144 different combo meals. The worst case scenario is that the first 144 orders are each for different combo meals. By the pigeonhole principle, the 145th order, therefore, must assure us that at least one combo meal is ordered twice.

The fast-food outlet also offers breakfast items. The breakfast sandwiches include five different bagel sandwiches, seven different biscuit sandwiches, and four different English muffin sandwiches.

(b) Suzzie Softknuckle comes to the fast-food outlet for a breakfast sandwich. How many different breakfast sandwiches does she have to choose from? (3 points)

Solution: 16 choices

The sandwich types are disjoint from one another, so use the addition principle to determine there are 5+7+4 different sandwiches.

The Merchanteer County All-Stars softball team stopped at the fast-food outlet. Each of the 21 team members purchased either a double cheeseburger or a hot ham-and-cheese sandwich. No team member ordered more than one sandwich.

(c) Freddie the Fry Cook kept track of the sandwich purchases in the exact order they were made. How many different orderings were possible if k team members purchased a hot ham-and-cheese sandwich? (3 points)

Solution: C(21,k)=C(21,21-k)

In the list of 21 sandwich orders, select k of them for hot ham-and-cheese. This can be done in C(21,k) ways.

.

3.

Five brothers each have the same set of seven hats, distinguished only by color. Each has a white hat, a black hat, an orange hat, a green hat, a yellow hat, a maroon hat, and a red hat.

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

Solution: 7^5

Each brother chooses one of seven hats. Each brother's choice is independent of the others, so by the multiplication principle, there are 7*7*7*7*7 different 5-hat sets.

(b) How many ways are there for each of the brothers to all choose hats of different colors? (3 points)

Solution: P(7,5)

The first brother has 7 colors to choose from, the next has 6, and so on, down to the last brother who has 3 colors to choose from.

(c) At a recent family reunion, four of the brothers were seen wearing the same color hat while the fifth brother wore a hat of a different color. In how many ways could this have occurred? (4 points)

Solution: P(7,2)*C(5,1)=7*6*5

Choose one of the five brothers to wear the different-colored hat. This can be done in C(5,1)=5 ways. The set of four brothers choose one of seven colors and the fifth chooses from the remaining six colors.

.

4.

4. Consider the letters in the word EXCESSIVENESS.

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

Solution: 13!/(4!1!1!4!1!1!1!)=13!/(4!4!)

We permute the 13 letters in the word, carried out in 13! ways. We then divide by the denominator shown here to account for the duplicate letters that occur in the word.

(b) How many arrangements exist if the three-letter sequence EXC must be kept together in the order shown? (2 points)

Solution: 11!/(1!4!4!1!1!1!)

Treat EXC as a unit, resulting in 11 objects to permute. We now carry out the same process as in (a) above.

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

Solution: [P(8,2)*P(11,11)]/(4!*4!)=(8*7*11!)/(4!*4!)

Within the 13 places for letters, place the first and last to assure they are consonants. There are 8 consonants to choose from for the first and 7 for the last. This is P(8,2)=8*7. Now place the remaining 11 letters. This can be done in P(11,11)=11! ways. Because each of the P(8,2) possible first-last consonant arrangements can be matched with the P(11,11) ways to place the remaining letters, we multiple the two results. Finally, we account for the duplication of letters, requiring us to divide out those equivalent groups. We divide by (4!*4!) as we did in (a) above. This results in [P(8,2)*P(11,11)]/(4!*4!)=(8*7*11!)/(4!*4!) ways to rearrange the letters with a consonant in the first place and a consonant in the last place.

(d) How many 3-letter sets can be created using only the unique letters in the word? (3 points)

Solution: C(7,3)

There are 7 unique letters in the word and we select 3 of them.

.

5.

At Bunion College, a small undergraduate institution in the midwest, every student must select a password to use to enter the college computer network. In creating a password, the following restrictions must all be met.

  • The password must contain only digits or letters of the alphabet.
  • The password must be four or five characters in length.
  • The password must begin with either a B or a C.

How many different passwords are possible under these restrictions?

Solution: 2*36^3 + 2*36^4

Consider two cases, one for the 4-character password and one for the 5-character password.

Case I: For a 4-character password, there are 2 choices for the first position (B or C) and 36 choices for each of the next three positions, resulting in 2*36^3 different 4-character passwords.

Case I: For a 5-character password, there are again 2 choices for the first position (B or C) and 36 choices for each of the next four positions, resulting in 2*36^4 different 5-character passwords.

Because the cases are disjoint&emdash;we cannot have a password that is both 4 and 5 characters long&emdash;we can add the results of the two cases.

.

6.

Francisco approached his combinatorics instructor and showed her the following claims:

(i) 5! + 5! = 10! (ii) 2! &endash; 1! = 1! (iii) 5! = 5*4!

(a) State whether each claim is true or false. Show arithmetic work to support your response. (3 points)

Solution

(i) 5! + 5! = 10! False: 5!=120, so 5!+5!=240 but 10!=3,628,800.

(ii) 2! - 1! = 1! True: 2!=2 and 1!=1, so 2-1=1 is true.

(iii) 5! = 5*4! True: 5!=5*4*3*2*1, but 4*3*2*1=4!, so 5!=5*4!.

(b) For any of the three claims that are true, write a generalization of Francisco's claim. (3 points)

(ii) 2! - 1! = 1!

Generalization: n!-(n-1)!=(n-1)! Or, alternatively, n!-1!=1!

(iii) 5! = 5*4!

Generalization: n!=n*(n-1)!

(c) For each generalization you wrote for (b), determine whether it is true or false. If it is false, provide a counterexample to show that; if it is true, justify that the result holds in general. (4 points)

(ii-a) n!-(n-1)!=(n-1)!

False: Counterexample: 6!-5! is not equal to 5!

(ii-b) n!-1!=1!

False: Counterexample: 10!-1! is not equal to 1!

(iii) n!=n*(n-1)!

True: By the definition of factorials this must always hold.

.


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