HMMT 二月 2009 · COMB 赛 · 第 9 题
HMMT February 2009 — COMB Round — Problem 9
题目详情
- [ 7 ] The squares of a 3 × 3 grid are filled with positive integers such that 1 is the label of the upper- leftmost square, 2009 is the label of the lower-rightmost square, and the label of each square divides the one directly to the right of it and the one directly below it. How many such labelings are possible?
解析
- [ 5 ] The squares of a 3 × 3 grid are filled with positive integers such that 1 is the label of the upper- leftmost square, 2009 is the label of the lower-rightmost square, and the label of each square divides the one directly to the right of it and the one directly below it. How many such labelings are possible? Answer: 2448 2 Solution: We factor 2009 as 7 · 41 and place the 41’s and the 7’s in the squares separately. The number of ways to fill the grid with 1’s and 41’s so that the divisibility property is satisfied is equal to the 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 are i ( ) 3+4 − 1 − 2 = 18 ways to choose which squares are divisible by 41. 3 To count the arrangements of divisibility by 7 and 49, we consider three cases. 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, for 2 the two blank squares on the left column, for a total of 6 = 36 possibilities in this case. If 1 is the highest power of 7 dividing the middle square, there are also 36 possibilities by a similar argument. If 7 is the highest power of 7 dividing the middle square, there are 8 possibilities for the upper right three squares. Thus there are 64 possibilities in this case. 2 Thus there are a total of 136 options for the divisibility of each number by 7 and 7 , and 18 options for the divisibility of the numbers by 41. Since each number divides 2009, this uniquely determines the numbers, and so there are a total of 18 · 136 = 2448 possibilities.