9. In how many ways can the cells of a $4 \times 4$ table be filled in with the digits $1,2, \ldots, 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 \leq 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 \geq 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 number - which is only possible if all 16 cells contain the same digit. Conversely, for each $d=1, \ldots, 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.