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: Semester Exam

1.

a. Show how to simplify the following expression to generate a positive integer: C(5,2).

b. Determine the number of ways to arrange 10 distinct dogs in a straight line.

There are 10! arrangements.

c. There are 8 coffee choices and 12 tea choices on the menu at Farms and Babble Bookstore. These are the only beverage choices.

(i) If a customer orders either tea or coffee, how many selections does the customer have to choose from?

In this case, using the Addition Principle, there are 8 + 12 = 20 selections.

(ii) If a customer orders one tea choice and one coffee choice, how many choices are possible? Disregard whether tea or coffee is ordered or served first.

Using the Multiplication Principle, there are 8 x 12 = 96 choices.

d. Determine the number of non-negative integer solutions to the equation

A + B + C + D + E + F = 40.

C(40+6-1,6-1) = C(45,5).

e. Consider Pascal's Triangle, where 1 is the 0th row, 1 1 is the 1st row, and 1 2 1 is the 2nd row.

(i) Show the elements in row 6 of Pascal's Triangle.
Row 6:
1 6 15 20 15 6 1

(ii) State the sum of the elements that appear in row 20 of Pascal's Triangle.

The sum is 2^20.

2.

a. Determine the number of collected terms in the expansion of .

There are w+1 collected terms.

b. Determine the value of the coefficient K in the collected term resulting from the expansion of .

K = 9!/(2!7!)

c. Determine the number of uncollected terms in the expansion of .

There are 4^15 uncollected terms.

d. Determine the number of collected terms in the expansion of .

There are C(22+5-1,5-1) = C(26,4) collected terms.

3.

The following conjecture is to be proven true by induction or shown to be false using a counterexample:

a. State and carry out the first step in the induction process.

Step 1: Show that the conjecture is true when n=1.

When n=1, the LS is (2-1)(2x1)=2. When n=1, the RS is (1x3x2)/3=2. When n=1, LS=RS.

b. State and carry out the second step in the induction process.

Step 2: Assume that the conjecture holds when n=k.

When n=k, the conjecture is

c. State but do not carry out the third step in the induction process.

Step 3: Use the assumption in Step 2 to show that the conjecture holds when n=k+1.

4.

A passenger jet may fly three routes from New York to Chicago and four routes from Chicago to Los Angeles. For a round trip from New York to Los Angeles and back, determine the number of ways a passenger can travel without repeating the same route on any leg of the round trip.

Starting in NY, there are 3 ways to get to Chicago and 4 ways to get from Chicago to LA. Therefore there are 3x4=12 different ways to get from NY to LA via Chicago. On the return trip, the passenger has only 3 ways to go from LA to Chicago because a previously used route cannot be repeated. Likewise there are 2 ways to go from Chicago back to NY. Therefore, the return trip has 2x3=6 ways to return to NY from LA via Chicago.

By the multiplication principle, there are 12x6=72 different round trips in all that reuse none of the legs of the journey.

5.

Five unique dice are thrown simultaneously. Determine the portion of all possible throws that result in at least two 5s appearing.

First determine the number of different throws that are possible with no restrictions: There are 6 ways for each die to land, so there are 6x6x6x6x6=6^5 unique throws.

Now determine how many throws show at least two 5s. do this by subtracting from 6^5 the number of ways to get exactly one 5 and exactly no 5s.

To get no 5s, there are 5x5x5x5x5=5^5 ways for the dice to land, because each die can result in one of five outcomes (everything but 5). To get exactly one 5, there are 5 ways to choose which die will be the 5, and then once that choice is made, the remaining four dice each have 5 outcomes possible. Therefore, there are 5(5x5x5x5)=5^5 ways for exactly one 5 to appear.

Therefore, there are 5^5 + 5^5 ways to get exactly zero or one 5 to appear, so there are 6^5-(2x5^5) ways for at least two 5s to appear.

Of all possible throws, the portion that show at least two 5s when five unique dice are thrown is

[6^5-(2x5^5)] / 6^5.

6.

A nurse walks from home at 10th and H to her clinic at 16th and M, always walking to higher numbers or to letters further along in the alphabet. On a certain day, police block off 13th street between K and L streets. What portion of all possible paths from the nurse's home to the clinic contain the blocked-off street?

First determine the total number of ways to walk from 10th and H to 16th and M with no restrictions. Assume that the numbered streets run east and west and the lettered streets run north and south. Also assume that the numbered streets get higher as you move south and the lettered streets get further into the alphabet as you move east. The nurse must walk 6 blocks south and 5 blocks east. There are C(11,6) ways to do this.

Now determine how many of these paths include the blocked-off street. To get to K and 13th, you must walk 3 blocks east and 3 blocks south. Therefore, there are C(6,3) paths from 10th and H to 13th and K. There is 1 way to get from 13th and K to 13th and L. From 13th and L, there are 3 southerly blocks and 1 easterly block to walk to get to 16th and M. There are C(4,3) walks to walk this stretch. All in all, there are C(6,3)x1xC(4,3) paths from 10th and H to 16th and M that include the restricted street.

We remove these from the total number of paths, yielding C(11,6) - [C(6,3)x1xC(4,3)] total paths that do not include the blocked-off street.

7.

A company named GAMES has an advertising display with the letters of its name, "GAMES." Colors are used for each letter, but the colors may be repeated. On one particular day, for example, the colors might be red, green, green, blue, red. The company wishes to use a different color scheme for each of the 365 days in the year 2001. Determine the minimum number of colors that are required for this task.

One way to approach this problem is to think of the choices available to fill each of 5 available spaces. Here those 5 spaces are the letters, and the things we fill them with are colors.

