Maths Olympiad Prep

Library / /39 of 86

Number theory Difficulty 5.8 AIME, harder Prove it Estonia

Two positive integers together contain each digit 00, 11, \ldots, 99 exactly once. Find the largest possible common divisor that these two numbers can have.

Solution

Answer: 4865148651.

Suppose that both numbers contain 55 digits. A common divisor of two different numbers cannot exceed half of the larger one; thus the greatest common divisor of two such numbers must be less than 5000050000. It means that if the greatest common divisor has 55 digits then the first digit is at most 44. Let the greatest common divisor be dd and suppose that it has 55 digits, the first of which is 44. Then the two numbers under consideration are dd and 2d2d. If the second digit of dd were 99 then the first two digits of 2d2d would be either 9898 or 9999, but in both cases, 99 would occur in these numbers repeatedly. Thus the second digit of dd is at most 88; suppose that it is 88. Then the first digit of 2d2d is 99. If the third digit of dd were 77 then the second digit of 2d2d would be 77, too. Thus the third digit of dd is at most 66 and the fourth digit of dd is at most 55; suppose that the third and the fourth digit are 66 and 55, respectively. Then the second and the third digit of 2d2d are 77 and 33, respectively, and the fourth digit is 00 as the remaining digits 11 and 22 cannot cause a carry. Finally, 11 and 22 must be the last digits of dd and 2d2d, respectively, yielding d=48651d = 48651 and 2d=973022d = 97302. These numbers satisfy the conditions of the problem.

If the given integers are not 55-digit numbers then the greatest common divisor can have at most 44 digits. Consequently, there cannot be solutions greater than that found in the previous paragraph.

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 and solution reproduced as published; topic and difficulty added by this site.