Maths Olympiad Prep

Track / Stage 7 / 80 of 300 #1960 of 2444

Problem 1960

National Olympiad second round; IMO P1/P4
Algebra Difficulty 7.3 Prove it Estonian Mathematical Olympiad · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.