Maths Olympiad Prep

Library / /6 of 8

, 2018

Number theory Difficulty 8.5 Shortlist Prove it Saudi Arabia

Two positive integers mm and nn are called similar if one of them can be obtained from the other one by swapping two digits (note that a 0-digit cannot be swapped with the leading digit). Find the greatest integer NN such that NN is divisible by 13 and any number similar to NN is not divisible by 13.

Solution

Let kk be the number of digits of NN and let N=i=0k110idiN = \sum_{i=0}^{k-1} 10^{i} \cdot d_{i} where did_{i} are digits. If MM is obtained by swapping the ii-th and the jj-th digits, then
MN=(10j10i)(didj). M - N = (10^{j} - 10^{i}) \cdot (d_{i} - d_{j}) .
Therefore 13MN13 \mid M - N implies that di=djd_{i} = d_{j} or 6ij6 \mid i - j. Hence, a number NN satisfies the property given in the problem if and only if 13N13 \mid N, didjd_{i} \neq d_{j} for all iji \neq j and no swap between ii-th and jj-th digits are possible if 6ij6 \mid i - j.

- If k8k \geq 8, one can swap the 0th and the 6th digits, hence NN does not satisfy the property.
- If k=7k = 7, one can swap the 0th and the 6th digits unless the 0th digit is 0, but if the 0th digit is 0, then no swap is possible.

Hence, NN satisfies the property if and only if 13N13 \mid N, all the digits are distinct and the 0th digit is 0. Therefore, N9876540N \leq 9876540.

Considering all multiples of 13 that end with 0 below this level, one finds N{9876490,9876360,9876230,}N \in \{9876490, 9876360, 9876230, \ldots\}. Since the two greatest elements of this set do not have all distinct digits, the greatest integer N=9876230N = 9876230.

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.