Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers

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



Possible Solutions: Test #1


 

1.

Set N contains the following digits: {0,1,2,3,4,5,6,7,8,9}; set L contains the following letters: {A,B,C,D,E,F}; set S contains the following symbols: {<,>,=}

(a) A unique 2-character code is to be created by selecting one digit from set N and one letter from set L. If it matters not whether a digit or a letter is listed first, how many unique 2-character codes can be created? (3 points)

Solution: 2*10*6=120 codes

There are 10 digits to choose from followed by six letters. Double that to change the order so that a letter appears first.

(b) Mathilda drew on paper a line-up of six symbols from S. Her line-up included 2 of < and 4 of >. How many different 6-symbol line-ups containing 2 of < and 4 of > could she create? (3 points)

Solution:C(6,2)=C(6,4)=15 ways

This is analogous to the S/D problem, asking how many birth orders are possible in a family with 4 sons and 2 daughters. Mathilda created a 6-symbol string that included 2 of one type of symbol and 4 of another.

(c) Jackie was asked to create a subset of set N. She could choose no more than one of each digit, her subset was required to contain at least one digit, and her subset could contain no more than 9 digits. How many different subsets could Jackie create? (4 points)

Solution: 2^10 - 2 = 1022 possible subsets

There are 2^10 possible subsets of N, for we have two choices with each element of N: include it in a subset or not. The restrictions of the problem means we cannot create the empty set nor can we take the entire set N. Therefore, we must subtract two subsets from the 2^10 that are possible.

.

2.

2) The passenger door that is part of a keyless entry system on a new car has a 5&endash;pad keypad on the driver's door similar to the diagram shown here:

1/2
3/4
5/6
7/8
9/0

Every car is assigned a keyless entry code as it rolls off the assembly line. If each code is a three-digit number, such as 5-7-8, how many different keypad entries (unique sequences of keypad pushes) are possible? For instance, the code 5-7-8 has this keypad sequence:

5/6
7/8
7/8

Solution:5^3=125 unique keypad entries

Each code requires three keypad pushes. There are 5 keypads available for each push, so there are 5*5*5 different ways to make a three-step keypad entry.

.

3.

Five pairs of shoes were in a single line in Winnie's closet. Each pair was a solid color and there were five different colors: Black, White, Brown, Red, and Green. Each pair contained a left shoe and a right shoe, each distinguishable from one another.

(a) With no regard to matching pairs of shoes, how many ways exist for the shoes to be lined up in a single line? (3 points)

Solution: P(10,10)=10! ways

All the items are distinguishable from another, so this is the permutations of 10 things taken 10 at a time.

(b) Suppose that four single shoes are chosen from these five pairs. How many ways exist for these four single shoes to contain only shoes for the left foot? (3 points)

Solution: C(5,4)*C(5,0)=5*1=5 ways

There are 5 left-foot shoes and 5 right-foot shoes. We seek 4 of the five left-foot shoes and none of the five right-foot shoes. We are choosing not arranging, so we use combinations.

(c) Suppose that three single shoes are chosen from these five pairs. Of all the ways to select three single shoes, what portion of those will include a matched pair of shoes? (4 points)

Solution: 40/120 = 1/3 of all three-shoe sets will contain a matched pair

There are C(10,3)=120 ways to select 3 shoes from the 10. To get one pair among the three that are chosen, we have 5 pairs to choose from to get the pair, matched up with one of the 8 remaining shoes in the closet. This results in 5*8=40 3-shoe sets that contain a matched pair.

.

4.

Consider the letters in the word ACANTHOCHEILONEMIASIS.

Note: There are 21 letters in the word, including 3 A, 2 C, 2 E, 2 H, 3 I, 1 L, 1 M, 2 N, 2 O, 2 S, and 1 T.

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

Solution: 21!/(3!2!2!2!3!2!2!2!) arrangements

There are 21! ways to arrange the 21 letters, but there is duplication of letters. We divide by 3!2!2!2!3!2!2!2! to eliminate all duplicates.

b) How many arrangements exist if each arrangement must begin and end with a consonant? (2 points)

