Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A teacher decided to encourage the kids by distributing prizes to them. Each of the prizes was different from the other. The total number of prize was $k$, and total number of kids was $p$. To encourage the kids, the number of prizes was more than the number of kids. But, the teacher imposed a restriction on herself that each kid would receive $(k – 1)$ prizes at the most. How many ways she could distribute the prizes?

Answer is $p^k-p$

If I understood the problem correctly, it is no-where stated that a student can get no prize at all, and the answer seems to be using this assumption,however I am a bit confused why the answer is not $p^{k-1}$?

If the restriction is that no student can get more than $(k-1)$ prizes then what is wrong with starting with $(k-1)$ distinct prizes and distributing those into $p$ distinct groups (students)?

share|improve this question
    
Then what happens with the last prize? That one needs to be distributed too, right? But then it makes a difference if the first k-1 prizes went to a single student or more students... –  N. S. Nov 6 '11 at 23:34

2 Answers 2

up vote 0 down vote accepted

Suppose there were no restrictions whatsoever and the problem simply said "How can you distribute $k$ prizes among $p$ students?".

For each prize, there are $p$ possibilities for the recipient of that prize. In total, that means there are $p \cdot p \cdot \dots \cdot p$ (with $k$ copies of $p$ in the product) possible ways to assign the prizes. This is the $p^k$ part.

Now let's impose the restriction that no student receives all the prizes (this is the same as saying no student receives more than $k-1$ prizes). Of the $p^k$ configurations we just enumerated, which ones are illegal under this new restriction? Exactly $p$ of them, since there is one illegal configuration for each student (namely, giving that student all the prizes).

Subtracting the illegal configurations from our previous enumeration, we get $p^k - p$ legal configurations.

share|improve this answer
    
But what I wanted to know is what is wrong with $p^{k-1}$? –  Quixotic Nov 6 '11 at 23:31
    
If you simply distribute $k-1$ prizes into the $p$ students, you still have a prize remaining to give out. When you try to give that last prize, you'll have to worry about the case that you are giving it to a student who already has $k-1$ prizes. –  Austin Mohr Nov 6 '11 at 23:34
    
Thanks that rests my doubts :) –  Quixotic Nov 6 '11 at 23:37
    
Just trying to vary the parameters ..in general if we have to distribute k (distict) prizes into p (distinct) students so that no student can get more than (k-n) prizes is $p^k-n \times p$, isn't?! –  Quixotic Nov 7 '11 at 0:22
    
@MaX It is not quite so simple, and to elaborate would be a whole answer unto itself. In your original problem, there was only one way a student could get too many prizes (namely, he received all the prizes). In your new version, there are many ways a student can receive too many gifts and also many students can simultaneously receive too many gifts. If you are interested, you might post your new version as it's own question. –  Austin Mohr Nov 7 '11 at 0:43

The answer can easily be seen with this reasoning: there are p students and k prizes, so the total number of ways the prizes can be distributed is $p^k$ (for each of $k$ prizes, there are $p$ different students to whom it can be given). However, with the added constraint that no student can receive every prize, we must eliminate $p$ of those possibilities (one for when each student receives all of the prizes). Therefore the total number of ways is $p^k - p$.

We can't simply start with $k - 1$ prizes and distribute them to $p$ students because we would be missing the different cases that come from which student gets the last ($k^{th}$) prize.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.