Maths Olympiad Prep

Library / /8 of 24

Number theory Difficulty 6.0 National olympiad Prove it Argentina

For every positive integer mm, we write S(m)S(m) for the sum of its digits. For example, S(2018)=2+0+1+8=11S(2018) = 2+0+1+8=11.
We say a positive integer nn is rioplatense if there is a positive integer mm such that m+2S(m)=nm + 2S(m) = n.
Find all positive integers that are rioplatenses.

Solution

For every positive integer mm, we know that mm and S(m)S(m) have the same remainder rr modulo 33. Then, m+2S(m)m + 2S(m) has the same remainder as 3r3r and so, it is a multiple of 33. Therefore, if a number nn is rioplatense, then it is a multiple of 33.

Now we are going to show that every multiple of 33 is rioplatense. We will prove by induction on kk that every integer nn divisible by 33 with at most kk digits can be written as n=m+2S(m)n = m + 2S(m) for an integer mm with at most kk digits.

For k=1k=1, the result is immediate, since 3=1+2S(1)3 = 1 + 2S(1), 6=2+2S(2)6 = 2 + 2S(2) and 9=3+2S(3)9 = 3 + 2S(3). Assume the result holds for k1k \ge 1 and consider an integer nn multiple of 33 with k+1k+1 digits. We have 10k+2n<10k+110^k + 2 \le n < 10^{k+1}, since 10k+2=100210^k + 2 = 10\cdots02 is the smallest multiple of 33 with k+1k+1 digits. Let us call N=10k+2N = 10^k + 2. When dividing nn by NN, we obtain a quotient qq and a remainder rr. Note that 1q91 \le q \le 9, since n<10k+1<10Nn < 10^{k+1} < 10N. On the other hand, r<10k+2r < 10^k + 2 and it is a multiple of 33, since r=nNqr = n - Nq and both nn and NN are multiples of 33, which implies that r10k1r \le 10^k - 1 and so, it has at most kk digits. By the induction assumption, there exists t=ak1a1a0t = \overline{a_{k-1} \cdots a_1 a_0} such that r=t+2S(t)r = t + 2S(t).

Take m=akak1a1a0m = \overline{a_k a_{k-1} \cdots a_1 a_0}, where aka_k is the quotient qq. Note that mm has k+1k+1 digits and
m+2S(m)=akak1a1a0+2(ak+ak1++a1+a0)==10kak+ak1a1a0+2ak+2(ak1++a1+a0)==(10k+2)ak+t+2S(t)=Nq+r=n, \begin{align*} m + 2S(m) &= \overline{a_k a_{k-1} \cdots a_1 a_0} + 2(a_k + a_{k-1} + \cdots + a_1 + a_0) = \\ &= 10^k a_k + \overline{a_{k-1} \cdots a_1 a_0} + 2a_k + 2(a_{k-1} + \cdots + a_1 + a_0) = \\ &= (10^k + 2)a_k + t + 2S(t) = Nq + r = n, \end{align*}
as desired.

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.