Note: The notation C(n,r) will mean "n choose r".
This page is maintained by Amit Chakrabarti.
Adding it all up gives 1120 possible teams. If you call the special players A and B and want to distinguish between the cases when A plays in the backfield and B on the line and when A plays on the line and B on the backfield, then the last of the six cases gives double the number of teams. Counting this way you get 1120 + 280 = 1400 teams.
Both answers have been accepted for full credit.
[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*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)There have been two interpretations of this problem: that the secretary must avoid point (4,3) and that he must avoid all four edges of the square with vertices (4,3), (5,3), (4,4) and (5,4). I've given full credit for both interpretations. In the former interpretation, 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.
In the latter interpretation we must additionally avoid the paths which do not touch (4,3) but use either the "right edge" or the "top edge" of the above-mentioned square. There are C(5+2, 2) * C(4+3, 3) = 735 paths of the former kind and C(3+4, 4) * C(4+3, 3) = 1225 paths of the latter kind. We are left with 7030 - 735 - 1225 = 5070 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!
[29] In a combination, suppose there are i_1 objects of type 1, i_2 of type 2 and so on. The combination is uniquely determined by the values of the integers (i_1, i_2, ..., i_k). The integer i_j may take any of the (1 + n_j) values from 0 thru n_j. Thus, there are a total of
(1 + n_1) * (1 + n_2) * ... * (1 + n_k)combinations.
[31] Substituting
y_1 = x_1 - 2 y_2 = x_2 y_3 = x_3 + 5 y_4 = x_4 - 8we 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.
We have counted royal straight flushes and straight flushes as flushes and as straights.
[2] For this problem all you needed to do was write a program to find the k for which the success probability of the k-strategy is highest, and the corresponding value of that probability. Most people have got this problem right. Many have given an argument which shows that the best k to use is approximately n/e, using the fact that 1 + 1/2 + 1/3 + ... + 1/m approximately equals ln(m).