HMMT 二月 2006 · COMB 赛 · 第 8 题
HMMT February 2006 — COMB Round — Problem 8
题目详情
- In how many ways can we enter numbers from the set { 1 , 2 , 3 , 4 } into a 4 × 4 array so that all of the following conditions hold? (a) Each row contains all four numbers. (b) Each column contains all four numbers. (c) Each “quadrant” contains all four numbers. (The quadrants are the four corner 2 × 2 squares.)
解析
- In how many ways can we enter numbers from the set { 1 , 2 , 3 , 4 } into a 4 × 4 array so that all of the following conditions hold? (a) Each row contains all four numbers. (b) Each column contains all four numbers. (c) Each “quadrant” contains all four numbers. (The quadrants are the four corner 2 × 2 squares.) Answer: 288 Solution: Call a filled 4 × 4 array satisfying the given conditions cool . There are 4! possibilities for the first row; WLOG, let it be 1 2 3 4. Since each quadrant has to contain all four numbers, we have exactly four possibilities for the second row, namely: (i) 3 4 1 2 (ii) 3 4 2 1 (iii) 4 3 1 2 (iv) 4 3 2 1 I claim that the number of cool arrays with (i) is equal to those with (iv), and that the number of cool arrays with (ii) is equal to those with (iii). Let’s first consider (i) and (iv). Now, (i) is 1 2 3 4 3 4 1 2 while (iv) is 1 2 3 4 4 3 2 1 3 In (iv), switch 3 and 4 (relabeling doesn’t affect the coolness of the array); then, it becomes 1 2 4 3 3 4 2 1 Now, interchange the last two columns, which also does not affect the coolness. This gives us (i). Hence, the cool arrays with (i) and the cool arrays with (iv) have a 1:1 correspondence. Using the exact same argument, we can show that the number of cool arrays with (ii) equals those with (iii). So we only need consider cases (i) and (ii). It is easy to verify that there are four cool arrays with (i), determined precisely by, say, the first two entries of the third row; and two with (ii), determined precisely by, say the first entry of the third row. Hence, the answer is 4! × (4 + 2) × 2 = 288.