1.

Respond to each of these questions by placing your solution in the blank. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (e).

a. There are 6 ways to complete Task A and 10 ways to complete Task B. Assume that Task A and Task B are independent events that share no common elements. (i) How many unique ways exist to complete Task A or Task B? Solution: 6+10 = 16 (ii) How many unique ways exist to complete Task A and then Task B? Solution: 6*10 = 60

b. Single copies of the digits 0,1,2,3,4,5,6,7,8, and 9 are to be arranged in a single line. How many unique arrangements are there for these digits? Solution: P(10,10) = 10!

c. How many distinct arrangements exist for the letters in the word SENSELESSNESS? Solution: (13!) / (6!4!2!1!)

d. How many unique ways exist to arrange 10 pennies in a line such that 6 of them are heads up? Solution: C(10,6)

e. Given an unlimited supply of letters M, A, and D to choose from, how many unique 10-letter sets can be created that contain at least 3 Ds? Solution: C(9,2)

2.

Respond to each of these questions by placing your solution in the blank. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (e).

a. A recursive relationship has first term t(1) = -4 with t(n) = -2t(n-1)+ 3. Determine the value of t(4). Solution: t(4) = 41

b. Jan had to answer the following question: Julie's Eastside Eatery serves three different sandwiches: a cheese sandwich that sells for $2, a deli sandwich that sells for $4, and a deluxe veggie sandwich for $5. How many ways are there to spend $16 for sandwiches at Julie's? To answer the question, Jan created a generating function that, when expanded, included the following terms: What answer did Jan provide, based on the expansion shown here? Solution: 7 ways

c. State the explicit formula for the number of derangements of n distinct items. Solution: D(n) = n!*( 1/0! - 1/1! + 1/2! - 1/3! + . . . + (/1)^n/n! )

d. Study this completed difference table: x 1 2 3 4 5 6 7 f(x) 3 15 75 243 603 1263 2355 D1 ---> 12 60 168 360 660 1092 D2 ---> 48 108 192 300 432 D3 ---> 60 84 108 132 D4 ---> 24 24 24 D5---> 0 0 If we assume there exists a polynomial function that best represents the relationship between x and f(x), what is the degree of that polynomial? Solution: 4th degree

e. Replace a, b, and c in C(21,a) = C(b,9) + C(c,10) to correctly illustrate Pascal's Formula. Solution: a = 10, b = 20, c = 20

3.

Respond to each question below by placing your solution in the blank. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (e) on this page. (2 points each)

a. At Blaise's Bistro, the Friday night special is Pizza! For $6.95 plus tax, patrons choose one of 12 different pre-made pizzas and one of 8 different beverages. No additions or substitutions are allowed for this price. How many different $6.95 pizza/beverage options are there? Solution: 12*8 = 96

b. Eighteen (18) donuts are to be placed in a single line on a serving tray. Among the 18 donuts, there are 4 identical jelly donuts, 6 identical chocolate donuts, and 8 identical cream-filled donuts. How many unique arrangements exist for these 18 donuts? Solution: (18!) / (4!6!8!)

c. One version of the current automobile license plates issued in Minnesota shows three letters followed by a three-digit number. If no letter or digit may be repeated, how many unique license plates of this format can be created? Solution: P(26,3) * P(10,3)

d. A group of 15 people are to be separated into three rooms called the Blue Room, the Green Room, and the White Room. If there are no restrictions on how many people go in each room, and we are only concerned with the number of people in each room, how many ways can the separation occur? Solution: C(17,2)

e. Pauline works 10 blocks west and 12 blocks south of her apartment. All streets from her apartment to her workplace are laid out in a rectangular grid, and all of them are available for walking. On her walk to work, Pauline stops at an ATM that is located 3 blocks west and 5 blocks south of her apartment. On her way home from work, Pauline stops at People's Produce, located 7 blocks north and 3 blocks east of her workplace. If she walks 22 blocks from her apartment to work and 22 blocks from work to her apartment, how many different round-trip paths are possible for Pauline, given the stops she makes along the way? Solution: C(8,3) * C(14,7) * C(10,3) * C(12,5)

4.

Consider the expansion of (p + h + a + n + t + o + m)^666.

a. Determine the number of uncollected terms in the expansion. (2 points) Solution: 7^666

b. Determine the number of collected terms in the expansion. (2 points) Solution: C(666+7-1,7-1) = C(672,6)

c. Determine the coefficient C for the collected term C*p^111*h^222*n^333. (3 points) Solution:: (666!) / (111!222!333!)

d. How many unique collected terms in the expansion are of the form K*x^r*y^s*z^t, where x, y, and z are distinct elements from the set {p,h,a,n,t,o,m}? (3 points) Solution: C(7,3) * C(665,2) First, choose three distinct letters from {p,h,a,n,t,o,m}. This can be done in C(7,3) ways. Next, determine the number of ways for r+s+t = 666, where r, s, and t must all be positive integers (if 0, the factor would not appear within a collected term). This can be done in C(666-1,3-1) = C(665,2) ways.

5.

A public opinion poll of 1400 college students shows that

• 675 are females
• 682 range from 20 to 21 years old
• 684 are in extra-curricular activities
• 195 are females and are from 20 to 21 years old
• 467 are females in extra-curricular activities
• 318 are in extra-curricular activities and range in age from 20 to 21 years
• 165 are females in extra-curricular activities and range in age from 20 to 21 years

The Venn diagram here was created using the information above, starting with the last bullet and working up the list.

a. In this group of 1400 college students, how many were males who are not aged 20 or 21, and who are not in extra-curricular activities? (4 points) Solution: 174

