HMMT 十一月 2011 · 团队赛 · 第 7 题
HMMT November 2011 — Team Round — Problem 7
题目详情
- [ 7 ] Julia is learning how to write the letter C. She has 6 differently-colored crayons, and wants to write Cc Cc Cc Cc Cc. In how many ways can she write the ten Cs, in such a way that each upper case C is a different color, each lower case C is a different color, and in each pair the upper case C and lower case C are different colors? [GG]eometry
解析
- [ 7 ] Julia is learning how to write the letter C. She has 6 differently-colored crayons, and wants to write Cc Cc Cc Cc Cc. In how many ways can she write the ten Cs, in such a way that each upper case C is a different color, each lower case C is a different color, and in each pair the upper case C and lower case C are different colors? Team Round Answer: 222480 Suppose Julia writes Cc a sixth time, coloring the upper-case C with the unique color different from that of the first five upper-case Cs, and doing the same with the lower-case C (note: we allow the sixth upper-case C and lower-case c to be the same color). Note that because the colors on the last Cc are forced, and any forced coloring of them is admissible, our problem is equivalent to coloring these six pairs. There are 6! ways for Julia to color the upper-case Cs. We have two cases for coloring the lower-case Cs: • Case 1: the last pair of Cs use two different colors. In this case, all six lower-case Cs have a different color to their associated upper-case C, and in addition the six lower-case Cs all use each color exactly once. In other words, we have a derangement* of the six colors, based on the colors of the upper-case Cs. We calculate D = 265 ways to color the lower-case Cs here. 6 • Case 2: the last pair of Cs have both Cs the same color. Then, the color of the last lower-case C is forced, and with the other five Cs we, in a similar way to before, have a derangement of the remaining five colors based on the colors of the first five lower-case Cs, so we have D = 44 ways 5 to finish the coloring. Our answer is thus 720(265 + 44) = 222480. *A derangement is a permutation π of the set { 1 , 2 , . . . , n } such that π ( k ) 6 = k for all k , i.e. there are no fixed points of the permutation. To calculate D , the number of derangements of an n -element n set, we can use an inclusion-exclusion argument. There are n ! ways to permute the elements of the set. ( ) n n ! Now, we subtract the number of permutations with at least one fixed point, which is ( n − 1)! = , 1 1! since we choose a fixed point, then permute the other n − 1 elements. Correcting for overcounting, ( ) n n ! we add back the number of permutations with at least two fixed points, which is ( n − 2)! = . 2 2! Continuing in this fashion by use of the principle of inclusion-exclusion, we get ( ) n 1 1 1 ( − 1) D = n ! − + + · · · + . n 0! 1! 2! n !