# Combinations and Permutations Question

I am sitting my A level exams (MEI) and I was looking through the S1 past papers and I encountered this question in the January 2010 paper:

Three prizes, one for English, one for French and one for Spanish, are to be awarded in a class of 20 students. Find the number of different ways in which the three prizes can be awarded if

(i) no student may win more than 1 prize,

(ii) no student may win all 3 prizes.

I tried to do part 1 using combinations, ie: 20 choose 3, but that didn't work. I couldn't even attempt part 2.

(i) 20 × 19 × 18 = 6840

(i) (20^3) – 20 = 7980

Could someone please explain to me how these answers have been reached? The paper is at http://www.mei.org.uk/files/papers/s110ja_4766rev.pdf in case you want to see it. Mark scheme is at the end.

-

1. The prize for English may be awarded in any of 20 ways: any student may get it. After the English prize has been awarded, the French prize may be awarded to any of the 19 students who have not yet won the price. After both the English and French prize are awarded, the Spanish prize may be awarded to any one of the 18 remaining students who have not won either of the other two prizes. Since all three prizes are awarded, we multiply the total possibilities: $20\times 19\times 18$.

You may feel a little queasy about why I selected to award the prizes in that order: it doesn't matter in which order you award them. The "first prize" can go to any of 20 students; the "second prize" to any of the remaining 19; and the "third prize" to any of the remaining 18.

2. First we will count all the cases we want, but add some cases we don't want (because it makes counting easier). Then, we will "throw away" (by subtracting) the cases we don't want.

Forget the restriction first: the English prize can be awarded to any of 20 students; the same for French; the same for Spanish. So there are a total of $20\times 20\times 20 = 20^3$ ways of distributing all the prizes.

But this includes cases in which we award all three prizes to the same student, which we aren't supposed to do. How many of these distributions award all prizes to the same student? Well, we can award all prizes to the first student; or all prizes to the second;...; or all prizes to the 20th student. So in 20 of the cases, we award all prizes to the same student. Since there are a total of $20^3$ ways of distributing the prizes, but $20$ of them are "bad", the total number of "good" ways of distributing the prizes is $20^3 - 20$ (total ways minus bad ways).

-
Thanks! That explained it very well! So I can't really use nCr or nPr for these questions at all? I just tried it and nPr works for the first one. Why? I thought you used nPr when the order matters. And it clearly doesn't. – Ben Elgar May 14 '11 at 6:26
@Ben Elgar: Unfortunately, all too often, when a student sees a problem, the first impulse is to ask: do I use $P(n,r)$ or $C(n,r)$? The first question should always be, "What's happening here, how can I count this concrete collection of objects?". After one does enough varied problems, one notices certain recurrent strategies. But "What formula do I use?" is only a viable strategy in the simplest of problems. – André Nicolas May 14 '11 at 6:43
@Ben Edgar: There are $3$ chairs in a row, the First Prize Chair, the Second Prize Chair, and the Third Prize Chair. The number of ways of choosing the winners of the prizes (if no one can get more than one prize) is, I think clearly, the same as the number of ways of choosing and seating $3$ people in these chairs. So, using this analysis, the fact that the number of ways is $P(20,3)$ is clear. – André Nicolas May 14 '11 at 12:34
@Ben Edgar: I also suggest you take a look at this answer to an old question that discusses some of the basics. – Arturo Magidin May 14 '11 at 19:39
@User6312: Ah that makes it much clearer, I see now that I'd abstracted the problem to too great an extent and had lost the fact that the prizes are in fact different. @Artuo Magidin: Thanks! That link was very handy, not so much for this question, but for a couple of other problems I had earlier. Thanks to everyone! You've all been very helpful! – Ben Elgar May 15 '11 at 11:19