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@ilstu.edu)

 Test #3: Possible Solutions

Evaluation Criteria

You may earn up to 10 points on each of questions 1 through 6. For each question:

• 6 points count toward a correct solution to the problem. I will evaluate the mathematics you use:
• Is it accurate and appropriate?
• Have you provided adequate justification?
• 4 points count toward how you express your solution. I will evaluate how you communicate your results:
• Is your solution clear and complete?
• Have you expressed logical connections among components of your solution?

1.

Respond to each of these questions. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (d) of problem 1.

a) Determine the number of derangements of the elements in the set {1,2,3,4,5,6}, where the natural position for 1 is the first position, the natural position for 2 is the second position, and so on.

 There are at least two efficient strategies for solving this problem. You can use the explicit formula for determining the number of derangements of n objects. That is Here D(6) = 265. You can also refer to the recursive relationship D(n)=n[D(n-1) + D(n-2)], where D(1)=0 and D(2)=1. Again, D(6) = 265.

b) Answer the following questions for the recurrance relationship described by:

a(n)=5a(n-1) - 2a(n-3) for n a positive integer,
where a(1) = -5, a(2) = -6, and a(3) = -1.

(i) Determine a(6).

(ii) Determine the smallest value of n such that a(n+1) &endash; a(n) is greater than 5000.

 (i) a(6) = 5a(5) - 2a(3), but we do not know a(5); a(5) = 5a(4) - 2a(2), but we do not know a(4); a(4) = 5a(3) - 2a(1) = 5(-1) - 2(-5) = 5. Using this, a(5) = 5(5) - 2(-6) = 37. This results in a(6) = 5(37) - 2(-1) = 187. (ii) Further calculations show that a(7)=925, a(8)=4551, a(9)=22381, and a(10)=110055. comparing the differences of pairs of values, we see that a(9) and a(8) provide the first pair with a difference greater than 5000. The desired value of n is 8.

c) In the expansion of , state:

i) the number of uncollected terms
ii) the coefficient K in the collected term .

 (i) The number of uncollected terms is 4^10. (ii) The desired coefficient is 10!/(3!1!2!4!).

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

 The number of collected terms is n+1 = C(n+1,n) = C(n+1,1).

2.

Georgania Higgenbottom served a variety of cool drinks at her spring garden party. Each of the 120 guests selected exactly one beverage, chosen from the following list: ginsing go-getter, spinach surprise, cabbage combo, tomato torment, and cucumber delight.

Georgania's head waiter, Christof, kept a tally sheet of drink selections for the 120 guests.

a) Suppose Christof noticed that each of the beverages had been selected by at least one guest. How many different tally sheets could Christof have generated for the party's drink selection under these circumstances?

 We need to determine the number of solutions, over the positive integers, for the equation GG+SS+CC+TT+CD=120, where each variable represents the number of guests who selected a particular beverage. The desired solution is C(120-1,5-1) = C(119,4).

b) Suppose instead that when Georgania screamed to Christof, "What are our minimums on drinks?" he replied, "I see that at least 10 people chose the ginsing go-getter, 20 or more went for the spinach surprise, more than 6 people tried the cabbage combo, no one selected tomato torment, and at least 15 drank cucumber delight." Under these conditions, how many different tally sheets could Christof have generated for the party's drink selection?

 We begin with the same equation, GG+SS+CC+TT+CD=120, but modify it to account for the known information. We know GG is greater than or equal to 10, SS is greater than or equal to 20, CC is greater than or equal to 7, TT is 0, and CD is greater than or equal to 15. If we adjust the equation to include these conditions, writing new variables for the remaining numbers of guests who could delect beverages, we have GG' + SS' + CC' + CD' = (120-10-20-7-15) or GG' + SS' + CC' + CD' = 68. We seek the number of non-negative integer solutions to GG' + SS' + CC' + CD' = 68. This is C(68+4-1,4-1)=C(71,3). The desired solution is C(71,3).

c) Try to picture Amiele, the beverage host, walking around the table asking guests for their beverage choice. How many guests would Amiele have to ask before he would be assured that a beverage choice repeated itself? What assumptions underlie your response?

 We apply the pigeonhole principle here, considering the worst-case scenario. It could be that the first 5 guests Amiele encountered each chose a different beverage. The sixth guest, however, would be assured of repeating a beverage choice, by the pigeonhole principle. The assumption is that each guest selects one and only one beverage from the list of five beverages discussed in the problem situation.

