Maths Olympiad Prep

Library / /401 of 462

Number theory Difficulty 7.0 National Olympiad Prove it Ireland

For each integer n100n \ge 100 we define T(n)T(n) to be the number obtained from nn by moving the two leading digits to the end. For example, T(12345)=34512T(12345) = 34512 and T(100)=10T(100) = 10. Find all integers n100n \ge 100 for which:
n+T(n)=10n. n + T(n) = 10n.

Solutions — 2

Solution 1

The general solution is
n=1091×(106k1)=(1+106+1012++106(k1))×109890 n = \frac{10}{91} \times (10^{6k} - 1) = (1 + 10^6 + 10^{12} + \dots + 10^{6(k-1)}) \times 109890
for any positive integer kk. In other words, the number nn consists of kk replicates of the digits 109890.

Let mm be the number of digits of nn so m3m \ge 3 when n100n \ge 100. Dividing nn by 10m210^{m-2}, let qq be the quotient and rr the remainder. This splits the digits of nn into the first two and the remaining digits,
n=10m2q+r n = 10^{m-2}q + r
where 10q9910 \le q \le 99 and 0r<10m20 \le r < 10^{m-2}. Rearranging the digits we have:
T(n)=100r+q. T(n) = 100r + q.
The equation n+T(n)=10nn + T(n) = 10n is equivalent to T(n)=9nT(n) = 9n which we write in terms of qq and rr:
100r+q=9×10m2q+9r 100r + q = 9 \times 10^{m-2}q + 9r
or
91r=(9×10m21)q.(7) 91r = (9 \times 10^{m-2} - 1)q. \qquad (7)

We know that q10q \ge 10. We now claim that q=10q = 10 for any solution. For a contradiction, suppose that q11q \ge 11. Then equation (7) implies that
(9×10m21)×11(9×10m21)q=91r<91×10m2. (9 \times 10^{m-2} - 1) \times 11 \le (9 \times 10^{m-2} - 1)q = 91r < 91 \times 10^{m-2}.
Comparing the left and right end gives (9991)×10m211(99-91) \times 10^{m-2} \le 11, contradicting m3m \ge 3. Therefore q=10q = 10. Substituting q=10q = 10 into equation (7) gives
91r=(9×10m21)×10. 91r = (9 \times 10^{m-2} - 1) \times 10.
As gcd(91,10)=1\gcd(91, 10) = 1 then 91 must divide 9×10m219 \times 10^{m-2} - 1. This is not only necessary but also sufficient, as we can then write:
r=9×10m2191×10<991×10m1<10m2(8) r = \frac{9 \times 10^{m-2} - 1}{91} \times 10 < \frac{9}{91} \times 10^{m-1} < 10^{m-2} \quad (8)
and rr is then an integer that lies in the feasible range.
It remains then to find the values of mm for which 9×10m219 \times 10^{m-2} - 1 is a multiple of 91. Equivalently, we require that (9+91)×10m21=10m1(9 + 91) \times 10^{m-2} - 1 = 10^m - 1, is a multiple of 91. As 91=7×1391 = 7 \times 13 we can use a short cut to check that 10m110^m - 1 is a multiple both of 7 and of 13. Remainders tabulated below:

m10m10^m (mod 7)10m10^m (mod 13)10m10^m (mod 91)
0111
131010
2299
361290
44381
55482
6111

The pattern continues with period 6. Therefore, mm must be a multiple of 6, and, as m3m \ge 3 we have m=6km = 6k for some positive integer kk.
Reconstructing the pieces and using equation (8) we have:
q=10r=9×106k2191×10n=106k2q+r=10×91×106k2+9×106k2191=10×106k191. \begin{align*} q &= 10 & r &= \frac{9 \times 10^{6k-2} - 1}{91} \times 10 \\ n &= 10^{6k-2}q + r = 10 \times \frac{91 \times 10^{6k-2} + 9 \times 10^{6k-2} - 1}{91} = 10 \times \frac{10^{6k} - 1}{91}. \end{align*}
We can write the digits explicitly, noting that:
10×106k191=10×(1061)91(1+106+1012++106(k1)). 10 \times \frac{10^{6k} - 1}{91} = \frac{10 \times (10^6 - 1)}{91} (1 + 10^6 + 10^{12} + \dots + 10^{6(k-1)}).
As 10×(1061)/91=98901010 \times (10^6 - 1)/91 = 989010 the stated representation follows.

