Maths Olympiad Prep

Library / /244 of 299

Number theory Difficulty 7.2 National Olympiad, round 2 Prove it Iran

Arman starts with a number and calculates the sum of the cubes of its digits. He then repeats this procedure with the resulting number, and continues this procedure. Arman considers a number to be 'good' if, after a certain number of steps, it reaches 11. Prove that there exists an arithmetic progression of length 14021402 consisting of good numbers.

Solutions — 2

Solution 1

We define T(n)T(n) to be the sum of the cubes of digits of nn.

In this solution first we give an example of an arithmetic progression of length 14021402 such that all the numbers have the same non-zero digits with the same amount of recurrence. Then we will have an arithmetic progression of a1,,a1402a_1, \dots, a_{1402} such that T(a1)==T(a1402)T(a_1) = \dots = T(a_{1402}).

By adding some amount of ones on the left sides of these numbers we can keep them as an arithmetic progression and additionally convert all of them to a good number.

Now let's find the promised progression. Let A=10φ(7m)17mA = \frac{10^{\varphi(7^m)} - 1}{7^m} for an m>10m > 10. We claim that A,8A,15A,,(1402×7+1)AA, 8A, 15A, \dots, (1402 \times 7 + 1)A all have the same digits with the same number of recurrence. We shall use a lemma here:

Lemma 1. 1010 is a primitive root for every power of 77.

Proof. It is enough to see that 1010 is a primitive root modulo 77 and 727^2.

Lemma 2. For every 1a7m1 \le a \le 7^m, gcd(a,7)=1\text{gcd}(a, 7) = 1, aAaA represents the repeating part in the decimal representation of a7m\frac{a}{7^m}. Furthermore it is a cyclic permutation of the digits in AA.

Proof. Let a7m=0.a1as\frac{a}{7^m} = 0.\overline{a_1\cdots a_s}. We have:
a1as=a×10s17m \overline{a_1 \cdots a_s} = a \times \frac{10^s - 1}{7^m}
As the left hand side is an integer, 7m(10s1)a7^m \mid (10^s - 1)a. Knowing gcd(a,7)=1\text{gcd}(a, 7) = 1 and by Lemma 1 we have s=φ(7m)s = \varphi(7^m).
a1as=a×10φ(7m)17m=aA \overline{a_1 \cdots a_s} = a \times \frac{10^{\varphi(7^m)} - 1}{7^m} = aA
As 1010 is a primitive root modulo 7m7^m there exists α\alpha such that:
a10α(mod7m)    10α7ma7mZ a \equiv 10^{\alpha} \pmod{7^m} \implies \frac{10^{\alpha}}{7^m} - \frac{a}{7^m} \in \mathbb{Z}
a7m\frac{a}{7^m} is less than 11 resulting in a7n={10α7n}\frac{a}{7^n} = \{\frac{10^\alpha}{7^n}\}. However the repeating decimal of {10α7n}\{\frac{10^\alpha}{7^n}\} is a cyclic permutation of the repeating decimal of 17n\frac{1}{7^n} which is AA (that is a special case of the first part where a=1a = 1).

Solution 2

Let n=j=0kaj10jn = \sum_{j=0}^{k} a_j 10^j, T(n)=j=0kaj3T(n) = \sum_{j=0}^{k} a_j^3. Then, T(n)=n(mod3)T(n) = n \pmod{3}. So, nn is good only if n=1(mod3)n = 1 \pmod{3}. We prove that there would be an arithmetic progression of common difference of 33 of arbitrary length. Let T0(x)=xT^0(x) = x, Tm(x)=T(Tm1(x))T^m(x) = T(T^{m-1}(x)). If Tm(y)=xT^m(y) = x and xx is good then yy is good.

Lemma 1. Let x,y,tx, y, t be positive integers and 10t>y10^t > y. Then T(10tx+y)=T(x)+T(y)T(10^t x + y) = T(x) + T(y).

Proof. Obvious.

Lemma 2. For any a1,,ana_1, \dots, a_n and r,yr, y there are an integer YY such that Tr(Y+ai)=y+Tr(ai), i=1,,nT^r(Y + a_i) = y + T^r(a_i), \ i = 1, \dots, n.