3.

In the Ancient yet little-known game of gnikoj, scoring occurs several ways. A player can earn 1 point for a kaboom, 1 point for a laboom, and 1 point for a maboom. A player earns 2 points for executing a bifter or for executing a cifter. In traditional gnikoj, there is no way to earn 3 points on a single move, and the only way to earn 4 points is by the rarely seen move called a gemserp. Points are added and the player with the highest point total wins.

a) Show at least three different scoring sequences a gnikoj player could execute and earn 11 points. Note that the order in which points are earned is significant. A kaboom followed by a cifter is a different scoring sequence than a cifter followed by a kaboom.

 Three possible routes to 11 points: gemserp + gemserp + maboom + bifter (4+4+1+2 = 11) gemserp + gemserp + bifter + maboom (4+4+2+1 = 11) maboom + gemserp + gemserp + bifter (1+4+4+2 = 11) Note from the next solution that there are 1,055,505 different ways to score 11 points in gnikoj.

b) In gnikoj, play continues until an essapmi is reached. Individual player totals could exceed 100 points. Create a recursion relationship T(n), including any required initial conditions, to describe the number of different sequences of gnikoj moves that result in a total of n points. Show justification for your result.

 We know T(1)=3 [three different 1-point scoring methods], T(2)=11 [9 pairs of 1-point/1-point scoring methods plus two 2-point scoring methods], T(3)=39 [6 different 1-point/2-point scoring methods plus 33 2-point/1point scoring methods], and T(4)=140 [117 different ways to get from 3 points to 4 points, 22 different ways to get from 2 points to 4 points, no ways to get from 1 point to 4 points, and 1 way to get from 0 points to 4 points]. If we consider how we can get to n points, we can get there from already having n-1 points, from already having n-2 points, and from already having n-4 points. For each way we can get to n-1 points (there are T(n-1) ways), there are 3 ways to add a point and get to n points. For each way we can get to n-2 points (there are T(n-2) ways), there are two ways to add 2 points and get to n points. For each way we can get to n-4 points (there are T(n-4) ways), there is one way to add 4 points and get to n points. Summarizing information in the preceeding paragraph, T(n)=3*T(n-1) + 2*T(n-2) + T(n-4). This is the desired recursive relationship, given the initial conditions of T(1)=3, T(2)=11, T(3)=39, and T(4)=140.

4.

What is wrong with the following problem situation?

A survey of 144 new teachers in a metropolitan school district determined that 16 new teachers had been to Europe, 13 had been to Asia, and 17 had been to Africa. Of those who had been to Europe, 10 had been to Africa. Of those who had been to Asia, 9 had been to Africa. Of all the new teachers surveyed, 5 had been to Africa, Asia, and Europe, and 111 new teachers had been to none of those continents.

Describe specifically and clearly what is wrong and how you determined that.

 This is a counting situation that involves three categories of inclusion/exclusion. Visually, we can represent the situation with a Venn diagram, like the one shown here. The letters A through G shown above represent the various travel categorizations into which we could place each of the 144 new teachers. Using the notation developed in class, we can represent the number of people in each category by using vertical brackets around each category symbol. From the given information, we know that: (1) |E|+|B|+|C|+|G|=16 (2) |A|+|B|+|C|+|D|=13 (3) |C|+|D|+|F|+|G|=17 (4) |C|+|G|=10 (5) |C|+|D|=9 (6) |C|=5 (7) |H|=111. Using equations (3),(4), (5), and (6) shown above, we can conclude that (8) |G|=5 (9) |D|=4 (10) |F|=3 [using (8) and (9) just derived]. Using equations (1), (2), (6), (8), and (9), we know that (11) |E|+|B|=10 (12) |A|+|B|=4. Using equations (6) through (10), and the fact that 144 new teachers took the survey, we know that (13) |A|+|B|+|E|=16. From (11) and (12), by addition, we see that (14) |A|+2*|B|+|E|=14. Here's where the contradiction can be shown. If we subtract (13) from (14), we get (15) |B|=-2. But equation (15) is impossible, for we cannot have a negative number of people responding to a survey question.

5.

