Maths Olympiad Prep

Library / /91 of 128

Combinatorics Difficulty 6.0 AIME, harder Prove it Philippines

Problem:

How many ways are there to arrange 5 identical red balls and 5 identical blue balls in a line if there cannot be three or more consecutive blue balls in the arrangement?

Solution

Solution:

We first consider the number of ways we can split the blue balls into groups of 1 or 2. The possible ways contain either 5 single blue balls, 3 single blue balls and one group of 2 balls, and 1 single blue ball with two groups of two balls. For each way, there are 1, 4, and 3 ways to arrange these groups.

We can then add in the red balls as the dividers, meaning that there should be at least one red ball to separate each group. The remaining red balls can be placed anywhere, using the Balls and Urns Method.

- For the group of 5, you need 4 red balls to divide them, so there is one remaining ball and 6 urns, so the number of ways you can arrange the red ball is (1+611)=6\binom{1+6-1}{1} = 6.

- For the group of 3 singles and 1 pair, you need 3 red balls, so the number of ways you can arrange the remaining red balls is (2+512)=15\binom{2+5-1}{2} = 15.

- For the group of 1 single and 2 pairs, you need 2 red balls, so the number of ways you can arrange the remaining red balls is (3+413)=20\binom{3+4-1}{3} = 20.

Thus, the total number of ways is 1×6+4×15+3×20=1261 \times 6 + 4 \times 15 + 3 \times 20 = 126.

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.