HMMT 二月 2005 · GEN2 赛 · 第 9 题

HMMT February 2005 — GEN2 Round — Problem 9

In how many ways can the cells of a 4 × 4 table be filled in with the digits 1 , 2 , . . . , 9 so that each of the 4-digit numbers formed by the columns is divisible by each of the 4-digit numbers formed by the rows?

解析

In how many ways can the cells of a 4 × 4 table be filled in with the digits 1 , 2 , . . . , 9 so that each of the 4-digit numbers formed by the columns is divisible by each of the 4-digit numbers formed by the rows? Solution: 9 If a and b are 4-digit numbers with the same first digit, and a divides b , then since b < a + 1000 ≤ 2 a , b must equal a . In particular, since the number formed by the first row of the table divides the number in the first column (and both have the same first digit), these numbers must be equal; call their common value n . Then, for k = 2, 3, or 4, we find that the number in the k th column and the number in the k th row have the same first digit (namely the k th digit of n ), so by the same reasoning, they are equal. Also, the smallest number b formed by any column is divisible by the largest number a formed by any row, but by the symmetry just proven, a is also the largest number formed by any column, so a ≥ b . Since b is divisible by a , we must have equality. Then all columns contain the same number — and hence all rows also contain the same 3 number — which is only possible if all 16 cells contain the same digit. Conversely, for each d = 1 , . . . , 9, filling in all 16 cells with the digit d clearly gives a table meeting the required condition, so we have exactly 9 such tables, one for each digit.