If there is 1 color available, we have 1 way to fill the first space, 1 way to fill the second, and so on. Repetition is allowed. Using the multiplication principle, there is 1x1x1x1x1 way to color the letters in the sign.

If there are 2 colors available, we have 2 ways to fill the first space, 2 ways to fill the second, and so on. Repetition is allowed. Using the multiplication principle, there are 2x2x2x2x2=2^5 ways to color the letters in the sign.

In general, there are n^5 different coloring schemes, where n is the number of available colors.

We seek n such that n^5 >= 365. We have 1^5=1, 2^5=32, 3^5=243, and 4^5=1024.

The minimum number of colors is 4.

8.

In 7,843 families, all of which have a TV set, a dishwasher, a microwave, and a car, there are six different types of TV sets, five different types of dishwashers, four different types of microwaves, and eight different types of cars. What is the least number of families that have the same type of TV, dishwasher, microwave, and car?

By the multiplication principle, there are 6x5x4x8=960 different combinations of the 4 objects when we consider the different number of types of each object.

By the pigeonhole principle, we may have the first 960 families surveyed each identify a different combination of the 4 objects, but by the 961st family, we will repeat one of the 960 combinations.

Dividing 7843 by 960, we get a quotient between 8 and 9. Thus we could have 8 full sets of the 960 pigeonholes, and some with at least 9 responses. Thus, there are at least 9 families that share the same type of objects.

9.

Cannon balls are stacked in a compact equilateral triangular pattern. When there are n layers in the stack, there are n balls per side of the triangle on the lowest layer, n-1 per side on the next layer, and so on, up to 1 ball on the top. Determine a recursion relationship B(n), including any initial conditions, for the total number of balls in a pile with n layers.

Here is a two-dimensional visual image of several layers, moving down from the top.

Notes:

  • Each layer represents atriangular number: 1,3,6,10, and so on.
  • These numbers each represent the sum of a specific number of positive integers: 1=1, 3=1+2, 6=1+2+3, 10=1+2+3+4.
  • Recall that the sum of the first n positive integers is [n(n+1)]/2.

Now consider some initial examples of the cannon-ball stacks.

  • A stack with one layer has 1 cannon ball, so B(1)=1.
  • A stack with two layers has layers (a) and (b) shown above, so it has 4 cannon balls. Another way to think of this is that it has the number B(1) plus the new layer, here figure (b). So B(2)=B(1)+3.
  • A stack with three layers has layers (a) through (c) shown above, so it has 10 cannon balls. Another way to think of this is that it has the number B(2) plus the new layer, here figure (c). So B(3)=B(2)+6.
  • A stack with four layers has layers (a) through (d) shown above, so it has 20 cannon balls. Another way to think of this is that it has the number B(3) plus the new layer, here figure (d). So B(4)=B(3)+10.

So what do these examples illustrate in general? Each new pile of cannon balls has the same number as the previous pile plus the number in the lew layer. That new layer will always have a number of cannon balls equal to the sum of the positive integers up to that layer number. That is, for a stack with n layers, the number of balls will be B(n-1) plus the sum of the first n positive integers.

In compact notation, we have B(n)=B(n-1)+[n(n+1)]/2, with initial condition B(1)=1.

10.

Exactly 10 chocolate chips are to be distributed at random into 6 chocolate-chip cookies. What is the probability that some cookie has at least 3 chips in it?

We need two values to compare as a ratio to determine the desired probability: The total number of ways to distribute 10 chocolate chips into 6 cookies and the number of those ways that result in at least three chips in one cookie.

To determine the total number of ways to distribute the chips, we determine the number of non-negative solutions to the equation

A+B+C+D+E+F=10,

where each letter represents a cookie. The number of solutions is C(10+6-1,6-1)=C(15,5).

To determine the number of those ways that result in at least three chips in one cookie, we solve the complementary problem and subtract that result from the total number of ways.

The complementary problem is to determine the number of ways that the chips can be distributed so less than three chips are in any cookie. Considering the equation above, we want A,B,C,D,E, and F to be values less than 3.

One case in this solution is for a cookie to have no chips in it. If that is the case, the other five cookies will each have two chips. There are 6 cookies to choose from in determining which will have no chips, so there are 6 ways to distribute the chips so one cookie gets no chips.

We can also distribute the chips so two cookies get one chip each and the rest get two each. This can be done in C(6,2) ways, for we need to determine the number of ways to select two of the six cookies into which we place one chip each.

There are no other ways to restrict the chips to less than three chips, for there is no way to have two or more cookies with no chips (without some of the others having at least three chips), and if more than two cookies each have one chip, we are assured of at least one cookie getting three or more chips.

So there are 6+C(6,2)=6+15=21 ways to restrict chip distribution to two chips or less. That means there must be C(15,5)-21 ways to have three or more chips in a cookie.

This means the desired probability is [C(15,5)-21]/C(15,5)=2982/3003 or approximately a 99.3% probability that a cookie will get three or more chips.

BONUS!

A survey was conducted of 983 families to determine whether they possessed (1) a cell phone, (2) a microwave, (3) a satellite dish, or (4) a CD player. No family was completely without such items, and 481 families had at least two of these items. At least three items were possessed by 345 families and 264 families possessed all 4 items.

a. Determine the total number of pieces of equipment held by all 983 families.

b. Determine the number of families that held the number of pieces of equipment specified below. Assume that none of these families had more than one of any particular item.

(i) exactly one piece of equipment

(ii) exactly two different pieces of equipment

(iii) exactly three different pieces of equipment

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