2017 AMC 10 A

Let the threedigit number be :

If a number is divisible by , then the difference between the sums of alternating digits is a multiple of .

There are two cases: and We now proceed to break down the cases. Note: let so that we avoid counting the same permutations and having to subtract them later.

Case : .

Part : , , this case results in , , . There are two ways to arrange the digits in each of those numbers. .

Part : , , this case results in , , . There are ways to arrange the digits in all of those number except the first, and ways for the first. This leads to cases.

Part : , , this case results in , , . There are ways to arrange the digits in all of those number except the first, and ways for the first. This leads to cases.

Part : , , this case results in , , . There are ways to arrange the digits in all of those number except the first, and ways for the first. This leads to cases.

Part : , , this case results in and . There are ways to arrange the digits in and ways for . This leads to cases. This case has subcases.

Case : .

Part : , , this cases results in , , , . There are ways to arrange each of those cases. This leads to cases.

Part : , , this cases results in , , ,. There are ways to arrange each of those cases, except the last. This leads to cases.

Part : , , this cases results in , , . There are ways to arrange each of those cases. This leads to cases.

If we continue this counting, we receive subcases. .

We note that we only have to consider multiples of and see how many valid permutations each has. We can do casework on the number of repeating digits that the multiple of has:

Case : All three digits are the same. By inspection, we find that there are no multiples of here.

Case : Two of the digits are the same, and the third is different.

Case : There are multiples of without a zero that have this property: , , , , , , , . Each contributes valid permutations, so there are permutations in this subcase.

Case : There are multiples of with a zero that have this property: , , , , , , , , . Each one contributes valid permutations (the first digit can't be zero) so there are permutations in this subcase.

Case : All the digits are different Since there are multiples of between and , there are multiples of remaining in this case. However, of them contain a zero, namely , , , , , , , and . Each of those multiples of contributes valid permutations, but we overcounted by a factor of ; every permutation of , for example, is also a permutation of . Therefore, there are . Therefore, there are remaining multiples of without a in this case. Each one contributes valid permutations, but once again, we overcounted by a factor of (note that if a number is a muliple of , then so is ). Therefore, there are valid permutations in this subcase. Adding up all the permutations from all the cases, we have .

We can overcount and then subtract. We know there are multiples of .

We can multiply by for each permutation of these mutiples. (Yet some multiples don't have ) Now divide by , because if a number with digits , , and is a multiple of , then cba is also a multiple of so we have counted the same permutations twice.

Basically, each multiple of has its own permutations (say has and whereas has and ). We know that each multiple of has at least permutations because it cannot have repeating digits.

Hence we have permutations without subtracting for overcounting. Now note that we overcounted cases in which we have at the start of each number. So, in theory, we could just answer and move on.

If we want to solve it, then we continue.

We overcounted cases where the middle digit of the number is and the last digit is . Note that we assigned each multiple of permutations.

The last digit is gives possibilties where we overcounted by permutation for each of , , , .

The middle digit is gives possibilities where we overcount by . , , , and , , , subtracting gives .

Now, we may ask if there is further overlap (l.e if two of and and were multiples of ). Thankfully, using divisibility rules, this can never happen as taking the divisibility rule mod and adding we get that , , or is congruent to . Since , , are digits, this can never happen as none of them can equal and they can't equal as they are the leading digit of a digit number in each of the cases.

As said in solution , each number only has at most permutations. There are multiples of , so the answer is at most or . But we know that we overcounted, so the answer is less than , leaving our only choice as