Maths Olympiad Prep

Library / /5 of 7

Combinatorics Difficulty 6.8 National Olympiad Prove it Vietnam

Calculate the number of the arrangements of 5 girls G1G_1, G2G_2, G3G_3, G4G_4 and G5G_5 and 12 boys in a row satisfying the following conditions:
1. The order of the girls from left to right is G1G_1, G2G_2, G3G_3, G4G_4 and G5G_5.
2. There are at least 3 boys between G1G_1 and G2G_2.
3. There are at least 1 boy and at most 4 boys between G4G_4 and G5G_5.

Solution

Recall that the number of natural solutions of the equation
i=1nxi=m \sum_{i=1}^{n} x_i = m
is (m+n1n1)\binom{m+n-1}{n-1}. We will use this fact to calculate the number of the arrangements of boys and girls satisfying the given conditions.

Let xix_i be the number of boys standing between Gi1G_{i-1} and GiG_i for i2i \ge 2; x1x_1 be the number of boys standing on the left of G1G_1, and x6x_6 be the number of the boys standing on the right of G5G_5. Then we have 3x23 \le x_2, 1x441 \le x_4 \le 4, and
x1+x2+x3+x4+x5+x6=12.(9) x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 12. \qquad (9)
Replacing yi=xiy_i = x_i for i2i \ne 2 and y2=x23y_2 = x_2 - 3, we have
y1+y2+y3+y4+y5+y6=9, y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 9,
where yi0y_i \ge 0 and 1y441 \le y_4 \le 4. Putting y4=1,2,3,4y_4 = 1, 2, 3, 4 into (9), we conclude that the number of solutions (x1,x2,x3,x4,x5,x6)(x_1, x_2, x_3, x_4, x_5, x_6) satisfying (9) is
y4=14(9y4+5151)=(135)(95)=1161. \sum_{y_4=1}^{4} \binom{9-y_4+5-1}{5-1} = \binom{13}{5} - \binom{9}{5} = 1161.
Since we can permute the boys in the row, the total number of arrangements of boys and girls satisfying the given conditions is 12!×116112! \times 1161.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.