1991 AMC 12 Problem 26

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

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

The fifth digit must be

5,

and the full number must be even and divisible by

3

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.

Problem 26 in other years