Two positive integers together contain each digit , , , exactly once. Find the largest possible common divisor that these two numbers can have.
Solution
Answer: .
Suppose that both numbers contain 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 . It means that if the greatest common divisor has digits then the first digit is at most . Let the greatest common divisor be and suppose that it has digits, the first of which is . Then the two numbers under consideration are and . If the second digit of were then the first two digits of would be either or , but in both cases, would occur in these numbers repeatedly. Thus the second digit of is at most ; suppose that it is . Then the first digit of is . If the third digit of were then the second digit of would be , too. Thus the third digit of is at most and the fourth digit of is at most ; suppose that the third and the fourth digit are and , respectively. Then the second and the third digit of are and , respectively, and the fourth digit is as the remaining digits and cannot cause a carry. Finally, and must be the last digits of and , respectively, yielding and . These numbers satisfy the conditions of the problem.
If the given integers are not -digit numbers then the greatest common divisor can have at most digits. Consequently, there cannot be solutions greater than that found in the previous paragraph.