Solution: (11*10*19!)/(3!2!2!2!3!2!2!2!) arrangements

There are 11 consonants, so there are 11*10 ways to arrange the first and last letters as consonants. There are 19! ways to arrange the reamining 19 letters. We divide by the same denominator as in (a) to eliminate duplicates.

c) How many arrangements exist if all vowels must be kept together? (3 points)

Solution: (10!12!)/(3!2!2!2!3!2!2!2!) arrangements

Treat the 10 vowels as a chunk. There are 10! ways to arrange the vowels within that chunk. With the 11 consonants and the chunk of vowels, there are 12 things to place which can be done in 12! ways. We still divide by the same denominator as in (a) and in (b) to account for duplication.

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

Solution: C(11,5) sets

There are 11 unique letters in the word. We select 5 of them. Arrangenment is not an issue here, only selection, so we use a combination.

.

5.

Three people who frequented a local juice bar were such bitter enemies that they could not be trusted to sit on bar stools that were next to each other. The juice-bar proprietor required that there always be at least one bar stool (occupied or not) between any two of these bitter enemies.

(a) What is the minimum number of bar stools, all in a line, that is required to meet the proprietor's seating restrictions for the three enemies? (2 points)

Solution: 5 stools

Each of the three enemies needs a stool and there must be a stool between each pair: E1, S1, E2, S2, E3. Because the enemies can occupy the "outside" stools, we need two to place between them. Thus we need 5 stools in all.

(b) How many ways could the three enemies be seated, under these restrictions, if there were 8 bar stools in a line? (4 points)

Solution: P(6,3)=(6,3)*P(3,3)=6*5*4=120 ways

We know that 5 of the 8 stools will not be occupied by enemies, so we place these first. We assume the stools are not distinguishable from one another, so there is only one way to place these 5 stools. These five stools create 6 spaces among them:

___ S1 ___ S2 ___ S3 ___ S4 ___ S5 ___

We now arrange the three enemies among these 6 empty spaces, so there are P(6,3)=(6,3)*P(3,3)=6*5*4 ways to arrange the enemies.

(c) Generalize the solution to (b) for N enemies and B bar stools. State any restrictions on the quantities N and B. (4 points)

Solution: P(B-N+1,N) ways

We place the B-N stools that will not contain enemies. This creates B-N+1 empty spaces at which the enemies can sit. Any choice of N of these B-N+1 stools will meet the proprietor's requirements, so there are P(B-N+1,N) ways to seat the N enemies.

Regarding restrictions, we must have B-N+1>=N, so B>=2N-1. Try this with part (a).

.

6.

6) Oliveras approached her discrete-mathematics instructor and showed him the following claims:

(a) C(n,r)=P(n,r)/r!

(b) P(n,r)=n!/(r-1)!

State whether each claim is always true, sometimes true, or never true. Show appropriate evidence to support your response. In addition, if a claim is sometimes true, show a case for which the claim is true and a case for which the claim is false. If a claim is never true, include a case for which the claim is false.(5 points each)

(a) C(n,r)=P(n,r)/r!

Solution: always true

Compare the left-side expression to the right-side expression in this equation:

LS: C(n,r)=n!/(r!(n-r)!)

RS: P(n,r)/r!=(n!/(n-r)!*(1/r!)=n!/(r!(n-r)!)

We have shown that the right side can be made equivalent to the left side, so the equation will always be true.

(b) P(n,r)=n!/(r-1)!

Solution: sometimes true

Compare the left-side expression to the right-side expression in this equation:

LS: P(n,r)=n!/(n-r)!

RS: n!/(n-1)!

The RS will equal the LS only if (n-r)!=(r-1)!. These two products (factorials) will only be true if n-r=r-1, or if n=2r-1. This is the condition on n and r that muct hold for this result to be true. Otherwise, it will be false.

Example: True Case: Let n=5 and r=3. Note that 2r-1=n. P(5,3)=5*4*3, and 5!/2!=5*4*3. LS=RS=60

Example: False Case: Let n=3, r=3. Note that 2r-1<>n. P(3,3)=3!, but 3!/2!=3. The RS is not equal to the LS.

.


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