Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers



Possible Solutions: Supplementary Problems Set B


1. This question depends on how you define the phrase "different pizzas." It's clear there's one choice from three sizes and one crust from two types. This gives us 6=3*2 different size/crust combinations. Now consider toppings. How many could you have?

I suggest there are 5 toppings to choose from and you can select from none to all of them. So we need to count the ways we can get 0 toppings, 1 topping, and so on, through 5 toppings. I do not consider order important, so I will count the possibilities using combinations.

The number of ways to select no toppings is C(5,0)=1, to select 1 topping is C(5,1)=5, 2 toppings C(5,2)=10, 3 toppings C(5,3)=10, 4 toppings C(5,4)=5, and 5 toppings C(5,5)=1. These choices sum to 32. There are 32 different combinations of pizza toppings given the assumptions I've made here.

Therefore, there are 6*32=192 different pizzas that can be ordered at Blaise's Bistro.

2. Blaise's specials board will display three soda names. The arrangement matters here, so we use permutations. From the 6 sodas available, Blaise chooses and arranges three of them. This is P(6,3)=120. There are 120 soda displays Blaise could use.

3.a. Because the four sets of folks from which the next selection will be made are disjoint sets, we can apply the addition principle to determine there are 5+6+2+4=17 possible next patients.

3.b. We are selecting without arranging, and selection from one set does not influence the selection from another set. We can use the multiplication principle here to determine that there are 5*6*2*4=240 ways to assemble the desired group.

3.c. We use the 240 ways determined in (3b) and permute each one. For each of the 240 groups, there are 4!=24 ways to arrange it. Therefore, there are 240*24=5760 ways arrange a desired group as described.

4. We are arranging 4 digits from the set {0,1,2,...,9} and not allowing repetition. The two restrictions we must honor are that the digit 0 cannot appear in the thousands' position and that the units digit be odd. Start by assuring there is an odd units' digit. There are 5 odd digits to choose from. This leaves us 8 digits to choose from for the thousands' position (0 not available, another non-zero odd digit used in the units' position), 8 digits for the hundreds' position (0 back in the set), and 7 for the tens' position. By the multiplication principle we have 8*8*7*5=2240 odd integers from 1000 to 9999 inclusive.

5.a. The action of dealing implies we are concerned with order, so we use permutations. There are P(52,5) such arrangements.

5.b. Now all we are concerned about is the set or cards in hand, not their order. There are C(52,5) such sets.

6. One way to solve this problem is to choose 15 squares on the checkerboard and then arrange the 15 desired integers in those selected squares. The first task can be completed in C(64,15) ways and the second in P(15,15)=15! ways. By the multiplication principle, there are C(64,15)*P(15,15) ways to place the integers. Simplifying the last expression yields P(64,15), which invites another way to see the solution, as permutations of 15 of the 64 squares.

7. Consider three disjoint cases, count the possibilities for each, and sum the results.

Case I: Neither the digit 5 nor 6 is in the number. Here, we now have 7 digits to use to create the 7-digit number with no repeating digits. There are P(7,7)=7! Such numbers.

Case II: Both the digits 5 and 6 are in the number. First, arrange five digits from the set of digits that does not include 5 and 6: {1,2,3,4,7,8,9}. This can be done in P(7,5) ways. Now, to be sure that 5 and 6, both of which must be in the number for this case, do not appear consecutively, select two of the six positions that exist beside the 5 digits already chosen. This is C(6,2). Said another way, having chosen a line up of five digits (none of which are 5 or 6), select two of the six slots that exist between or outside the five digits: _X_X_X_X_X_. Once the two slots are selected, permute the 2 values (5 and 6) that we place in the two slots. This is P(2,2). This gives us P(7,5)*C(6,2)*P(2,2)=P(7,5)*P(6,2) ways for this case.

Case III: Exactly one of the digits 5 or 6 is in the number. Here, there's no concern for the adjacency problem. First create a 6-digit number from the 7 digits in the set {1,2,3,4,7,8,9}. This can be done in P(7,6) ways. Now, from among the seven slots surrounding these already-chosen six digits, chose one slot in which to place a 5 or a 6. There are C(7,1)=7 ways to choose a slot and 2 ways to choose a 5 or a 6 to place there. This yields P(7,6)*7*2 7-digit numbers that have either a 5 or a 6 but not both.

By the addition principle, there are P(7,7) + P(7,5)*P(6,2) + P(7,6)*7*2 different 7-digit numbers that meet the stated criteria.

8.a. Because two points determine a line, we determine how many unique pairs of points there are in a set of 25. Because order doesn't matter in stating or in drawing a line, we use combinations. There are C(25,2) different pairs of points and therefore that same number of straight lines.

