HMMT 二月 2009 · COMB 赛 · 第 9 题

英文解析

9. [ 5 ] The squares of a 3 × 3 grid are filled with positive integers such that 1 is the label of the upperleftmost square, 2009 is the label of the lower-rightmost square, and the label of each square dividesthe one directly to the right of it and the one directly below it. How many such labelings are possible?
   Answer: 2448
   Solution: We factor 2009 as 7 · 41 and place the 41’s and the 7’s in the squares separately. The 2
   number of ways to fill the grid with 1’s and 41’s so that the divisibility property is satisfied is equal tothe number of nondecreasing sequences a , a , a where each a ∈ { 0 , 1 , 2 , 3 } and the sequence is not
   1 2 3 i
   0 , 0 , 0 and not 1 , 1 , 1 (here a corresponds to the number of 41’s in the i th column.) Thus there arei
   ( )
   3+4 − 1 − 2 = 18 ways to choose which squares are divisible by 41.
   To count the arrangements of divisibility by 7 and 49, we consider three cases.3
   If 49 divides the middle square, then each of the squares to the right and below it are divisible 49.
   The two squares in the top row (besides the upper left) can be (1 , 1), (1 , 7), (1 , 49), (7 , 7), (7 , 49), or
   (49 , 49) (in terms of the highest power of 7 dividing the square). The same is true, independently, forthe two blank squares on the left column, for a total of 6 = 36 possibilities in this case.2
   If 1 is the highest power of 7 dividing the middle square, there are also 36 possibilities by a similarargument.
   If 7 is the highest power of 7 dividing the middle square, there are 8 possibilities for the upper rightthree squares. Thus there are 64 possibilities in this case.
   Thus there are a total of 136 options for the divisibility of each number by 7 and 7 , and 18 options 2
   for the divisibility of the numbers by 41. Since each number divides 2009, this uniquely determinesthe numbers, and so there are a total of 18 · 136 = 2448 possibilities.