2017 AMC 10A Problem 25

Below is the professionally curated solution for Problem 25 of the 2017 AMC 10A, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2017 AMC 10A solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:divisibilitydigitspermutationscasework

Difficulty rating: 2380

25.

How many integers between 100100 and 999,999, inclusive, have the property that some permutation of its digits is a multiple of 1111 between 100100 and 999?999? For example, both 121121 and 211211 have this property.

226226

243243

270270

469469

486486

Solution:

We can analyze all the multiples of 1111 and see how many permutations each of them contribute. We can do this by casing on the number of unique digits in the number.

Case 1:1: all the digits are the same

This cannot happen. We can see this by the divisibility rule for 11,11, which says that the sum of the first and last digit minus the middle digit must be divisible by 11.11.

If all the digits are the same, then the above expression evaluates to that digit, which cannot be divisible by 11.11.

Case 2:2: two of the digits are the same

We can split this up into the numbers that have the digit 00 and those that don't.

There are 88 multiples of 1111 that do not have the digit 0:0: 121,242,363,484,616,737,858, 121, 242, 363, 484, 616, 737, 858, and 979.979.

Each of these numbers contributes 33 permutations, so this scenario has 83=248 \cdot 3 = 24 numbers.

There are 99 multiples of 1111 that have the digit 0:0:110,220,330,440,550,660,770, 110, 220, 330, 440, 550, 660, 770, 880,880, and 990.990.

For these numbers, 00 cannot be the hundreds digit, so each of them only contributes 22 permutations, for a total of 92=18.9 \cdot 2 = 18.

Case 3:3: all the digits are different

There are a total of 8181 multiples of 1111 between 100100 and 999.999. The number of these with all different digits is 8189=64. 81 - 8 - 9 = 64. As in case 2,2, we have to specially account for the numbers with 00 as a digit. There are 8:8: 209,308,407,506,605,704,803, 209, 308, 407, 506, 605, 704, 803, and 902.902.

Each of these gives us 22=42 \cdot 2 = 4 permutations, but we overcount by a factor of 22 since flipping the first and last digits creates another number already in the set.

Therefore, these numbers provide a total of 84÷2=16 8 \cdot 4 \div 2 = 16 unique permutations.

There are now 648=5664 - 8 = 56 multiples of 1111 that we need to account for.

We know that each of these provides 3!=63! = 6 permutations. As above, however, note that flipping the first and last digit of any number in this set produces another number in this set.

We can see this by using the divisibility rule for 11.11. If ABCABC is divisible by 11,11, then we have that A+CBA + C - B is divisible by 11.11.

This means that C+ABC + A - B is divisible by 11,11, which means that CBACBA is also divisible by 11.11.

Therefore, these numbers contribute 566÷2=168 56 \cdot 6 \div 2 = 168 more permutations.

Over all the cases, we have a total of 24+18+16+168=226 24 + 18 + 16 + 168 = 226 numbers.

Thus, A is the correct answer.

Problem 25 in Other Years