Solution 2

The equation n+T(n)=10nn + T(n) = 10n could also be written as T(n)=9nT(n) = 9n.
As nn and T(n)T(n) have the same number of digits, the leading digit of nn must be equal to 1 and the leading digit of T(n)=9nT(n) = 9n, which is the third digit from the left of nn, has then to be equal to 9. This implies that there occurs a carry from the third to the second place from the left, hence the second digit of nn must be zero. The shapes of nn and T(n)T(n) are therefore
n=109T(n)=910 n = 109 **\ldots** * \qquad T(n) = 9 **\ldots** * 10
where each star stands for a digit and the dots indicate that the number of digits of nn is currently unknown. We can now work our way backwards from T(n)=9nT(n) = 9n to nn, starting at the end. The key feature we are using here is that 9kk10k(mod10)9k \equiv -k \equiv 10 - k \pmod{10}.
Let the rightmost unknown digit be equal to dd so that we have
n=109d9n=T(n)=9d10 n = 109 **\ldots** * d \qquad 9n = T(n) = 9 **\ldots** * d10
then 9d0(mod10)9d \equiv 0 \pmod{10}, hence d=0d = 0. This gives us
n=10909n=T(n)=9010 n = 109 **\ldots** * 0 \qquad 9n = T(n) = 9 **\ldots** * 010
We will again call the rightmost unknown digit dd so that we have
n=109d09n=T(n)=9d010 n = 109 **\ldots** * d0 \qquad 9n = T(n) = 9 **\ldots** * d010
and 9d1(mod10)9d \equiv 1 \pmod{10}, hence d=9d = 9. We now need to check if this digit could already be the third digit from the left, i.e. n=1090n = 1090. But 10909=9810T(1090)1090 \cdot 9 = 9810 \neq T(1090). This gives us, with new dd,
n=109d909n=T(n)=9d9010 n = 109 **\ldots** * d90 \qquad 9n = T(n) = 9 **\ldots** * d9010
and, keeping the carry in mind, 9d+80(mod10)9d + 8 \equiv 0 \pmod{10}. Therefore, d=8d = 8 and
n=109d8909n=T(n)=9d89010 n = 109 **\ldots** * d890 \qquad 9n = T(n) = 9 **\ldots** * d89010
with 9d+89(mod10)9d + 8 \equiv 9 \pmod{10}, which implies d=9d = 9. We have to check again if this digit could already be the third digit from the left, i.e. n=109890n = 109890. Indeed, we now have 9n=9109890=989010=T(n)9n = 9 \cdot 109890 = 989010 = T(n).
So far we have shown that 109890109890 is one solution and that the last six digits of T(n)T(n) for any solution nn need to be 989010989010. This implies that the last six digits of any solution nn are equal to 989010/9=109890989010/9 = 109890.
We could now continue in the manner above to see that this sequence of digits must repeat if nn has more than six digits. Alternatively, we could argue as follows.

Let mm be the number obtained from nn by removing the last six digits. We show that T(m)=9mT(m) = 9m. Clearly, T(m)T(m) agrees, except possible at the last two digits, with the number T(n)T'(n) obtained from T(n)T(n) by removing the last six digits. As we have seen above, the two leading digits of nn, and so also of mm, are 10. As the last six digits of nn are 109890, the last two digits of T(n)T'(n) are 10. Hence, T(n)=T(m)T'(n) = T(m). Using T(n)=9nT(n) = 9n it follows now that T(m)=9mT(m) = 9m. It follows by induction that nn has 6k6k digits (k1k \ge 1) and consists of kk consecutive blocks of six digits, all equal to 109890.

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.