PUMaC 2014 · 团队赛 · 第 12 题

PUMaC 2014 — Team Round — Problem 12

[ 9 ] Let n be the number of possible ways to place six orange balls, six black balls, and six white balls in a circle (two placements are considered equivalent if one can be rotated to fit the other). What is the remainder when n is divided by 1000?

解析

[ 9 ] Let n be the number of possible ways to place six orange balls, six black balls, and six white balls in a circle (two placements are considered equivalent if one can be rotated to fit the other). What is the remainder when n is divided by 1000? Solution: We can partition the placements into four categories, based on the size of the smallest subper- mutation that can be repeated to fill the whole circle: 3-3-3-3-3-3, 6-6-6, 9-9, and 18. There are a total 3! = 6 permutations of the form 3-3-3-3-3-3. Correcting for repetition, we 6 get = 2. 3 6! There are a total − 6 = 90 − 6 = 84 permutations of the form 6-6-6. Correcting for 2!2!2! 84 repetition, we get = 14. 6 9! There are a total − 6 = 1680 − 6 = 1674 permutations of the form 9-9. Correcting for 3!3!3! 1674 repetition, we get = 186. 9 18! The remaining permutations are of the form 18, and there are s = − (6 + 84 + 1674) of 6!6!6! 18 · 17 · ... · 7 them. Simplifying, we get s = − (6 + 84 + 1674) = 18 · 17 · 4 · 14 · 13 · 11 · 7 − 1764. 6!6! s Correcting for repetition, we get = 17 · 4 · 14 · 13 · 11 · 7 − 98. 18 Recall that 13 · 11 · 7 = 1001 ≡ 1 (mod 1000). So, our answer is 2 + 14 + 186 + 17 · 4 · 14 − 98 = 1056 ≡ 56 (mod 1000).