Maths Olympiad Prep

Library / /5 of 10

Algebra Difficulty 8.5 Shortlist Prove it China

Given a positive integer kk, let integers a,ba, b (not both zero) satisfy 0a<k0 \le a < k, 0b<k+10 \le b < k+1. Define the sequence {Tn}nk\{T_n\}_{n \ge k} as follows:
Tk=a,Tk+1=b, T_k = a, \quad T_{k+1} = b,
and for nk+2n \ge k + 2,
TnTn1+Tn2(modn)with0Tn<n. T_n \equiv T_{n-1} + T_{n-2} \pmod{n} \quad \text{with} \quad 0 \le T_n < n.
Concatenating the decimal expansions of Tk,Tk+1,T_k, T_{k+1}, \dots after the decimal point yields an infinite decimal x=0.TkTk+1x = 0.T_kT_{k+1}\dots. For example, if k=66k = 66, a=5a = 5, b=20b = 20, then T66=5T_{66} = 5, T67=20T_{67} = 20, T68=25T_{68} = 25, T69=45T_{69} = 45, T70=0T_{70} = 0, T71=45T_{71} = 45, T72=45T_{72} = 45, T73=17T_{73} = 17, etc., so x=0.52025450454517x = 0.52025450454517\dots.
Prove that xx is irrational.

Solution

Proof: First, we prove that {Tn}n=k\{T_n\}_{n=k}^{\infty} is unbounded. If not, let M=maxnk{Tn}M = \max_{n \ge k}\{T_n\}, then for any n>2Mn > 2M, from Tn1MT_{n-1} \le M and Tn2MT_{n-2} \le M, we have Tn=Tn1+Tn2T_n = T_{n-1} + T_{n-2}. By the boundedness of TnT_n, the only possibility is Tn1=Tn2=0T_{n-1} = T_{n-2} = 0, which inductively leads to Tk+1=Tk=0T_{k+1} = T_k = 0, a contradiction!

Let m0m_0 be the number of digits of kk. We further prove that for any m>m0m > m_0, there exists nn such that 10m1Tn<10m10^{m-1} \le T_n < 10^m. By the unboundedness of TnT_n, there exists a minimal Tn10m1T_n \ge 10^{m-1}, then n>k+1n > k+1 and Tn1,Tn2<10m1T_{n-1}, T_{n-2} < 10^{m-1}, thus TnTn1+Tn2<210m1<10mT_n \le T_{n-1} + T_{n-2} < 2 \cdot 10^{m-1} < 10^m.

For convenience, denote pqp \star q as the number obtained by concatenating positive integer pp with non-negative integer qq. By contradiction, assume 0.TkTk+1=0.a1asb1btb1bt0.T_k \star T_{k+1} \star \dots = 0.a_1 \dots a_s b_1 \dots b_t b_1 \dots b_t \dots (i.e., this repeating decimal has ultimate period length tt), where ai,bj{0,1,,9}a_i, b_j \in \{0, 1, \dots, 9\}. Take nn sufficiently large so that TnT_n appears to the right of asa_s, then for any rnr \ge n, TrTr+1Tr+2T_r \star T_{r+1} \star T_{r+2} \dots is a number with period wtwt, where ww is any positive integer. Take m=νtm = \nu t with ν\nu sufficiently large so that 10m1>Ti10^{m-1} > T_i for all ini \le n, then there exists a minimal \ell such that TT_\ell has exactly mm digits, clearly >n\ell > n.

If T1T_{\ell-1} has more than mm digits, then there must exist j<1j < \ell - 1 where TjT_j has m1m-1 digits, leading to some number before TT_\ell having mm digits, a contradiction!

Clearly kmk \ne m, so k<mk < m. But mm is the period length, thus the last kk digits of T1T_{\ell-1} and TT_\ell must be identical, which implies T2T_{\ell-2} has at least mm digits. Therefore, there exists a number before T1T_{\ell-1} with mm digits, another contradiction!

In conclusion, the assumption by contradiction is invalid, and the original proposition is proved. □

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.