Question

An $n$ -digit positive integer is cute if its $n$ digits are an arrangement of the set $\{1,2,\ldots,n\}$ and its first $k$ digits form an integer that is divisible by $k,$ for $k=1,$ $2,$ $\ldots,$ $n.$ For example, $321$ is a cute $3$ -digit integer because $1$ divides $3,$ $2$ divides $32,$ and $3$ divides $321.$ How many cute $6$ -digit integers are there?

$0$

$1$

$2$

$3$

$4$

Answer: C

Concepts:divisibility permutations case analysis

Difficulty rating: 2270

Small Hint:

The second digit must be even, the third-prefix digit sum must be divisible by $3,$ and the fourth prefix must be divisible by $4$

Big Hint:

The fifth digit must be $5,$ and the full number must be even and divisible by $3$

Solution:

Divisibility by $5$ forces the fifth digit to be $5.$ Divisibility by $2$ and $6$ forces the second and sixth digits to be even. Now apply the divisibility tests successively: the first three digits must have sum divisible by $3,$ and the two-digit number formed by the third and fourth digits must be divisible by $4.$ Checking the remaining choices from $\{1,2,3,4,6\}$ leaves $123654$ and $321654.$ Each number directly satisfies all six prefix divisibility conditions, so there are $2.$

Thus the correct answer is C.

1991 AMC 12 Problem 26

Answer: C

Difficulty rating: 2270

Small Hint:

Big Hint:

Solution:

Problem 26 in Other Years