Maths Olympiad Prep

Library / /87 of 101

Algebra Difficulty 7.3 National olympiad, round 2 Prove it Estonia

Call a natural number twistable if it does not contain digits 33, 44, 77 and its last digit is not zero. The twisting of a twistable number is the number obtained after the following two steps:
* Reverse the order of digits of the given number;
* Twist each digit: 00, 11 and 88 remain unchanged, 22 and 55 are turned into each other, 66 and 99 are turned into each other.

For instance, the twisting of the number 6801268012 is 5108951089 and the twisting of the number 6969 is 6969.

Find all integers that can be represented as the ratio of a twistable positive integer nn and its twisting kk.

Solution

Since the numbers nn and kk are positive integers of the same length, the quotient nk\frac{n}{k} must be a single-digit positive number, because multiplying by a multi-digit number increases the number of digits. The quotient 11 is obviously possible (e.g. 6969=1\frac{69}{69} = 1). We show that no other quotient is possible.

* If the first digit of the number kk is 11, then the last digit of the number nn is 11. The quotient nk\frac{n}{k} cannot be 22, 44, 55, 66, or 88, because the multiples of these numbers cannot end with the digit 11. If the quotient nk\frac{n}{k} were 33 or 77, then the last digit of kk should be 77 or 33, respectively. However, these digits cannot occur in a twisting. If the quotient nk\frac{n}{k} were 99, then the last digit of the number kk should be 99 and the first digit of the number nn should therefore be 66. However, since n=9kn = 9k, the number nn can only start with the digit 99. Therefore, the only possibility is nk=1\frac{n}{k} = 1.

* If the first digit of the number kk is 22, then the last digit of the number nn is 55. The quotient nk\frac{n}{k} cannot be 55, 66, 77, 88, or 99, because in these cases the number nn would have more digits than the number kk. The quotient nk\frac{n}{k} cannot be 22 or 44, because the multiples of these numbers cannot end with the digit 55. If the quotient nk\frac{n}{k} were 33, then the last digit of the number kk should also be 55 and the first digit of the number nn should therefore be 22. However, since n=3kn = 3k, the number nn can only start with the digits 66, 77, and 88. So again, the only possibility is nk=1\frac{n}{k} = 1.

* The first digit of the number kk cannot be 33 or 44, because these numbers do not occur in a twisting.

* If the first digit of the number kk is 55, 66, 77, 88, or 99, then nk2\frac{n}{k} \ge 2 is not possible, because then there would be more digits in the number nn than in the number kk. Thus, the only possibility is nk=1\frac{n}{k} = 1.

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.