Maths Olympiad Prep

Library / /35 of 100

Combinatorics Difficulty 4.6 AIME Find the answer China

Twenty-four volunteers will be allocated to three schools. The rule is that each school will accept at least one volunteer and all the schools will accept different numbers of volunteers. Then there are ______ different ways of allocating volunteers.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We may use each space between every two consecutive bars (|) to represent a school and each asterisk (*) to represent a volunteer, as seen in the following example; the first, second and third schools receive 44, 1818 and 22 volunteers, respectively.
| * * * * | * \cdots * | * * |
Then the allocation problem may be regarded as a permutation-and-combination problem of 44 bars and 2424 asterisks.

Since the two ends of the line must be occupied by a bar, respectively, there are (232)=253\binom{23}{2} = 253 ways to insert the other 22 bars into the 2323 spaces between the 2424 asterisks such that there is at least 11 asterisk between every two consecutive bars, in which there are 3131 ways that at least two schools have the same number of volunteers. So the number of allocating ways satisfying the conditions is 25331=222253 - 31 = 222.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.