HMMT 二月 2005 · 冲刺赛 · 第 42 题
HMMT February 2005 — Guts Round — Problem 42
题目详情
- [18] In how many ways can 6 purple balls and 6 green balls be placed into a 4 × 4 grid such that every row and column contains two balls of one color and one ball of the other color? Only one ball may be placed in each box, and rotations and reflections of a single configuration are considered different. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, FEBRUARY 19, 2005 — GUTS ROUND
解析
- In how many ways can 6 purple balls and 6 green balls be placed into a 4 × 4 grid of boxes such that every row and column contains two balls of one color and one ball of the other color? Only one ball may be placed in each box, and rotations and reflections of 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 choose the empty spots. Once that has been done, there are 6 ways to choose which two rows have 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 purple balls 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 two rows and first two columns, etc.). Let a , b , c , and d denote the number of purple balls in 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 each other. For example, given a = 1 and d = 0, there are 2 ways to color A and 1 way to color 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 is as 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