Maths Olympiad Prep

Library / /28 of 520

Combinatorics Difficulty 6.3 National olympiad Find the answer

In how many ways can 1010 distinct books be placed onto 33-shelf bookcase in such a way that no shelf is empty?

Pick one

Solution

1. First, we need to determine the number of ways to distribute 10 distinct books onto 3 shelves such that no shelf is empty. This is a classic application of the "stars and bars" theorem with the additional constraint that no shelf can be empty.

2. We start by considering the total number of ways to distribute 10 books into 3 groups without any restrictions. This can be done using the multinomial coefficient:
k1+k2+k3=1010!k1!k2!k3! \sum_{k_1 + k_2 + k_3 = 10} \frac{10!}{k_1! k_2! k_3!}
where k1,k2,k30k_1, k_2, k_3 \geq 0.

3. However, we need to ensure that no shelf is empty. This means k1,k2,k31k_1, k_2, k_3 \geq 1. To account for this, we use the principle of inclusion-exclusion.

4. First, calculate the total number of ways to distribute the books without any restrictions:
310 3^{10}
This is because each of the 10 books can go on any of the 3 shelves.

5. Next, subtract the cases where at least one shelf is empty. There are (31)=3\binom{3}{1} = 3 ways to choose which shelf is empty, and for each of these, the remaining 10 books can be distributed among the 2 remaining shelves:
3210 3 \cdot 2^{10}

6. However, we have subtracted too much, as we have subtracted the cases where two shelves are empty twice. There are (32)=3\binom{3}{2} = 3 ways to choose which two shelves are empty, and for each of these, the remaining 10 books must all go on the one remaining shelf:
3110 3 \cdot 1^{10}

7. Applying the principle of inclusion-exclusion, the number of ways to distribute the books such that no shelf is empty is:
3103210+3110 3^{10} - 3 \cdot 2^{10} + 3 \cdot 1^{10}

8. Calculate the values:
310=59049 3^{10} = 59049
210=1024 2^{10} = 1024
110=1 1^{10} = 1

9. Substitute these values back into the inclusion-exclusion formula:
5904931024+31=590493072+3=55980 59049 - 3 \cdot 1024 + 3 \cdot 1 = 59049 - 3072 + 3 = 55980

10. Finally, we need to account for the fact that the books are distinct. There are 10!10! ways to arrange the 10 distinct books. Therefore, the total number of ways to place the 10 distinct books onto the 3 shelves such that no shelf is empty is:
5598010! 55980 \cdot 10!

The final answer is 8110!\boxed{81 \cdot 10!}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.