Olympiad Maths Prep

Library / /28 of 60

Number theory Difficulty 5.8 AIME, harder Prove it Ukraine

Determine the greatest positive integer that has pairwise distinct digits and is divisible by each of its digits.

Solution

Clearly, 00 is not one of the digits. In order to be divisible by 55 last digit has to be 55, but the number will not be divisible by 22, 44, 66 and 88, so it will consist of more digits if 55 is not one of them. But then if all other digits are present, it is not divisible by 33, 66 and 99. Therefore, one more digit has to be taken from the number in order for it to be divisible by 33. If so, the following cases are possible:

Case 1. If either 11 or 77 are taken, then number is divisible by 33 and 66, but not by 99, thus digit 99 is not present and the number has 66 digits;

Case 2. If 44 is taken, then it is possible to arrange digits that are left so that each digit divides the number, so the number has 77 digits (all except 00, 44 and 55).

Therefore, the number has 77 digits: 11, 22, 33, 66, 77, 88, 99. Our goal is to make it the largest possible.

If the number starts with 987987, then digits 11, 22, 33, 66 can make numbers divisible by 88, those are 63126312, 16321632, 21362136 to 32163216. But then any of the numbers is not divisible by 77.
If the number starts with 32163216, then digits 11, 22, 33 form a number 312312 that is divisible by 88.
Moreover, 98673129867312 is divisible by 77, therefore, it is the largest number that satisfies given conditions.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.