Solutions to Homework Set 3

The solutions that follow are not the only possible ones. They are not necessarily the best possible either. If you find a mistake in any of these solutions or if you feel that any solution can be significantly improved, please feel free to send us email and we'll do the needful.

 Note:
Several problems have ambiguous statements, such as #21. So there can be different intepretations. As long as your assumption is acceptable and your solution is consistent with your assumption, you'll receive full credit. For those problems I only post the most common answers.

Problems from Section 3.6

[11] Consider the various possibilities for the two special players who can play in either position. Find out the number of teams possible in each case:
     
  1. Special players not used: C(5,4)*C(8,7) = 40 teams
  2. One special player used on line: 2*C(5,4)*C(8,6) = 280 teams
  3. Both special players used on line: C(5,4)*C(8,5) = 280 teams
  4. One special player used in backfield: 2*C(5,3)*C(8,7) = 160 teams
  5. Both special players used in backfield: C(5,2)*C(8,7) = 80 teams
  6. Special players used in different positions: 2*C(5,3)*C(8,6) = 560 teams
Adding it all up gives 1400 possible teams. 

[13] For the five front-only students, there are P(8,5) ways for them to sit. For the four back-only students, the number is P(8,4). Now we have 7 seats and 5 students remaining, there are P(7,5) ways to arrange them. So total P(8,5)*P(8,4)*P(7,5)=28,449,792,000 

[19] Let us count the number of circular permutations with 0 and 9 opposite each other. As is usual with circular permutations, we fix the position of some element, say 0. This fixes the position of 9 automatically. The other 8 numbers can now be permuted in 8! ways. That leaves 9! - 8! = 322560 permutations with 0 and 9 not opposite. 

[21] (a) The secretary has to walk 9 blocks east and 7 blocks north; his path can therefore be thought of as a permutation of (a multiset of) 9 EASTs and 7 NORTHs. Therefore, there are C(9+7, 7) = 11440 possible paths.

 (b)The secretary must avoid point (4,3). Paths to be avoided can be chosen by taking one of the C(4+3, 3) paths from (0,0) to (4,3) and catenating it with one of the C(5+4, 4) paths from (4,3) to (9,7). This gives 11440 - C(7,3)*C(9,4) = 7030 possible paths.

[22] This one was really simple. The number of circular permutations equals the number of linear permutations divided by the total number of objects. The total number of object in this case is n+1. The number of linear permutations is, from the multiset permutation formula, equal to 

               (n + 1)!
     ----------------------------
     1! * n_1! * n_2! * ... * n_k!
And that's it! 

[31] Substituting 

y_1 = x_1 - 2
y_2 = x_2
y_3 = x_3 + 5
y_4 = x_4 - 8
we see that the problem is equivalent to finding non-negative integers y_1, y_2, y_3 and y_4 such that their sum is 25. Therefore there are C(25+4-1, 25) = C(28,3) = 3276 solutions. 

[35] Since the order in which the drinks are given is unimportant, we may assume any particular order provided we do not overcount. This is a useful general principle.

 There are four ways to give away the lime drink, then three ways to give away the lemon drink (because the same student may not get both). This forces us to give one orange drink each to the two students who've got nothing so far. The remaining eight orange drinks can be distributed as we like between the four students and by now we ought to see immediately that there are C(8+4-1, 8) = 165 ways to do that.

 Thus the total number of ways is 4*3*165 = 1980.