24
$\begingroup$

Let $m$ be a natural number. Define $f(m) = m + \lfloor\sqrt{m}\rfloor$. Prove that at least one of the number among $m, f(m), f^2(m), \ldots$ is a perfect square. Here $f^k(m)$ denotes the composition of $f$ over itself $k$ times.

I tried the question, but the greatest integer along with square root is creating trouble.

$\endgroup$
  • 1
    $\begingroup$ If you don't mind my asking, where'd you find this? $\endgroup$ – Chris May 19 '17 at 19:34
  • 1
    $\begingroup$ @Chris A friend posted it on AoPs. Apparently, it was asked in some Indian exam. $\endgroup$ – user313479 May 19 '17 at 19:43
  • 2
    $\begingroup$ A footnote, since Joffan has already provided quite a nice answer: this question was asked as the B$4$ problem on the 1983 Putnam exam. (So if OP is interested, he can peruse the official solutions to that exam.) $\endgroup$ – Chris May 19 '17 at 21:22
22
$\begingroup$

Supposing $m$ is not a perfect square, then $m=n^2+k$, where $n^2$ is the largest perfect square less than $m$. Without loss of generality, if $k>n$ we can take $m_0=m-n$ and $k_0=k-n$, otherwise $m_0=m, k_0=k$.

Then we can see that $f^2(m_0) = n^2+k_0+2n = (n+1)^2+(k_0-1)$.

Taking $m_1=f^2(m_0)$ and $k_1=(k_0-1)$ we can see the same process applies relative to $(n+1)^2$ and so in a total of $2k_0$ applications of $f$ we will have a perfect square, $f^{2k_0}(m_0) = (n+k_0)^2$.


Additional observation: Note that once a square is found, $s_0^2 = f^d(m)$, the same process can be applied to $f^{d+1}(m) = s_0^2+s_0$, which will then give another perfect square at $f^{d+1+2s_0}(m) = (2s_0)^2$.

Thus there are an infinite number of perfect squares in the given sequence, of the form $(2^as_0)^2$, where $a$ is a non-negative integer. This also means there is at most one odd square in the sequence, which only occurs if $m_0$ is odd (or if $m$ itself is an odd square).

$\endgroup$
  • 1
    $\begingroup$ Nice! I guess it is a matter of taste what to do with the case $k=0$ (if we interpret the question to ask for a positive number of iterations). $\endgroup$ – Jyrki Lahtonen May 19 '17 at 20:03
  • 1
    $\begingroup$ @JyrkiLahtonen yeah, I thought I'd leave that to the intelligence of the readers :-) $\endgroup$ – Joffan May 19 '17 at 20:15
  • 1
    $\begingroup$ How the heck did you obtain this? The definitions of $m_0$ and $k_0$ make sense, but how did you anticipate the neat recurrence whereby $f^{2j}(m_0) = (n+j)^2 + (k_0 - j)$? Anyway, (+1) for you! $\endgroup$ – Chris May 19 '17 at 20:50
  • $\begingroup$ @Chris, I can't speak for Joffan, but my first thought on seeing the question was to try a geometric approach. I read the answer while considering its geometric meaning and my diagram made the recurrence fairly plain to see. $\endgroup$ – Wildcard May 20 '17 at 1:22
  • 1
    $\begingroup$ @Wildcard Sure, but my point was that for Joffan's argument it is irrelevant whether we allow $f^0(m^2)=m^2$ as a solution, or whether we apply the argument to $f(m^2)=m^2+m$, and then find a positive $\ell>0$ such that $f^\ell(m^2)$ is some other square. The basic idea still works the same. $\endgroup$ – Jyrki Lahtonen May 20 '17 at 4:19
1
$\begingroup$

The case where $m$ is a perfect square is trivial. Else there's a $k$ with $k^2 < m < (k+1)^2$. Define $r(m)= m - k^2$ and $s(m) = m - k - k^2$. We show that either $r$ or $s$ monotonically decreases with applications of $f^2$, that is, $f$ applied twice.

There are two cases:

  • If $m + k < (k + 1)^2$ then $f^2(m) = m + 2k = k^2 + r - 1 + 2k + 1 = (k+1)^2 + r(m) - 1$. So the error is now $r(f^2(m)) = r(m) - 1$.
  • If $m + k = (k+1)^2$ then we're done, so assume $m + k > (k+1)^2$. Then $f^2(m) = m + 2k + 1 = s(m) +k + k^2 +2k + 1 = (s(m) - 1) + (k+1) + (k+1)^2$. So the error is now $s(f^2(m)) = s(m) - 1$. Since $s$ decreases by $1$ each time, eventually we'll get that $s = 1$ and so applying $f$ again will give us the next square.
$\endgroup$
  • $\begingroup$ Dammit! I wrote out the whole solution for this question then it got closed: math.stackexchange.com/questions/2594691/…. So I'm just posting my solution to the duplicate, which is basically the same argument as the existing solution, but in a slightly different way. $\endgroup$ – Colm Bhandal Jan 6 '18 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy