HMMT 二月 2005 · 冲刺赛 · 第 42 题

英文解析

42. In how many ways can 6 purple balls and 6 green balls be placed into a 4 × 4 grid ofboxes such that every row and column contains two balls of one color and one ball ofthe other color? Only one ball may be placed in each box, and rotations and reflectionsof a single configuration are considered different.
    Solution: 5184
    In each row or column, exactly one box is left empty. There are 4! = 24 ways to choosethe empty spots. Once that has been done, there are 6 ways to choose which two rowshave 2 purple balls each. Now, assume without loss of generality that boxes (1 , 1),
    (2 , 2), (3 , 3), and (4 , 4) are the empty ones, and that rows 1 and 2 have two purpleballs each. Let A , B , C , and D denote the 2 × 2 squares in the top left, top right,
    bottom left, and bottom right corners, respectively (so A is formed by the first tworows and first two columns, etc.). Let a , b , c , and d denote the number of purple ballsin A , B , C , and D , respectively. Then 0 ≤ a, d ≤ 2, a + b = 4, and b + d ≤ 4, so a ≥ d .
    Now suppose we are given the numbers a and d , satisfying 0 ≤ d ≤ a ≤ 2. Fortunately,
    the numbers of ways to color the balls in A , B , C , and D are independent of eachother. For example, given a = 1 and d = 0, there are 2 ways to color A and 1 way tocolor D and, no matter how the coloring of A is done, there are always 2 ways to color
    B and 3 ways to color C . The numbers of ways to choose the colors of all the balls isas follows:
    a \ d 0 1 2
    0 1 · (1 · 2) · 1 = 2 0 0
    1 2 · (2 · 3) · 1 = 12 2 · (1 · 1) · 2 = 4 0
    2 1 · (2 · 2) · 1 = 4 1 · (3 · 2) · 2 = 12 1 · (2 · 1) · 1 = 2
    In each square above, the four factors are the number of ways of arranging the balls in A ,
    B , C , and D , respectively. Summing this over all pairs ( a, d ) satisfying 0 ≤ d ≤ a ≤ 2
    gives a total of 36. The answer is therefore 24 · 6 · 36 = 5184 .
    17