Math Kangaroo 2011, Level 5-6, Problem 30

How many five digit numbers which use the digits 1, 2, 3, 4, and 5, with all different digits, have the following properties when looking at the number from left to right: the first two digits form a number divisible by 2, the first three digits from a number divisible by 3, the first four digits from a number divisible by 4, and the five digits number is divisible by 5?

(A) There are no such numbers    (B) 1    (C) 2    (D) 5    (E) 10

Solution

This problem requires the knowledge of the number divisibility rules. Let's review them before discussing the actual solutions.

A number is divisible by 2 if it's even.

A number is divisible by 3 if the sum of its digits is divisible by 3.

A number is divisible by 4 if a two-digit number formed by its 10's and 1's digits is divisible by 4.

A number is divisible by 5 if it has either 0 or 5 in the 1's place.

Now, the key to quickly finding the right answer is to examine each of the four conditions in the problem in the order opposite to the order in which they are listed. Let's also note that each of the five digits can only be used once in all possible 5-digit numbers.

The 5-digit number is divisible by 5. Then there must be 5 in the 1's place – 0 is not available.

The number formed by the first 4 digits is divisible by 4. Since 5 has been already used, only 1 through 4 are available. The only 2-digit combinations that form numbers divisible by 4 are 12, 24 and 32. Thus the possible 4-digiit combinations are:
34[12]
43[12]
13[24]
31[24]
14[32]
41[32]

The number formed by the first 3 digits is divisible by 3. From the previous step, the only 3-digit combinations available are below with their digit sums calculated.
341 (8) – not divisible by 3
431 (8) – not divisible by 3
132 (6) – divisible by 3
312 (6) – divisible by 3
143 (8) – not divisible by 3
413 (8) – not divisible by 3

The number formed by the first 2 digits is divisible by 2. They only 2-digit combinations we can possibly have at the beginning are 13 and 31. Neither is divisible by 2 since both are odd.

We can conclude that there is not a single 5-digit combination of the digits 1 through 5 where digits don't repeat that satisfies all four divisibility conditions. Therefore, the correct answer is: (A) There are no such numbers.