Olympiad Maths Prep

Track / Stage 8 / 69 of 180 #1769 of 2000

Problem 1769

IMO Shortlist mid-range; USAMO P2/P5
Number theory Difficulty 8.2 Prove it

81438 \cdot 143 The infinite sequence xnx_{n} is defined by the following rule:
xn+1=112xn, and 0x11x_{n+1}=|1-| 1-2 x_{n}|| \text {, and } 0 \leqslant x_{1} \leqslant 1 \text {. }
(1) Prove: The sequence becomes periodic from some term onwards if and only if x1x_{1} is a rational number.
(2) How many different values of x1x_{1} exist such that the sequence becomes periodic with period TT from some term onwards (for each T=2,3,T=2,3, \cdots)?

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

[Solution](1) From the given, we have
xn+1={2xn, if 0xn<1222xn, if 12xn1x_{n+1}=\left\{\begin{array}{l} 2 x_{n}, \text { if } 0 \leqslant x_{n}<\frac{1}{2} \\ 2-2 x_{n}, \text { if } \frac{1}{2} \leqslant x_{n} \leqslant 1 \end{array}\right.

If x1x_{1} is a rational number, we can set x1=pq,(p,q)=1,pN,qNx_{1}=\frac{p}{q},(p, q)=1, p \in N, q \in N. Note that for all nn, it is clear that 0xn10 \leqslant x_{n} \leqslant 1, and xn=pnq,pn{0,1,,q}x_{n}=\frac{p_{n}}{q}, p_{n} \in\{0,1, \cdots, q\}. Therefore, there must exist n1,n2n_{1}, n_{2} and n1<n2n_{1}<n_{2}, such that
pn1=pn2p_{n_{1}}=p_{n_{2}}

Thus, we have xn1=xn2\quad x_{n_{1}}=x_{n_{2}}.
Therefore, from (1), we can see that {xn}\left\{x_{n}\right\} is periodic after the n1n_{1}-th term.
Conversely, if the sequence is periodic after the n1n_{1}-th term, and the period is TT. We represent xn1x_{n_{1}} in binary, denoted as
xn1=k=1ak2k, where ak{0,1}x_{n_{1}}=\sum_{k=1}^{\infty} a_{k} \cdot 2^{-k} \text {, where } a_{k} \in\{0,1\} \text {. }

We also denote
aˉk=1ak,kN\bar{a}_{k}=1-a_{k}, k \in N

Thus, from (1), we get
xn1+1={k=1ak+12k, if a1=0k=1ak+12k, if a1=1.xn1+2={k=1ak+22k, if a1+a20(mod2)k=1ak+22k, if a1+a21(mod2)\begin{array}{l} x_{n_{1}+1}=\left\{\begin{array}{l} \sum_{k=1}^{\infty} a_{k+1} \cdot 2^{-k}, \text { if } a_{1}=0 ; \\ \sum_{k=1}^{\infty} \overline{a_{k+1}} \cdot 2^{-k}, \text { if } a_{1}=1 . \end{array}\right. \\ x_{n_{1}+2}=\left\{\begin{array}{l} \sum_{k=1}^{\infty} a_{k+2} \cdot 2^{-k}, \text { if } a_{1}+a_{2} \equiv 0(\bmod 2) ; \\ \sum_{k=1}^{\infty}-a_{k+2} \cdot 2^{-k}, \text { if } a_{1}+a_{2} \equiv 1(\bmod 2) , \end{array}\right. \end{array}

By mathematical induction, it is easy to get
xn1+T={k=1ak+T2k, if a1+a2++aT0(mod2);k=1aˉk+T2k, if a1+a2++aT1(mod2)x_{n_{1}+T}=\left\{\begin{array}{l} \sum_{k=1}^{\infty} a_{k+T} \cdot 2^{-k}, \text { if } a_{1}+a_{2}+\cdots+a_{T} \equiv 0(\bmod 2) ; \\ \sum_{k=1}^{\infty} \bar{a}_{k+T} \cdot 2^{-k}, \text { if } a_{1}+a_{2}+\cdots+a_{T} \equiv 1(\bmod 2) \end{array}\right.

Since xn1+T=xn1\quad x_{n_{1}+T}=x_{n_{1}},
Therefore, when a1+a2++aT0(mod2)a_{1}+a_{2}+\cdots+a_{T} \equiv 0(\bmod 2), we immediately get ak=ak+Ta_{k}=a_{k+T}, kNk \in N,
Thus, it shows that xn1x_{n_{1}} is a binary repeating decimal, hence it is a rational number.
When a1+a2++aT1(mod2)a_{1}+a_{2}+\cdots+a_{T} \equiv 1(\bmod 2), from
xn1+T=xn1x_{n_{1}+T}=x_{n_{1}}

We get {ak=ak+T=1ak+T,kN,ak+T=ak+2T=1ak+2T,kN.\left\{\begin{array}{ll}a_{k}=\vec{a}_{k+T}=1-a_{k+T}, & k \in N, \\ a_{k+T}=\vec{a}_{k+2 T}=1-a_{k+2 T}, & k \in N .\end{array}\right.
Thus, we have
ak=1ak+T=1(1ak+2T)=ak+2T,kNa_{k}=1-a_{k+T}=1-\left(1-a_{k+2 T}\right)=a_{k+2 T}, k \in N

Therefore, xn1x_{n_{1}} is also a rational number.
From (1), we know that xn1x_{n_{1}} is derived from x1x_{1} through n11n_{1}-1 rational operations, so x1x_{1} must also be a rational number.
(2) If we take
x1=(0.1˙100˙)2,x1=(0.1˙10m1)2x_{1}=(0 . \dot{1} 10 \dot{0})_{2}, x_{1}=(0 . \underbrace{\dot{1} \cdots 10}_{m-1 \uparrow})_{2} \text {, }

Then, the corresponding {xn}\left\{x_{n}\right\} are periodic with T=2T=2 and T=m,m3T=m, m \geqslant 3, respectively.
If x1x_{1} is equal to 12k,kN\frac{1}{2^{k}}, k \in N of the values of x1x_{1} in (2), then the period TT of the corresponding sequence {xn}\left\{x_{n}\right\} after a certain term remains unchanged. Therefore, for each T=2,3,T=2,3, \cdots, there are infinitely many x1x_{1} such that the sequence {xn}\left\{x_{n}\right\} is periodic with TT after a certain term.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.