math154 wrote: Let $a_0,b_0$ be positive integers, and define $a_{i+1}=a_i+\lfloor\sqrt{b_i}\rfloor$ and $b_{i+1}=b_i+\lfloor\sqrt{a_i}\rfloor$ for all $i\ge0$. Show that there exists a positive integer $n$ such that $a_n=b_n$. David Yang. We use contradiction method to deal with this problem. W.L.O.G., we let $a_i>b_i$, for all $i$ First $a_{i+1}-b_{i+1}=a_{i}-b_{i}+\lfloor\sqrt{b_i}\rfloor-\lfloor\sqrt{a_i}\rfloor$. This means $a_{i+1}-b_{i+1}\le a_{i}-b_{i}$, the equality case holds when $\lfloor\sqrt{b_i}\rfloor=\lfloor\sqrt{a_i}\rfloor$ By contradiction, we must have one $N$, such that for all $n\ge N$, $\lfloor\sqrt{b_n}\rfloor=\lfloor\sqrt{a_n}\rfloor$, which is equvalent to between $a_n$ and $b_n$, there is no square number. If $a_N>b_N+1$, we can use $b_N+1$ subsitute $a_N$. It is because the difference between $a_N$ and $b_N$ is smaller. Let $a_{N+1}=x^2+r$, $b_{N+1}=x^2+r-1$ where $0\le r<2x+1$, If $r=0$, $a_{N+1}$ is a perfect square, and $a_{N+2}=b_{N+2}$. Contradiction! If $r=x+1$, $a_{N+2}=x^2+2x+1$, which is a perfect square, again contradiction! If $r>x+1$, we have $a_{N}=x^2+t$, where $t<x+1$. Therefore we only need to consider the case that $r<x+1$ If $0<r<x+1$, it is easy to check that $a_{N+3}=(x+1)^2+r-1$, $b_{N+3}=(x+1)^2+r-2$. By induction we have $a_{N+2r+1}=(x+r)^2$, $b_{N+2r+1}=(x+r)^2-1$ Therefore $a_{N+2r+2}=b_{N+2r+2}=(x+r)^2+x+r-1$. Contradiction! As a result, we must have one $n$ such that $a_n=b_n$. The proof is complete.

I claim that $|a_n - b_n|$ is a non-increasing sequence of non-negative integers. To see why, remark that $a_{n+1} - b_{n+1} = a_n - b_n + \lfloor \sqrt{b_n} \rfloor - \lfloor \sqrt{a_n} \rfloor$. $a_n - b_n$ and $\lfloor \sqrt{b_n} \rfloor - \lfloor \sqrt{a_n} \rfloor$ have opposite signs, so the result follows. Hence, there exists some $N$ such that for all $n > N$, $|a_n - b_n| = C$ for some constant $C$. It is not hard to show there exists some $N'$ such that for all $n \ge N'$, $\text{sgn}(a_n - b_n) = \text{sgn}(a_{N'} - b_{N'})$ ($N' = N+1$ or $N$ actually lol) But then we have $\lfloor \sqrt{a_n} \rfloor = \lfloor \sqrt{b_n} \rfloor$ for all $n \ge N'$. However, this is clearly false unless $C=0$. WLOG $a_{N'} > b_{N'}$. Then let $a_{N'} = x^2 + m, b_{N'} = x^2 + (m-C)$ where $C \le m \le 2x$. Define $[x] = x - \lfloor \sqrt{x} \rfloor ^2$. Then remark that we need $[a_n] \ge C$ for all $n \ge N'$ as otherwise $\lfloor \sqrt{a_n} \rfloor \neq \lfloor \sqrt{b_n \rfloor}$. For $i = N'$ or $N'+1$ we have $[a_i] \le \lfloor \sqrt{a_i} \rfloor$. But then note that $[a_i] = [a_{i+2}]+1 = [a_{i+4}] + 2 = ...$. Eventually $[a_i] < C$ if $C > 0$, but then this will derive a contradiction. Thus $C=0$ and thus we're done. EDIT : Also, $|x-y| \ge |\lfloor \sqrt{x} \rfloor - \lfloor \sqrt{y} \rfloor |$ is needed to establish $|a_n - b_n|$ is a non-increasing sequence. However, this is trivial to prove.

As has been shown above, $a_i-b_i$ either remains the same or decreases at each stage. Now, suppose for a contradiction that $\lfloor\sqrt{b_i}\rfloor=\lfloor\sqrt{a_i}\rfloor$ for all $i$ greater than some $j$. Then note that the system of recursions become $a_{i+1}=a_i+\lfloor\sqrt{a_i}\rfloor$ and $b_{i+1}=b_i+\lfloor\sqrt{b_i}\rfloor$. Now it is easy to show by induction (Putnam-1983, anyone?) that for some $k, a_k$ is a perfect square. Let $a_k=t^2$. But since $a_k>b_k$, hence we have $\lfloor\sqrt{a_i}\rfloor=t$ and $\lfloor\sqrt{b_i}\rfloor=t-1$ which contradicts our assumptions. We are done. P.S: Putname 1983 states that if $f(n)=n+\lfloor\sqrt{n}\rfloor$, then for all $m\ge0$, the sequence $f(m),f(f(m)),f(f(f(m)))\cdots$ contains a perfect square.

WLOG let $a_0>b_0$. It's easy to show that $a_i>b_i$ for all $i$, hence $a_i-b_i\geq 0$ is clearly nondecreasing in $i$ and thus if such an $n$ does not exist, it must be eventually constant, i.e. we must have $\lfloor \sqrt{a_i}\rfloor=\lfloor \sqrt{b_i}\rfloor$ for all sufficiently large $i$. Pick some $m$ large such that the above equality is true for all $i\geq m$, and suppose that $a_i=x^2+a$ and $b_i=x^2+b$, so $a>b$. It is clear by induction that $a_{i+2k}=(x+k)^2+(a-k)$ for $1 \leq k \leq a$ and similarly $b_{i+2k}=(x+k)^2+(b-k)$ for $1 \leq k \leq b$. Thus taking $k=b$, we have $a_{i+2k}=(x+k)^2+(a-b)$ and $b_{i+2k}=(x+k)^2$, so $a_{i+2k+2} \geq (x+k)^2+2(x+k)+(a-b)\geq (x+k+1)^2$ and $b_{i+2k}=(x+k)^2+2(x+k)<(x+k+1)^2$, hence $\lfloor \sqrt{a_{i+2k+2}}\rfloor \neq \lfloor \sqrt{b_{i+2k+2}}\rfloor$: contradiction. $\blacksquare$