Maths Olympiad Prep

Library / /15 of 30

Algebra Difficulty 8.3 Shortlist Prove it Germany

Problem:

Determine all positive integers mm with the following property:
The sequence a0,a1,a2,a_{0}, a_{1}, a_{2}, \ldots with a0=2m+12a_{0}=\frac{2m+1}{2} and ak+1=akaka_{k+1}=a_{k}\left\lfloor a_{k}\right\rfloor for k=0,1,2,k=0,1,2, \ldots contains at least one integer.

Hint: x\lfloor x\rfloor denotes the greatest integer part (integer function) of xx.

Solution

Solution:

We have a0=m+12a_{0}=m+\frac{1}{2} and a1=a0a0=(m+12)m=m2+m2a_{1}=a_{0}\left\lfloor a_{0}\right\rfloor=\left(m+\frac{1}{2}\right) \cdot m=m^{2}+\frac{m}{2}. This expression is obviously an integer for even mm, so that the desired property of the sequence holds in this case.

Furthermore, for m=1m=1 we have a0=32a_{0}=\frac{3}{2}, a0=1\left\lfloor a_{0}\right\rfloor=1, and for ak=32a_{k}=\frac{3}{2} we always also have ak+1=321=32a_{k+1}=\frac{3}{2} \cdot 1=\frac{3}{2}. Here, then, there is no integer term of the sequence.

Now let m3m \geq 3 be odd. There exists the unique representation m=2pn0+1m=2^{p} \cdot n_{0}+1 with p1p \geq 1, n0n_{0} odd and p,n0Np, n_{0} \in \mathbb{N}. Thus a0=2pn0+32a_{0}=2^{p} n_{0}+\frac{3}{2}, and for ak=2pnk+32a_{k}=2^{p} n_{k}+\frac{3}{2} (nkn_{k} odd) it follows that
ak+1=(2pnk+32)(2pnk+1)=2p1(2p+1nk2+5nk)+32, a_{k+1}=\left(2^{p} n_{k}+\frac{3}{2}\right)\left(2^{p} n_{k}+1\right)=2^{p-1}\left(2^{p+1} n_{k}^{2}+5 n_{k}\right)+\frac{3}{2},
where the term in parentheses is odd. Hence there exists a representation ak+1=2p1nk+1+32a_{k+1}=2^{p-1} n_{k+1}+\frac{3}{2} with nk+1n_{k+1} odd. Thus, as kk is increased by 11, pp is simultaneously decreased by 11, so that ak+p=20nk+p+32a_{k+p}=2^{0} n_{k+p}+\frac{3}{2} holds and ak+p\left\lfloor a_{k+p}\right\rfloor is even. Then ak+p+1a_{k+p+1} is an integer, and thus the desired property of the sequence also holds for every m3m \geq 3.

Thus all positive integers except 11 belong to the sought set.

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 translated into English from de; metadata (topic, difficulty) added by this project.