a) Using an unlimited supply of letters from the set {A,B,C,D}, how many 7-letter sets are possible to create with at least one C in the set?

 Here we are not concerned with the arrangement of the letters within the set, merely the collection of letters to form a 7-letter set. For example, the set {A,A,A,A,A,A,C} is the same as {C,A,A,A,A,A,A}. An efficient way to determine a solution for this question is to count all possible 7-letter sets that can be created and subtract from that the number of 7-letter sets that have no Cs. The remaining sets will all have at least one C. To determine the total possible number of 7-letter sets, we consider non-negative integer solutions to the equation a+b+c+d=7, where each variable represents the number of times that letter appears in the set. The number of such sets is C(7+4-1,4-1)=C(10,3). To determine the total possible number of 7-letter sets that have no Cs, we consider non-negative integer solutions to the equation a+b+d=7, where each variable represents the number of times that letter appears in the set. The number of such sets is C(7+3-1,3-1)=C(9,2). Using the two results, we can conclude that the number of 7-letter sets with at least one C is C(10,3)-C(9,2) = C(9,3).

b) Using an unlimited supply of letters from the set {A,B,C}, how many 5&endash;letter words (meaningless or not) are possible to create with exactly one A in the word?

 Now we must consider each arrangement of 5 letters, not merely the collection of them. There are 5 places to position exactly one A in our word. We must fill the remaining 4 positions with Bs and Cs. If we select from 0 to 4 of those remaining 4 positions and place the letter B in those selected positions, we have only one way to place Cs for each such selection. For example, suppose A is in the left-most position in the word. We have 4 positions to fill. Suppose we put Bs in positions 2,3, and 4. By selecting those positions for B, we force letter C to occupy position 5. This means that placing the Bs forces the C placement as well. There are 5 places to fix the letter A and there are C(4,i) ways to place the letter B in from 0<= i <= 4 remaining positions. For each of these, there is just one way to position C in any remaining positions. By the multiplication principle, our solution is 5*[C(4,0)+C(4,1)+C(4,2)+C(4,3)+C(4,4)].

6.

In a local chess competition, two players compete until one player wins 4 matches. With no regard for the ability of the players, what fraction of all possible two-player competitions will require exactly 7 matches?

 Every possible two-player rounds in this scenario will require from 4 to 7 matches. It is also the case that the person winning the competition wins the last match in each round. For example, for a round to require 5 matches, not only must the winner win 4 of those matches, the 4th win must occur during the 5th match of the round (otherwise the round would have ended at 4 matches). We also must consider that each rouind of competition could be won by one of the two players in the competition. Let us represent the two players as Black (B) and White (W), where the letter and placement of that letter represent a match win for that player. Thus, BBWBB represents a 5-match round with Black winning 4 matches, including the first, second, fourth, and fifth matches. Referring to the previous paragraph, we note that BBBBW is NOT a legitimate 5-match round, for Black would be the round winner after 4 matches. Thus we need to count the number of ways each player can win rounds of 4, 5, 6, and 7 matches. First look at how Black can win. We start by placing a B at the last match position, to assure that Black wins the last match of each round. For a 4-match round, the record of matches won must be _ _ _ B, where the first 3 matches must include 3 wins by Black. This can be done in C(3,3) ways, which is just 1. For a 5-match round, the record of matches won must be _ _ _ _ B, where the first 4 matches must include 3 wins by Black. This can be done in C(4,3) ways. For a 6-match round, the record of matches won must be _ _ _ _ _ B, where the first 5 matches must include 3 wins by Black. This can be done in C(5,3) ways. For a 7-match round, the record of matches won must be _ _ _ _ _ _ B, where the first 6 matches must include 3 wins by Black. This can be done in C(6,3) ways. So for Black to win a round, there are C(3,3)+C(4,3)+C(5,3)+C(6,3) ways. The same reasoning can be used to show there are C(3,3)+C(4,3)+C(5,3)+C(6,3) ways for White to win a round. Therefore, the total number of possible matches is 2*[C(3,3)+C(4,3)+C(5,3)+C(6,3)]. Of these, 2*[C(6,3)] require exactly 7 matches. The desired fraction, then, is just (2*[C(6,3)]) / (2*[C(3,3)+C(4,3)+C(5,3)+C(6,3)]) or C(6,3) / ([C(3,3)+C(4,3)+C(5,3)+C(6,3)]).

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