Can somebody provide a solution ?

very inteligent problem

First of all, it is clear that $x_i \ge \lfloor \sqrt{n}\rfloor$ for all $n$ since \[x_{i+1}=\left\lfloor \frac{x_i+y_i}{2}\right\rfloor=\left\lfloor \frac{x_i+\lfloor \frac{n}{x_i}\rfloor}{2}\right\rfloor=\left\lfloor \frac{\lfloor x_i+\frac{n}{x_i}\rfloor}{2}\right\rfloor \ge \left\lfloor \frac{\lfloor 2\sqrt{n}\rfloor}{2}\right\rfloor \ge \lfloor \lfloor \sqrt{n}\rfloor\rfloor=\lfloor \sqrt{n}\rfloor\]using $x+\frac{n}{x} \ge 2\sqrt{n}$ and $\lfloor 2x \rfloor \ge 2\lfloor x\rfloor$. So suppose the claim was false. Then $x_i>\sqrt{n}$ for all $n$. But then $y_i \le \frac{n}{x_i}<\sqrt{n}<x_i$ for all $i$. Hence $x_{i+1} \le \frac{x_i+y_i}{2}<x_i$ so that the sequence $(x_i)$ is strictly decreasing. But that of course is impossible since $x_1=n$ then implies $x_n \le 1<\sqrt{n}$. Done.

But that of course is impossible since $x_1=n$ then implies $x_n \le 1<\sqrt{n}$. Done. Can you explain the last sentence please and the ideas behind the problem.

Ad455 wrote: But that of course is impossible since $x_1=n$ then implies $x_n \le 1<\sqrt{n}$. Done. Can you explain the last sentence please and the ideas behind the problem. Well, we have an integer sequence $x_n$ with $x_1=n$ which is strictly decreasing. Hence $x_2 \le n-1, x_3 \le n-2$ etc. until finally $x_n \le 1$. But then since $1<\sqrt{n}$ this is a contradiction to our assumption that $x_i>\sqrt{n}$ holds for all $i$.

Thank you so much Tintarn