Maths Olympiad Prep

Library / /10 of 10

Combinatorics Difficulty 6.6 National Olympiad Prove it Philippines

Problem:

In how many ways can nine chips be selected from a bag that contains three red chips, three blue chips, three white chips, and three yellow chips? (Assume that the order of selection is irrelevant and that the chips are identical except for their color.)

Solution

Solution:

Let rr, bb, ww, and yy denote the number of red, blue, white, and yellow chips selected, respectively. We want the number of integer solutions to
r+b+w+y=9 r + b + w + y = 9
subject to 0r30 \leq r \leq 3, 0b30 \leq b \leq 3, 0w30 \leq w \leq 3, 0y30 \leq y \leq 3.

Since there are only 3 of each color, the maximum for each variable is 3.

We can use generating functions. The generating function for each color is (1+x+x2+x3)(1 + x + x^2 + x^3). The generating function for the total is
(1+x+x2+x3)4 (1 + x + x^2 + x^3)^4
We want the coefficient of x9x^9 in this expansion.

Let us expand (1+x+x2+x3)4(1 + x + x^2 + x^3)^4.

Alternatively, note that r+b+w+y=9r + b + w + y = 9 and 0r,b,w,y30 \leq r, b, w, y \leq 3.

Let us count the number of non-negative integer solutions to r+b+w+y=9r + b + w + y = 9 with r,b,w,y3r, b, w, y \leq 3.

We can use the inclusion-exclusion principle.

Let NN be the number of non-negative integer solutions to r+b+w+y=9r + b + w + y = 9 with r,b,w,y3r, b, w, y \leq 3.

Let SS be the set of all non-negative integer solutions to r+b+w+y=9r + b + w + y = 9.

The number of non-negative integer solutions is (9+4141)=(123)=220\binom{9 + 4 - 1}{4 - 1} = \binom{12}{3} = 220.

Now, subtract the solutions where at least one variable exceeds 3.

Let AA be the set where r4r \geq 4, BB where b4b \geq 4, CC where w4w \geq 4, DD where y4y \geq 4.

By inclusion-exclusion:

N=S(A+B+C+D)+(AB+AC+AD+BC+BD+CD)(ABC+ABD+ACD+BCD)+ABCDN = S - (|A| + |B| + |C| + |D|) + (|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|) - (|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|) + |A \cap B \cap C \cap D|

First, A|A| is the number of solutions with r4r \geq 4. Let r=r40r' = r - 4 \geq 0, so r+b+w+y=5r' + b + w + y = 5. The number of non-negative integer solutions is (5+4141)=(83)=56\binom{5 + 4 - 1}{4 - 1} = \binom{8}{3} = 56.

Similarly, B=C=D=56|B| = |C| = |D| = 56.

Now, AB|A \cap B| is the number of solutions with r4r \geq 4 and b4b \geq 4. Let r=r40r' = r - 4 \geq 0, b=b40b' = b - 4 \geq 0, so r+b+w+y=1r' + b' + w + y = 1. The number of non-negative integer solutions is (1+4141)=(43)=4\binom{1 + 4 - 1}{4 - 1} = \binom{4}{3} = 4.

There are (42)=6\binom{4}{2} = 6 such pairs, so the sum over all pairs is 6×4=246 \times 4 = 24.

Now, ABC|A \cap B \cap C| is the number of solutions with r,b,w4r, b, w \geq 4. Let r=r4r' = r - 4, b=b4b' = b - 4, w=w4w' = w - 4, so r+b+w+y=94×3=3r' + b' + w' + y = 9 - 4 \times 3 = -3. There are no non-negative integer solutions to this equation, so ABC=0|A \cap B \cap C| = 0.

Similarly, all triple and quadruple intersections are zero.

So,
N=2204×56+6×4=220224+24=20 N = 220 - 4 \times 56 + 6 \times 4 = 220 - 224 + 24 = 20

Therefore, there are 20\boxed{20} ways to select nine chips from the bag.

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.