Proof. Tr(10tlr+ai)=Tr1(T(10tlr+ai))=Tr1(10tlr1+T(ai))=Tr2(T(10tlr1+T(ai)))=Tr2(10tlr2+T2(ai))=y+Tr(ai)T^r(10^t l_r + a_i) = T^{r-1}(T(10^t l_r + a_i)) = T^{r-1}(10^t l_{r-1} + T(a_i)) = T^{r-2}(T(10^t l_{r-1} + T(a_i))) = T^{r-2}(10^t l_{r-2} + T^2(a_i)) = y + T^r(a_i).

Since T(n)=(9)klog10aT(n) = (9)^k \log_{10} a we find that for all a>Ma > M we have T(a)<aT(a) < a. So, if we apply the function TT repeatedly to aa we eventually reach a cycle with finite length or arrive at 11. The number of cycles of TT is finite.

Claim 1. *There exists a finite set BB such that*

i For any positive integer nn, Tr(n)BT^r(n) \in B for some r=0r = 0.
ii For any dBd \in B, Tl(d)=dT^l(d) = d for some integer l=0l = 0.

Choose the subset D={xB:x=1(mod3)}D = \{x \in B : x = 1 \pmod 3\}. Since for any integer nn, T(n)=n(mod3)T(n) = n \pmod 3 we see that n=1(mod3)n = 1 \pmod 3 if and only if Tr(n)DT^r(n) \in D, for some r=0r = 0.

If for dDd \in D there is a positive integer yy such that y+1,y+dy + 1, y + d both are good numbers, then there exists a sequence {l,l+3,,l+3(m1)}\{l, l + 3, \dots, l + 3(m - 1)\} of good numbers of any length mm. Let D={1,d1,,dk}D = \{1, d_1, \dots, d_k\}. We prove it by induction on mm. Assume m=2m = 2 then there exists an rr such that Tr(4)DT^r(4) \in D thus Tr(4)=1T^r(4) = 1 or did_i for some 1=k=k1 = k = k. By our assumption, there exists yiy_i such that both yi+1y_i + 1 and yi+diy_i+d_i are good numbers. According to above lemma, there is YY such that Tr(Y+1)=yi+Tr(1)=yi+1T^r(Y+1) = y_i+T^r(1) = y_i+1 and Tr(Y+4)=yi+Tr(4)=yi+diT^r(Y+4) = y_i+T^r(4) = y_i+d_i or yi+1y_i+1. Let l=Y+1l = Y+1 then both l,l+Pl, l+P are good.

Now, assume that the statement holds for m=u1m = u - 1 that is, there is an ll' such that l,l+3,,l+3(u2)l', l' + 3, \dots, l' + 3(u - 2) are all good. We consider two cases. If l+3(u1)l' + 3(u - 1) is happy take l=ll = l' and we are done. If l+3(u1)l' + 3(u - 1) is good then since l+3(u1)l1(mod3)l' + 3(u - 1) \equiv l' \equiv 1 \pmod 3. Thus, there exists rr such that
Tr(l+3(u1))=dj, T^r(l' + 3(u-1)) = d_j,
for some 1jk1 \le j \le k. According to the properties of DD there exists a positive integer vv such that
Tr+v(l+3(u1))=Tr(l+3(u1))=dj. T^{r+v}(l' + 3(u-1)) = T^r(l' + 3(u-1)) = d_j.
Meanwhile, there exists an RR such that TR(l+3(i1))=1T^R(l' + 3(i - 1)) = 1.

For any 1iu11 \le i \le u - 1, since l,,l+3(u2)l', \dots, l' + 3(u - 2) are all happy. Let Kr(modv)K \equiv r \pmod v) satisfy K>RK > R. Then, by above lemma, there is a positive integer YY such that
TK(Y+l+3(i1))=yj+TK(l+3(i1))=yj+1,(1iu1), T^K(Y + l' + 3(i - 1)) = y_j + T^K(l' + 3(i - 1)) = y_j + 1, \quad (1 \le i \le u - 1),
moreover,
TK(Y+l+3(u1))=yj+TK(l+3(u1))=yj+dj,(1iu1). T^K(Y + l' + 3(u-1)) = y_j + T^K(l' + 3(u-1)) = y_j + d_j, \quad (1 \le i \le u-1).
That is to say, Y+l+3(i1)Y + l' + 3(i - 1), (1iu1 \le i \le u) are all good. Taking l=Y+ll = Y + l' then l,,l+3(u1)l, \dots, l + 3(u - 1) are all happy. We are done.

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.