Maths Olympiad Prep

Library / /8 of 27

Combinatorics Difficulty 5.9 AIME, harder Prove it Czech-Polish-Slovak Mathematical Match

We distribute n1n \ge 1 labelled balls among nine persons AA, BB, CC, DD, EE, FF, GG, HH, II. Determine in how many ways it is possible to distribute the balls under the condition that AA gets the same number of balls as the persons BB, CC, DD and EE together.

Solution

Consider the polynomial
(x+2)2n=(x2+4x+4)n==(x2+x+x+x+x+1+1+1+1)(x2+x+x+x+x+1+1+1+1)(x2+x+x+x+x+1+1+1+1) (x+2)^{2n} = (x^2 + 4x + 4)^n = \\ = (x^2 + x + x + x + x + 1 + 1 + 1 + 1)(x^2 + x + x + x + x + 1 + 1 + 1 + 1) \dots \\ (x^2 + x + x + x + x + 1 + 1 + 1 + 1)
and suppose that we multiply out the brackets, obtaining 9n9^n summands. We show the one-to-one correspondence between the number of xnx^n's and the number of the distributions we deal with in the problem.
Suppose we have such a distribution. If the kk-th ball goes to AA, we pick x2x^2 from the kk-th bracket. If it goes to BB, CC, DD, EE, we pick the first, second, third or fourth 11, respectively, from the kk-th bracket. If it goes to FF, GG, HH, II, then we take the first, second, third or fourth xx from the kk-th bracket. Now if we multiply the factors we have chosen, we see, that the result is equal to xnx^n if and only if AA gets the same number of balls as BB, CC, DD, EE jointly.
Therefore, the number of the distributions we are interested in is equal to the coefficient at xnx^n in the polynomial (x+2)2n(x+2)^{2n}, that is,
(2nn)2n. \binom{2n}{n} \cdot 2^n.

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.