HMMT 二月 2006 · COMB 赛 · 第 8 题

英文解析

8. In how many ways can we enter numbers from the set { 1 , 2 , 3 , 4 } into a 4 × 4 array sothat 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 tocontain 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
   In (iv), switch 3 and 4 (relabeling doesn’t affect the coolness of the array); then, it 3
   becomes
   1 2 4 3
   3 4 2 1
   Now, interchange the last two columns, which also does not affect the coolness. Thisgives 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 coolarrays with (ii) equals those with (iii).
   So we only need consider cases (i) and (ii). It is easy to verify that there are four coolarrays with (i), determined precisely by, say, the first two entries of the third row; andtwo with (ii), determined precisely by, say the first entry of the third row. Hence, theanswer is 4! × (4 + 2) × 2 = 288.