b. In this group of 1400 college students, how many females not involved in extra-curricular activities range in age from 20 to 21 years? (3 points) Solution: 30

c. In this group of 1400 college students, how many males not involved in extra-curricular activities were questioned? (3 points) Solution: 334 + 174 = 508

6.

The set of letters {D,D,D,E,E,E,E,F,F} is to be used to create subsets with k elements in them.

a.State the range of values for k that is possible for this situation. (2 points) Solution: k is between 0 and 9, inclusive

b. How many subsets in all can be created? (2 points) Solution: 2^9

c. Create a generating function that can be used to determine the number of 6-element subsets that will have at least one E and at least two Ds. Show the factors of the generating function but do not expand the expression. Explain what each factor represents within the context of this problem. (3 points) Solution: (x^2 + x^3) * (x + x^2 + x^3 + x^4) * (1 + x + x^2) The first factor represents options for choosing Ds, as you must have 2 but can have no more than the 3 that are available. The second factor represents options for Es (from 1 to 4 of these) and the third factor options for Fs (none, 1, or at most 2 Fs).

d. Explain what you would do with this generating function in order to determine the number of 6-element subsets that will have at least one E and at least two Ds. (3 points) Solution: Expand the generating function, collect like terms, and read off the coefficient of the term with x^6 as a factor.

7.

Abby leads cryptography workshops at a local university and consults for the government when not teaching. She used a recent consulting case in one of her workshops. The government had intercepted a diplomatic pouch that contained a CD and hired Abby to analyze it when they discovered it contained code words.

The CD contained a long list of 4-character code words. Abby determined that:

(1) Each code word was created from a set of 36 characters that included letters of the alphabet (a,b,c,…,x,y,z) and the ten digits (0,1,2,3,4,5,6,7,8,9).

(2) A code word could contain either letters or digits or both letters and digits.

(3) In any one code word, no character appeared more than once.

(4) The CD list contained 1.5 million code words.

a. Generate an argument to justify that the list of code words must contain one or more duplicate code words, or provide evidence to the contrary. (5 points) Solution: Begin by determining how many different code words are possible, given the provided information. This is P(36,4) or 1,413,720 different words. But the list has 1,500,000 entries in it, so by the Pigeonhole Principle, there must be at least one code word duplicated.

b. Will your argument hold if item (3) above is changed to say that characters can be repeated within a code word? Explain. (5 points) Solution: No, it won't. Now there are 36^4 possible words, or 1,679,616. So the list of 1,500,000 words could be a list with no duplicate words.

8.

A company with the trade name MOBILES has a website display with the letters of its name, "MOBILES," splashed across the top of its welcome page.

MOBILES

A solid color is used for each letter in the name, but the colors may be repeated. On one particular day, for example, the colors of the letters might be blue, red, green, yellow, black, blue, and red, respectively. The company wishes to use a different color scheme for the MOBILES name on the website for each of the days in the 100 years that comprise the 21st century.

Determine the minimum number of different colors that are required for this task.

Solution: There are approximately 365 * 100 + 25 = 36,525 days in the 21st century, roughtly accounting for a leap year every four years. Therefore, we need at least 36,525 different color schemes. To solve this, we seek the smallest value k such that k*k*k*k*k*k*k is at least 36,525, because we will have k choices for each of the 7 letters in the word MOBILES. By guess and test, we see that k = 5 colors is the smallest value that satisfies this requirement.

9.

A theatrical producer intends to invest $250,000 in one Broadway production each year so long as the number of flops in which she has invested does not exceed the number of hits. Assuming that each year's production can be either a flop or a hit, and nothing else, determine the number of sequences of flops and hits that result in the producer continuing her investment strategy into the 7th year of productions.

Solution: By brute force or more sophiticated counting techniques, there are 20 different scenarios that would lead to the investment continuing into the 7th season.

10.

Two types of rectangles, each composed of an array of squares, are to be arranged in a line. Here are the shapes to be used:

The left rectangle measures 3-by-2 and the right rectangle measures 3-by-1. The arrangement to be created is to have 3 rows and n columns. One or more of the rectangles may be rotated 90º degrees when creating a line-up.

. . . . . . . . .

Here are a few examples. Note that the middle two figures show the same end result, a 3-by-2 arrangement, created two different ways. The first is created using a 3-by-2 rectangle and the second using two 3-by-1 rectangles. Also, note that the right-most figure, a 3-by-4 arrangement, has components that were rotated from their original perspective.

Your task is to explore this situation and create a recursive relationship A(n) to describe the number of unique 3-by-n arrangements that can be created.

Solution: A(n) = 3*A(n-3) + A(n-2) + A(n-1), with A(1) = 1, A(2) = 2, and A(3) = 6.

In the May 1996 issue of the Mathematics Teacher (p 368), R. S. Tiberio of Wellesley (MA) High School shared the following student discovery:

Your task: Justify that this relationship will hold in general, or, alternatively, show that the result cannot be generalized to all of Pascal's triangle.

Solution: By brute-force symbolic manipulation we can show that C(n,k-2) + C(n,k-1) + C(n,k) - [ C(n-3,k-3) + C(n-2,k-3) + C(n-1,k-3) ] - [ C(n-3,k-2) + C(n-2,k-1) + C(n-1,k-1) ] = C(n-2,k-2) + C(n-1,k-2) + C(n-1,k-1). This is left as an exercise for you! A less-symbolically intense method is to replace "positions" within the relationship with variables and relate them using Pascal's Formula and other known relationships.