8.b. Three unique non-collinear points in a plane determine a triangle. Following the same justification as in (8a), there are C(25,3) such triangles.

9. We first seat the students who must be in a specified row. The five students who sit in the front can be seated in P(8,5) ways, for the arrangement of the students as well as the choice of chairs is important. Likewise, there are P(8,4) ways to seat the four students who always sit in the back row. This leaves 7 seats, somewhere in the two rows, for the remaining 5 students. These students can be seated in P(7,5). With respect to the number of chairs available, the seating of each of these three groups is independent of one another (given that the always first-row and always-second-row are assured of seats first), so the total number of ways the 14 students can be seated is P(8,5)*P(8,4)*P(7,5).

10. We are not concerned with any particular offices or assignments within the committee, so we select 10 from the 750 students. This is just C(750,10).

11.a. There are three disjoint possibilities for the number of faculty on the committee. There could be three, four, or five faculty members. If there are three faculty members, they could be selected in C(30,3) ways. With those three faculty, the required five students could be selected in C(30,5) ways. Thus, a committee with exactly 3 faculty and 5 students could be created in C(30,3)*C(30,5) ways. Note that combinations are used throughout because no particular arrangement within the committee is required.

In a similar fashion, a committee with 4 faculty and 4 students can be created in C(30,4)*C(30,4) ways, and a committee with 5 faculty and 3 students can be created in C(30,5)*C(30,3) ways.

Because the possibilities for number of faculty are disjoint, we add the ways each type of committee could be formed. Therefore, there are 2*C(30,3)*C(30,5)+C(30,4)*C(30,4) ways to create the desired committee.

Note that a common wrong answer here is C(30,3)*C(30,3)*C(54,2). What logic is being used here, and why is it incorrect?

11.b. The complement to having at least one faculty member on the committee is that there be no faculty member on the committee. The latter situation could be created in C(30,8) ways, that is, by only choosing students. In all there are C(60,8) groups of 8 that can be formed from the 60-person pool that includes all eligible faculty and students. To determine the number of committee that would have at least one faculty member, we subtract the number of ways to assure no faculty are on a committee from the total number of committees that can be formed: C(60,8) - C(30,8).

12. A zero (0) occurs when 10 is a factor of a number. For two zeros to occur, 10 must be a factor twice. Our task is to determine how many times 10 is a factor of 52!. To count 10s as factors, we determine how many times 2 and 5 occur as factors, because 10 has 2*5 as its prime factorization.

The number 52! is the same as 52*51*50*...*3*2*1. The value 2 is a factor of every even term in 52!, In 2, 4, 6, 8, and so on. Thus, 2 appears at least 26 times. The value 5 is a factor when a term's unit digit is 0 or 5. This occurs with 5, 10, 15, 20, 25, 30, 35, 40, 45, and 50. No other terms have 5 as a factor. Note that 5 occurs twice as a factor in 25 and in 50, otherwise occurring once. Thus, 5 occurs as a factor 12 times in 52!. With this information, we know 10 is a factor 12 times, and therefore there are 12 consecutive zeros immediately to the left of the decimal point in 52!.

13. The question does not stipulate that a color may not repeat, in fact, it is implied that colors can repeat by the statement that an adequate supply of flags are available. Thus, for the 5-flag set, there are 7 choices for the color of the first flag, 7 for the next, and so on for each of the five flags. Because each flag color choice is independent, we multiply these individual possibilities to get 7*7*7*7*7 or 7^5 possible arrangements.

14. We assume there are 6 chairs at the round table.

If we assume that the three men are distinguishable from one another as are the three women, we simply have 6 people to arrange. In a line, this can de done in 6! ways. To account for duplication due to relative positions not changing at a round table, we divide by 6, since each of the 6! arrangements matches 5 others in the set according to relative position around the table. Therefore, there are 6!/6 or just 5! ways to arrange the 3 men and 3 women.

If the men are not distinguishable from one another nor are the women, we can solve the linear problem using combinations. From a set of 6 chairs in a line, choose three and place the men there are use the remaining three for the women. Again, we are not concerned with permuting the men nor women in each of their respective sets. This task can be done in C(6,3) ways.

I've found no combinatorial way to go from the linear case to the circular case for this version of the problem. I used brute force to look at the C(6,3) = 20 ways to arrange the three men and three women in a line, and then accounted for which of those 20 arrangements would actually be repeats when rotated around a table.

I determined only 4 unique arrangements of 3 non-distinct men and 3 non-distinct women around a 6-chair table. The drawing below illustrates those, where M represents a man seated and W represents a woman seated.