Maths Olympiad Prep

Library / /188 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

Noew is writing a 1515-problem mock AIME consisting of four subjects of problems: algebra, geometry, combinatorics, and number theory. The AIME is considered somewhat evenly distributed if there is at least one problem of each subject and there are at least six combinatorics problems. Two AIMEs are considered similar if they have the same subject distribution (same number of each subject). How many non-similar somewhat evenly distributed mock AIMEs can Noew write?

2019 CCA Math Bonanza Lightning Round #2.1

Solution

1. Assigning the minimum required problems:
- We need at least 6 combinatorics problems.
- We need at least 1 problem each from algebra, geometry, and number theory.
- This accounts for 6+1+1+1=96 + 1 + 1 + 1 = 9 problems.

2. Remaining problems:
- Since the total number of problems is 15, the remaining number of problems to be assigned is 159=615 - 9 = 6.

3. Using stars and bars:
- We need to distribute these 6 remaining problems among the four subjects: algebra, geometry, combinatorics, and number theory.
- Let aa, gg, cc, and nn represent the number of additional problems assigned to algebra, geometry, combinatorics, and number theory, respectively.
- We need to solve the equation a+g+c+n=6a + g + c + n = 6 where a,g,c,n0a, g, c, n \geq 0.

4. Applying the stars and bars theorem:
- The number of non-negative integer solutions to the equation a+g+c+n=6a + g + c + n = 6 is given by the binomial coefficient:
(6+4141)=(93) \binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}

5. Calculating the binomial coefficient:
(93)=9×8×73×2×1=84 \binom{9}{3} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84

Therefore, the number of non-similar somewhat evenly distributed mock AIMEs that Noew can write is 8484.

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.