Maths Olympiad Prep

Track / Stage 6 / 227 of 400 #1227 of 1964

Problem 1227

National olympiad, first round
Number theory Difficulty 6.4 Prove it

 Xrabrov A\underline{\text { Xrabrov } A},

The sequence of natural numbers ana_{n} is constructed as follows: a0a_{0} is some natural number;

an+1=1/5ana_{n+1}=1 / 5 a_{n}, if ana_{n} is divisible by 5;

an+1=[5an]a_{n+1}=\left[\sqrt{5} a_{n}\right], if ana_{n} is not divisible by 5. Prove that starting from some term, the sequence ana_{n} increases.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

The condition is equivalent to the fact that starting from some nn, the number ana_{n} is not divisible by 5. Let's prove this.

We will show that there will be two consecutive terms of the sequence that are not multiples of 5. Suppose the opposite. Then for any nn, either an+1a_{n+1} is obtained from ana_{n} by dividing by 5, or an+2a_{n+2} is obtained from an+1a_{n+1} by dividing by 5. Note that ak+15aka_{k+1} \leq \sqrt{5} a_{k}, so an+21/55an<ana_{n+2} \leq 1 / 5 \sqrt{5} a_{n} < a_{n}. This means that the sequence of natural numbers a1,a3,a5,a_{1}, a_{3}, a_{5}, \ldots is strictly decreasing. Contradiction.

Thus, there will be aka_{k} and ak+1a_{k+1} that are not divisible by 5. We will prove that ak+2a_{k+2} is also not a multiple of 5. Similarly, we will sequentially obtain that ak+3,ak+4,a_{k+3}, a_{k+4}, \ldots are not divisible by 5, which is what we need.

ak+1=[5ak],ak+2=[5ak+1]a_{k+1} = \left[\sqrt{5} a_{k}\right], a_{k+2} = \left[\sqrt{5} a_{k+1}\right]. Let ak=ma_{k} = m, then ak+1=5mαa_{k+1} = \sqrt{5} m - \alpha, where 0<α<10 < \alpha < 1. ak+2=[5(5mα)]=5m+[5α]a_{k+2} = [\sqrt{5}(\sqrt{5} m - \alpha)] = 5 m + [-\sqrt{5} \alpha]. Since

0<5α<30 < \sqrt{5} \alpha < 3, then m3ak+2<5mm - 3 \leq a_{k+2} < 5 m, so ak+2a_{k+2} is not divisible by 5.

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