Problem: A function $f \colon \NN \to \NN$ satisfies
\[ \underbrace{f(f(\dots f}_{f(n)\text{ times}} (n)\dots)) %chktex 9
  = \frac{n^2}{f(f(n))} \]
for all positive integers $n$.
What are all possible values of $f(1000)$?

Solution: Actually, we classify all such functions: $f$ can be any function which fixes odd integers
and acts as an involution on the even integers.
In particular, $f(1000)$ may be any even integer.

It's easy to check that these all work, so now we check they are the only solutions.

\begin{claim*}
  $f$ is injective.
\end{claim*}
\begin{proof}
  If $f(a) = f(b)$, then $a^2 = f^{f(a)}(a) f(f(a)) = f^{f(b)}(b) f(f(b)) = b^2$,
  so $a = b$.
\end{proof}

\begin{claim*}
  We have $f(n) = n$ for every odd integer $n \ge 1$.
\end{claim*}
\begin{proof}
  We prove this by induction on odd $n \ge 1$.

  Assume $f$ fixes $S = \{1,3,\dots,n-2\}$ now (allowing $S = \varnothing$ for $n=1$).
  Now we have that
  \[ f^{f(n)}(n) \cdot f^2(n) = n^2. \]
  However, neither of the two factors on the left-hand side can be in $S$ since $f$ was injective.
  Therefore they must both be $n$, and we have $f^2(n) = n$.

  Now let $y = f(n)$, so $f(y) = n$.
  Substituting $y$ into the given yields
  \[ y^2 = f^n(y) \cdot y = f^{n+1}(n) \cdot y = ny \]
  since $n+1$ is even.
  We conclude $n=y$, as desired.
\end{proof}

\begin{remark*}
  [Motivation]
  After obtaining $f(1) = 1$ and $f$ injective,
  here is one way to motivate where the above proof comes from.
  From the equation
  \[ f^{f(n)}(n) \cdot f^2(n) = n^2 \]
  it would be natural to consider the case where $n$ is \emph{prime},
  because $p^2$ only has a few possible factorizations.
  In fact, actually because of injectivity and $f(1)=1$, we would need to have
  \[ f^{f(p)}(p) = f^2(p) = p \]
  in order for the equation to be true.
  Continuing on as in the proof above, one then gets $f(p) = p$ for odd primes $p$
  (but no control over $f(2)$).

  The special case of prime $n$ then serves as a foothold by which one can continue
  the induction towards all numbers $n$, finding the induction works out exactly
  when the prime $2$ never appears.

  As a general point, in mathematical problem-solving,
  one often needs to be willing to try out a proof idea or strategy
  and then retroactively determine what hypothesis is needed,
  rather than hoping one will always happen to guess exactly the right claim first.
  In other words, it may happen that one begins working out a proof of a claim
  \emph{before} knowing exactly what the claim will turn out to say, and this is the case here
  (despite the fact the proof strategy uses induction).
\end{remark*}

Thus, $f$ maps even integers to even integers.
In light of this, we may let $g \coloneq f(f(n))$ (which is also injective),
so we conclude that
\[ g^{f(n)/2} (n) g(n) = n^2 \qquad \text{ for } n = 2, 4, \dots. \]

\begin{claim*}
  The function $g$ is the identity function.
\end{claim*}
\begin{proof}
  The proof is similar to the earlier proof of the claim.
  Note that $g$ fixes the odd integers already.
  We proceed by induction to show $g$ fixes the even integers;
  so assume $g$ fixes the set $S = \{1, 2, \dots, n-1\}$, for some even integer $n \ge 2$.
  In the equation
  \[ g^{f(n)/2}(n) \cdot g(n) = n^2 \]
  neither of the two factors may be less than $n$.
  So they must both be $n$.
\end{proof}

These three claims imply that the solutions we claimed earlier are the only ones.

\begin{remark*}
  The last claim is not necessary to solve the problem;
  after realizing $f$ and injective fixes the odd integers,
  this answers the question about the values of $f(1000)$.
  However, we chose to present the ``full'' solution anyways.
\end{remark*}

\begin{remark*}
  After noting $f$ is injective, another approach is outlined below.
  Starting from any $n$, consider the sequence
  \[ n, \; f(n), \; f(f(n)), \; \]
  and so on.
  We may let $m$ be the smallest term of the sequence;
  then $m^2 = f(f(m)) \cdot f^{f(m)}(m)$
  which forces $f^{f(m)}(m) = f(f(m)) = m$ by minimality.
  Thus the sequence is $2$-periodic.
  Therefore, $f(f(n)) = n$ always holds,
  which is enough to finish.
\end{remark*}

\paragraph{Authorship comments.}
I will tell you a great story about this problem.
Two days before the start of grading of USAMO 2017,
I had a dream that I was grading a functional equation.
When I woke up, I wrote it down, and it was
\[ f^{f(n)}(n) = \frac{n^2}{f(f(n))}. \]
You can guess the rest of the story
(and imagine how surprised I was the solution set was interesting).
%Much to my surprise, when I woke up and remembered my dream
%I was actually able to solve the problem
%(and found that the solution set was nontrivial).
I guess some dreams do come true, huh?