2
$\begingroup$

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)?

  • 0
    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...2011-11-06

2 Answers 2

1

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.

  • 0
    [Done](http://math.stackexchange.com/questions/79704/how-to-distribute-k-distinct-items-into-r-distinct-groups-with-each-groups-r).2011-11-07
0

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.