Maths Olympiad Prep

Library / /7 of 25

Number theory Difficulty 3.9 AMC 10/12 Prove it Japan

Both mm and nn are 3-digit positive integers, and mm and nn differ only in one of the 3 digits. Also, nn is an integral multiple of mm. How many possible such pairs (m,n)(m, n) are there?

Solution

From mnm \neq n and the fact that nn is a multiple of mm, it follows that n2mn \geq 2m. Since mm is an integer greater than or equal to 100100, we have nmm100n - m \geq m \geq 100, and therefore, we see that nn and mm differ on the hundred's digit. This means that there exists an integer kk (1k81 \leq k \leq 8) for which nm=100kn - m = 100k. Since mm divides nn, we see that mm divides nm=100kn - m = 100k. Also, from 2mn9992m \leq n \leq 999 it follows that m499m \leq 499. From these considerations we conclude that mm must be one of the following:

100100, 120120, 125125, 140140, 150150, 160160, 175175, 200200, 250250, 300300, 350350, 400400.

Values of nn matching these values of mm can be chosen for 88, 11, 11, 11, 22, 11, 11, 33, 11, 22, 00, 11 different ways, respectively. Hence the total number of ways the pair (m,n)(m, n) can be chosen to satisfy the conditions of the problem is 2222.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.