I claim that the answer is all positive evens. As a construction for an even $a$, consider the function \begin{align*} f(x)= \begin{cases} x \text{ for } x\neq a,1000 \\ a \text{ for } x=1000 \\ 1000 \text { for } x=a \\ \end{cases} \end{align*}Clearly, this function satisfies the assertion. Now, suppose that $f(1000)$ is odd. First, we will show injectivity. If $f(a)=f(b)$, then the condition implies $a^2=b^2\implies a=b$ as desired. Now, consider the sequence $S:\,1000,f(1000),f^2(1000),\ldots$. Note that, if we plug $f^k(1000)$ into the assertion, we get $f^{f^{k+1}(1000)+k}(1000)f^{k+2}(1000)=f^k(1000)^2$. So, one of the factors on the LHS is $\le f^k(1000)$. In particular, this implies that for all elements in $S$, there always exists a later element which is at most the current number. However, we can't have it always strictly decreasing, since all the values are positive integers, so eventually we find $i>j$ such that $f^i(1000)=f^j(1000)$, which combined with injectivity gives that $f^{i-j}(1000)=1000$. Therefore, $S$ is periodic with period $i-j$. Now, suppose we have an odd $x$. By the condition, $f^2(x)|x^2$, so $f^2(x)$ is odd. This means that $f^3(1000),f^5(1000),$ etc. are all odd. In general, $f^{2i+1}(1000)\equiv 1\pmod 2$. Now, plug $1000$ into the assertion to get that $1000^2=f^2(1000)f^{f(1000)}(1000)$. The latter factor is odd, so we must have $2^6|f^2(1000)$. Similarly, after plugging in $f^2(1000)$, we realize that $2^{12}|f^4(1000)$, and then $2^{24}|f^6(1000)$, etc. So, the sequence $\{v_2(f^{2i}(1000)\}$ is unbounded, which of course implies that $S$ is unbounded, as all terms are nonzero. However, this is a contradiction to the fact that it is periodic, and therefore $f(1000)$ cannot be odd.

Let $P(n)$ be the assertion that \[f^{f(n)}(n)f^2(n)=n^2.\]Note that this is our FE. We'll first show that $f(1)=1$. $P(1)$ gives \[f^{f(1)}(1)f^2(1)=1,\]so $f^2(1)=1$. Let $k=f(1)$. Then, $P(k)$ gives \[f^1(k)f^2(k)=k^2,\]so $k=k^2$, or $k=1$, or $f(1)=1$. We now have a lemma that is the crux of the solution. Lemma: If $f(n)=n$, and $f(m)=n$, then $m=n$. Proof of Lemma: $P(m)$ gives \[f^n(m)f^2(m)=m^2,\]or $n^2=m^2$, or $n=m$. $\blacksquare$ This yields an easy corollary that if $f^\ell(m)=n$, then $m=n$. We now show that $f$ is the identity on the odds. Claim: $f(n)=n$ for odd $n$. Proof of Claim: Proceed by strong induction on $n$. The case $n=1$ is sovled. Suppose $f(n')=n'$ for all odd $n'<n$. We have \[f^2(n)f^{f(n)}(n)=n,\]so if $f^2(n)\ne n$, then one of the two LHS terms is odd and less than $n$. But then the lemma gives a contradiction, so $f^2(n)=n$. Let $k=f(n)$. $P(k)$ gives \[f^n(k)f^2(k)=k^2,\]or $f^n(k)=k$. But since $n$ is odd, $f^n(k)=f(k)=n$, so $n=k$, so $f(n)=n$, completing the induction. $\blacksquare$ The lemma now implies that $f(1000)$ must be even. To see that all even values are attained, it's easy to check that if $f$ is the identity on the odds and an involution on the evens, it satisfies the FE. Our involution can swap $1000$ and $k$ for any even $k$, so we hit all evens, as desired.

My problem. Have a great story to tell during the upcoming math jam about how I came up with it... EDIT: for posterity, here's the story. 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 from there! 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. Claim: $f$ is injective. 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$. $\blacksquare$ Claim: $f$ fixes the odd integers. 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. $\blacksquare$

Thus, $f$ maps even integers to even integers. In light of this, we may let $g \coloneqq 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. \] Claim: The function $g$ is the identity function. 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$. $\blacksquare$ These three claims imply that the solutions we claimed earlier are the only ones. 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. 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)) = f^{f(m)}(m) = m$ by minimality. Thus the sequence is $2$-periodic. Therefore, $f(f(n)) = n$ always holds, which is enough to finish.

The possible values are all the even positive integers. To see that they work, note that \[f(n) = \begin{cases*} n & $n \neq 1000, \lambda$\\ \lambda & $n = 1000$\\ 1000 & $n = \lambda$ \end{cases*}\]is always a solution for any even $\lambda$. To check this, it is only important that $f$ fixes all odd integers and is an involution on the even integers. For convenience let $P(n)$ denote the functional equation. If $n$ is odd, then $f(n) = n$ and so $P(n)$ reads $n = \tfrac{n^2}{n}$ which is valid. If $n$ is even, then $f(f(n)) = n$, so $f^{f(n)}(n) = n$ as $f(n)$ itself is even. Hence once again $P(n)$ reads $n = \tfrac{n^2}{n}$ which is valid. Now we prove that $f(1000)$ cannot be odd. Claim. The function $f$ is injective. Proof. If $f(a) = f(b)$, then \[\frac{a^2}{f(f(a))} = f^{f(a)}(a) = f^{f(b)}(b) = \frac{b^2}{f(f(b))}\]so $a = b$. $\square$ Claim. The function $f$ fixes all the odd positive integers. Proof. We prove by induction on odd $n$ that $f(n) = n$. Suppose it has been proven for all $1, 3, \dots, n-2$ and consider the statement for $n$. The statement $P(n)$ reads \[f^{f(n)}(n) \cdot f(f(n)) = n^2.\]In particular, both numbers $f^{f(n)}(n)$ and $f(f(n))$ are odd. Since $f(k) = k$ for $k = 1, 3, \dots, n-2$, we obtain that $f^{f(n)}(n) \ge n$ and $f(f(n)) \ge n$, and so \[f^{f(n)}(n) = f(f(n)) = n.\]If $f(n)$ is odd, we get $f(n) = n$ by injectivity. Suppose that $m = f(n)$ is even, so $n = f(m)$ and so $P(m)$ gives \[m^2 = [f^{f(m)}(m)] \cdot [f(f(m))] = [f(m)] \cdot [m] \implies m = n\]which is not possible. Thus $f(n) = n$ and the inductive step is complete. $\square$ To finish the problem, recall that $f$ is injective, but $f(n) = n$ for all odd $n$. Hence $f(1000)$ cannot be odd.

get a point?

I found that you only needed to prove f(n)=n for all prime powers, because 1000 has only 1 prime factor.

Does this induction work to prove that $f(f(n))=n$ for odd $n$? Define an order relationship on sequences of nondecreasing positive integers such that: $s_1>s_2$ if $s_1$ has more elements than $s_2$ $s_1>s_2$ if $s_1$ and $s_2$ has the same number of elements but the sum of the terms of $s_1$ is bigger than that of $s_2$ Break ties lexicographically. We induct on numbers of the form $n=\prod p_i^{e_i}$ where the $\{e_i\}$ are ordered as given above. Now from $f(f(n))f^{f(n)}(n)=n^2,$ if $f(f(n)) \neq n,$ one of $f(f(n))$ or $f^{f(n)}(n)$ have its exponent sequence in its prime factorization come before that of $n$ in our ordering. But for those guys we already know $f(f(k))=k,$ breaking injectivity. So $f(f(n))=n.$ The main issue is whether doing the induction in this order is valid... can anyone confirm?

The answer is any even integer. To show that these work, let $m$ be an even integer and consider the function $f$ that fixes all integers besides $1000$ and $m$ and swaps $1000$ and $m$. Then both sides of the equation are equal to $n$ for all $n$ — if $n=1000$ or $m$ then $f(n)$ is even so the LHS is a convolution of $f^2$ which is identity; if $n\neq1000$ or $m$ then everything is a convolution of the identity. Now we show that odd integers do not work. First note that $f$ is injective. Indeed, if $f(a)=f(b)$ then \[a^2=f^{f(a)-1}(f(a))f(f(a))=f^{f(b)-1}(f(b))f(f(b))=b^2\]so $a=b$. Now we prove that all odd $n$ are fixed points of $f$. For $n=1$, we have \[1=f^{f(1)}(1)f^2(1)\]so $f^{f(1)}(1)=f^2(1)=1$. Additionally, \[f(1)^2=f^{f(f(1))}(f(1))f^2(f(1))=1\cdot f(1)\]so $f(1)=1$. Now assume $1,3,\ldots,n-2$ are fixed points for some odd $n$. We have \begin{align*} n^2&=f^{f(n)}(n)f^2(n)\\ f(n)^2&=f^{f^2(n)+1}(n)f^3(n) \end{align*}by the functional equation. Then $f^2(n)$ is odd. If $f^2(n)<n$ then it is a fixed point. Then $f^3(n)=f^2(n)$ so by injectivity, $f(n)=n$ so $f^2(n)=n$, contradiction. Similarly $f^{f(n)}(n)$ is odd. If $f^{f(n)}(n)<n$ then it is a fixed point, so $f^{f(n)+1}(n)=f^{f(n)}(n)$ and by injectivity, $f(n)=n$ so $f^{f(n)}(n)=n$, contradiction. Thus $f^2(n)$ and $f^{f(n)}(n)$ are both at least $n$. But their product is $n^2$, so both are exactly $n$. But then \[f(n)^2=f^{n+1}(n)f(n)\]and $n+1$ is even so $f^{n+1}(n)=n$ and it follows that $f(n)=n$. So by induction, all odd $n$ are fixed points. Suppose $f(1000)=m$ with $m$ odd. Then $f^{f(n)}(n)=m$ and $f^2(n)=m$ so $n^2=m^2$, contradiction. Thus $f(1000)$ must be even.

If $f(a)=f(b),$ $a^2=b^2$ and $a=b,$ so $f$ is injective. Let $a_0=1000,$ $a_i=f(a_{i-1}).$ Plugging in $n=a_i$ gives $a_{i+a_{i+1}}a_2=(a_i)^2.$ Take $a_i$ minimal. As $a_{i+a_{i+1}}\ge a_i$ and $a_{i+2}\ge a_i,$ by the above $a_{i+2}=a_i.$ Backwards induction + injectivity then gives $a_2=a_0.$ Plugging in $1000$ then gives $a_1=1000$ or $a_1$ is even. As even is easy to construct, the answer is all positive even integers.

Generic_Username wrote: Does this induction work to prove that $f(f(n))=n$ for odd $n$? Define an order relationship on sequences of nondecreasing positive integers such that: $s_1>s_2$ if $s_1$ has more elements than $s_2$ $s_1>s_2$ if $s_1$ and $s_2$ has the same number of elements but the sum of the terms of $s_1$ is bigger than that of $s_2$ Break ties lexicographically. We induct on numbers of the form $n=\prod p_i^{e_i}$ where the $\{e_i\}$ are ordered as given above. Now from $f(f(n))f^{f(n)}(n)=n^2,$ if $f(f(n)) \neq n,$ one of $f(f(n))$ or $f^{f(n)}(n)$ have its exponent sequence in its prime factorization come before that of $n$ in our ordering. But for those guys we already know $f(f(k))=k,$ breaking injectivity. So $f(f(n))=n.$ The main issue is whether doing the induction in this order is valid... can anyone confirm? Are you sure there are countably many sequences? Edit: can’t map reals

sampai7 wrote: Generic_Username wrote:

Are you sure there are countably many sequences? You can map the reals to sequences of integers right? *infinite sequences, finite okay.

Quote: Are you sure there are countably many sequences? Well the induction can be characterized by $(k,\Sigma, S)$ where $k$ is the number of terms, $\Sigma$ is the sum of the terms, and $S$ is the set of sequences with $k$ terms and sum $\Sigma.$ Here $S$ is finite. So one can envision this as induction on the two parameters $k$ and $\Sigma$?

I got that $f(n)$ fixes all odd $n$ in around 45 minutes and then freaked out after realizing that the answer was *not* $f(n)=n$, didn't see that I could just give a construction and finish, so spent another hour proving that $f$ is an involution for all $n$ (even and odd) and another hour writing up before realizing that it was unnecessary :thunk: . Rewrote my solution finishing from $f$ fixes odd step using half as many pages, but oh well

budu wrote:

get a point? I feel like it definitely should - especially since showing f(2n-1) = 2n-1 is done pretty much the same way as f(p) = p except with induction. However, I guess this was a large portion of the problem. I think given that you had f(1) = 1 and injectivity, it should be a point. Maybe more than 1 but that seems rare.

yrnsmurf wrote: I found that you only needed to prove f(n)=n for all prime powers, because 1000 has only 1 prime factor. What??

Lol my proof didn't actually prove f(x)=x for all odds. I just prove that the period of 1000, f(1000),f(f(1000))... must be 2 (or a factor of 2), which implies the result. Basically if it has a period, take the largest value and notice that f(f(Max))=Max, cuz it's one of two terms that multiply to the max. (Actually we can do the same for the min oops). Thus, injectivity gets period of 2. This proves that we must have even as odd will result in f^odd(1000)=odd, while f^2(1000)=1000. If no period, due to injectivity, must all be distinct terms, so yeah gg just contradiction with min term (cuz bounded from bottom so always a min).

For this problem I got: all evens work, $f(1) = 1$, $f(a) \neq 1$ if $a > 1$, odd primes produce odd numbers, and tried somewhat on odd numbers produce only odd numbers, ultimately concluding only evens work. All proofs were rigorous except the "tried somewhat" one. For my "construction" I just said the numbers other than 1000 and x didn't matter (and just said: $f(1000) = x$ while $f(x)=1000$). I didn't think it necessary to address how f(n) could be, for example, n for all other naturals. How many points would that be?

hmm @above i would guess 1 i got that $f(p)=p$ for all odd primes and that $f^k(n)\ne 1$ for $k\in \mathbb{N}$ and $n\ge 2$ but i said that only 1000 worked rip

asdf334 wrote: you also need to provide a construction although that would probably just be 1 point off o oops

Let $f^k(n)=\underbrace{f(f(\ldots f}_{k\text{ times}}(n)\ldots))$ and $P(n)$ the assertion $f(f(n))f^{f(n)}(n)=n^2$. From $P(n)$, $f$ is injective. We will prove by induction that $f(2n+1)=2n+1$ for $n\ge0$. Base case: $f(1)=1$ Note that $P(1)\Rightarrow f^{f(1)}(1)f(f(1))=1$, so $f(f(1))=1$. Then $P(f(1))$ finishes. Induction step: $f(2k+1)=2k+1$ for $0\le k<2n+1$ If $f(f(2n+1))\ne2n+1$ then we either have that $f(f(2n+1))$ is odd and less than $2n+1$, or $f^{f(2n+1)}(2n+1)$ is odd and less than $2n+1$. If $k$ is odd and less than $2n+1$, then $f(k)=k$. In the first case, we have $f(f(f(2n+1)))=f(f(2n+1))$, so $f(2n+1)=2n+1$ since $f$ is injective. If, on the other hand, $f^{f(2n+1)+1}(2n+1)=f^{f(2n+1)}(2n+1)$, we still have $f(2n+1)=2n+1$. Now we just need to consider the case $f(f(2n+1))=2n+1$, so $f^{2n}(2n+1)=2n+1$ $P(f(2n+1))\Rightarrow f^{2n+2}(2n+1)=f(2n+1)\Rightarrow f^{2n+1}(2n+1)=2n+1\Rightarrow f\left(f^{2n}(2n+1)\right)=2n+1\Rightarrow f(2n+1)=2n+1$ If $f(1000)$ is odd, then $f(f(1000))=f(1000)$, so $f^n(1000)=f(1000)$ for $n\in\mathbb N$. But $P(1000)$ gives $f(1000)=1000$, a contradiction. When $f(1000)=2k$, the function defined by $f(2k)=1000$, $f(1000)=2k$, and $f(n)=n$ otherwise satisfies $P(n)$.

Clearly $f$ is injective and $f(1)=1.$ Assume that $f(x)=x$ for $x<n$ with both $x,n$ odd. If $f(f(n))\neq n$ then $f^{f(n)}(n)f(f(n))=n^2$ implies either of them is odd and smaller than $n.$ But, by hypothesis and injectivity, this is absurd. So $f(f(n))=n$ for all odd $n.$ Finally $f(n)^2=f^{n} (f(n))f(n)=nf(n)$ so $f(n)=n.$ And hence $f(1000)$ must be even. For construction, set for any even $x$, $f(1000)=x$ and $f(f(1000))=1000$ and for other numbers $f(y)=y.$

$\textbf{Lemma 1.}$. $f$ is injective. For the sake of contradiction, assume otherwise. Then there exists $a>b, f(a)=f(b)=c$. Plugging $n=a,b$ we have $ stuff=a^2=b^2$ which is a contradiction since $a>b$, hence $a=b$. $\textbf{Lemma 2.}$ $f(1)=1$. Note that since $LHS$ is a natural number, we must have that $f^2(1)=1$. If $f(1)=2k$ for some natural number $k$, We have $f(2k)=1$. Plugging $n=2k$, we have $f(2k)=1=2k$, contradiction. Hence $f(1)=1$. $\textbf{Lemma 3.} f(2n+1)=2m+1$ for some natural numbers $n,m$. Assume that there exists some $n$ such that $f(2n+1)=2m$. Then we have $f(2m)=2n+1$ plugging $n=2n+1$ we have $ f^2(2n+1)=n$ which is a contradiction. $\textbf{Lemma 4.}$ $f(p)=p$ for some odd prime number $p$. Since $\frac{p^2}{f^2(p)}$ is an integer, we have cases $f^2(p)=1,p,p^2$ If $f^2(p)=1$, then by injectivity, $p=1$, contradiction. If $f^2(p)=p^2$ or $f^{f(p)}(p)=1$, by injectivity we must have $p=1$, contradiction. Hence, $f^2(p)=p$. Since $f(p)$ is odd, we have $f^{odd}(p)=f(p)=p$, hence conclusion. $\textbf{Lemma 5.} f(2k+1)=2k+1$ for all integers $k$ Note that since $f^2(n) | n^2$, starting by smaller factors $a_1,a_2,..$ we have $f(a_1)=a_1,f(a_2)=a_2...$ by injectivity hence we have $f^2(2k+1)=2k+1$. But observe that $$ f^{odd}(2k+1)= f(2k+1)= \frac{(2k+1)^2}{2k+1}=2k+1$$. Hence the conclusion. Now, we will show that $f(1000)=2k$ works for all integers $k$. Since $f(2k)=1000$, We have $f^{even}(2k)= f^2(2k)$. Then $f^2(2k)=2k$, which works. Checking $n=1000$, we can conclude that $f(1000)=2k$ indeed works, hence we are done

this problem sux never write dream problems again Rewrite our FE as $f^{f(n)}(n) \cdot f^2(n)=n^2$. Denote this assertion by $G(n).$ Claim 1: $f(1)=1$. Proof: $G(1)$ gives $f^{f(1)}(1)*f^2(1)=1,$ i.e. $f^2(1)=1.$ $G(f(1))$ gives $f^{f(f(1))}(f(1))*f^3(1)=f(1)^2$, or $f(1) = f(1)^2 \implies f(1) = 1$ as desired. Claim 2: $f$ is injective. Proof: Let $f(n)=f(m).$ Then $\frac{n^2}{f(f(n))} = \frac{m^2}{f(f(m))} \implies n^2=m^2 \implies n=m$, proving our claim. Claim 3: $f(n)=n$ for any odd $n.$ Proof: Strong induct on $n.$ We have already proved the base case $n=1$. For the inductive step, assume the claim holds for all odd $m < n.$ Then $G(n)$ implies that one of $f^{f(n)}(n)$ or $f^2(n)$ is an odd integer less than or equal to $n.$ If either $f^{f(n)}(n)$ or $f^2(n)$ were to be less than $n,$ this would contradict the fact that $f$ is injective, so $f^2(n) = n.$ Now, $G(f(n))$ implies that $f^n(f(n))*f^3(n)=f(n)^2$ or $f^n(f(n))=f(n).$ But $n$ is odd, so $f^n(f(n))=f(f(n))=n \implies f(n)=n$ as desired. This means that $f(1000)$ cannot be any odd integer, so it must be able to attain all evens - a construction for some even $k$ is $f(k)=1000$, $f(1000)=k$, and $f(n) = n$ for all other $n.$

woah, I've actually gotten better at math in the past four years? This problem seemed so impossible back in 2019. I claim that the answer is all positive even numbers. To see this, we may construct a working $f$ as follows: map each odd number to itself, and pair up even numbers $(2a,2b)$ so that $f(2a)=2b, f(2b)=2a$. This clearly works since $f^{f(n)}(n) \cdot f(f(n))= n\cdot n$ for all $n$. Thus, we may pair 1000 with any even number, and pair up the other evens with each other, and have constructed the function. We now show that $f(1000)$ cannot be odd. To do this, we attempt to prove the following, stronger claim. Claim: For all odd $n$, $f(n)=n$ and there do not exist $z\neq n$ such that $f(z)=n$. More succinctly, $f(z)=n$ if and only if $z=n$. Proof: To see this, we strong induct. Note that plugging $n=1$ into the condition gives: \[f^{f(1)}(1) \cdot f(f(1)) = 1^2 = 1\]Thus, we must have both $f^{f(1)}(1) = f(f(1))=1$. There are two ways for $f(f(1))=1$. However, in the case where $f(1)=m, f(m)=1$ for some $m\neq 1$, we must then have $m$ even in order for $f^{f(1)}(1)=1$. However, this then gives \[m^2 = f^{f(m)}(m) \cdot f(f(m)) = f(m)\cdot f(f(m)) = 1\cdot m\]a contradiction. Thus, $f(1)=1$. Now, we may move onto the inductive step. Assume that the claim is true for all $z<n$. Now, recall that \[f^{f(n)}(n) \cdot f(f(n)) = n^2\]However, both of the terms on the left side, $f^{f(n)}(n)$ and $f(f(n))$, both must be odd, and therefore cannot be less than $n$. This is because this would contradict the fact that there does not exist $z\neq d$ such that $f(z)=d$. Therefore, we must have \[f^{f(n)}(n) = f(f(n)) = n\]As before, we have two cases for $f(f(n))$. But, if $f(n)=m, f(m)=n$, then we must even $m$ in order for $f^m(n)=n$, and \[m^2 = f^{f(m)}(m) \cdot f(f(m)) = f^{\text{odd}}(m) \cdot f(f(m)) = n\cdot m\]a contradiction. Thus, $f(n)=n$. And for the second half of the inductive step, if $f(z)=n$ for some $z\neq n$, then \[z^2 = f^{f(z)}(z) \cdot f(f(z)) =f^n(z) \cdot f(f(z)) = n^2\]a contradiction. Thus, we have established for all odd $n$ that $f(z)=n$ if and only if $z=n$ through strong induction and we are now done. $\square$. With this claim, we clearly cannot have $f(1000)$ equal to some odd number, so $f(1000)$ must be even, but we have also shown that all even numbers are achievable, and have fully characterized the set of possible $f(1000)$ values. $\blacksquare$

We claim that the answer is all even integers. The following construction works for all even $k$: \[f(1000) = k, f(k) = 1000, f(n) = n \forall n \not\in \{1000, k\}\] Lemma 1: $f$ is injective. Proof: Suppose that $f(a) = f(b) = c$. Note that \[f^{f(a)}(a) = \frac{a^2}{f(f(a))} \implies f^c(a) = \frac{a^2}{f(c)} \implies a^2 = f^{c-1}(c)\]similarly, $b^2 = f^{c-1}(c)$, so $a = b$. Note that this implies that $f$ consists of some cycles and some nonperiodic sequences. Lemma 2: No nonperiodic sequence $f(n), f^2(n), f^3(n), \dots$ exists. Proof: Suppose that such a sequence exists. Take the minimum integer $m$ in that sequence. However, either $f^{f(m)}(m)$ or $f(f(m))$ is less than $m$, contradicting its minimality. Lemma 3: All cycles have period $1$ or $2$ Proof: Take the minimum integer $m$ in a cycle. However, $f^{f(m)}(m) = \frac{m^2}{f(f(m))} < m$, contradicting its minimality. Thus, $f(f(n)) = n$ for all $n$. Finally, note that if $f(1000) = k$ is odd, then $f^{f(k)}(k) = 1000 = \frac{k^2}{k} = k$, which is absurd.

The answer is all evens. For a construction, take $f(x)=x$ but swap the outputs for an even $a$ and $1000$. Also, obviously $f(f(1))=1$. FTSOC, assume there exists an odd $x$ such that $f(1000)=x$. Then we have \[f^x(1000)=\frac{1000^2}{f^2(1000)}\] Claim: For no even $a$ does $f(a)=1$. Proof: FTSOC, assume that $f(a)=1$ for some even $a$. Then, $f(a) = \frac{a^2}{f(f(a))}$ so $f(f(a))=a^2$. This means $f(1)=a^2$ so $f(a^2)=1$. Now plugging in $a^2$ into the original expression gives $f(a^2)=\frac{a^4}{f(f(a^2))} \implies f(a^2)=a^2$ which is a contradiction. Now consider the sequence $S=(f^0(n),f^1(n) \dots)$ where $n=1000$. Note that the $i$th term is the product of the $i+2$th term and the $i+f(x)$th term where $x$ is the value of the $i+1$th term. In particular, both of those values divide the $i$th term. Claim: The terms $f^{(2k+1)}(n)$ are odd. Proof: Note every $f^{(2k+1)}(n)$ divides $f^{(2k-1)}(n)$ and since $f^1(n)$ is odd by assumption, we are done by induction. Claim: The terms $f^{(2k)}(n)$ are all even. Proof: Consider the first term $f^{(2k)}(n)$ that isn't even. Note that this must at least be the second term since the first is even by assumption. Then, $f^{(2k-2)}(n)^2$ is the product of this non-even term and some even term later down the sequence. However, note that $f^{(2k+2)}(n)|f^{(2k)}(n)^2$ so that later term shares all its primes with $f^{(2k)}(n)$, implying that is is also even. Thus, all the even terms are of type $f^{(2k)}(n)$. Now consider the first occurrence of the smallest term in $S$, which is more than $1$ by the first claim. Then, since its square is the product of two terms later, those two terms must equal that smaller term. In particular, we have $x=f^2(x)$ for some $x$ in the sequence, so at some point, the sequence repeats with periodicity at most $2$. The periodicity cannot be $1$ by the parity claims above. If the periodicity is $2$, then consider the first even term in the periodic part. It is equal to the geometric mean of the two repeated terms because they have different parities by the claim above, implying that they are equal, contradicting that they have periodicity $2$. Thus, we are done.

Of course, $f$ is injective. We claim that $f(n) = n$ for all odd $n$. We will use strong induction. Base case: $f(1) = 1$. Note that $f(f(1)) = 1$. If $f(1)$ were some even integer, say $2n$, then, $f(2n) = 1$, so $f(2n) = \frac{4n^2}{f(f(2n))} = \frac{4n^2}{2n} = 2n$, a contradiction. If $f(1)$ were some odd integer, say $2n+1$, it follows that $f(1) = \frac{n^2}{1}$. Solving over positive integers gives us $n=1$, so $f(1) =1$. Inductive step: To show $f(n) = n$. If $f(f(n)) > n$, then $\underbrace{f(f(\ldots f}_{f(n)\text{ ties}}(n)\ldots))$ is some odd integer $m$ that is less than $n$. But that implies that $n = m$, due to the injectivity of $f$ and our inductive assumption (only $f(m) = m$), so this is a contradiction. If $f(f(n)) < n$, $f(f(n))$ must be odd, which results in a similar contradiction. So $f(f(n)) = n$. Therefore, \[ \underbrace{f(f(\ldots f}_{f(n)\text{ times}}(n)\ldots)) = n. \]If $f(n) = m$ for some even $m$, it follows that $f(m) = n$; then, plugging $m$ into the functional equation gives us $f(m) = \frac{m^2}{f(f(m))} = m,$ a contradiction. So, $f(n)$ is odd. Then, the functional equation becomes \[ f(n) = \frac{n^2}{f(f(n))} = n,\]as desired. Therefore, due to the injectivity of $f$, $f(1000)$ must be even. It may, in fact, be any even integer, since for any even integers $a$ and $b$, we can let $f(a) = b$ and $f(b) = a$ without any adverse effects. The fact that Evan wrote a problem as nice as this, not just in his head, but in a dream, is proof that God must exist - God is Evan.

We claim that the answer is all even positive integers. Say that a positive integer $n$ is stuck if $f(n)=n$ and $f(k)\neq n$ for all $k\neq n$. We will gradually build up to the claim that all odd $n$ are stuck. Denote by $ord(n)$ the minimum $m\geq 1$ such that $f^m(n)=n.$ Claim 1: 1 is stuck. Clearly, $$f^{f(1)}(1)=f(f(1))=1.$$Now, if $f(1)\neq 1$, then $f(1)=2k$ and $f(2k)=1$ for some $k$ since $ord(1)=2$. However, we would then have $$f^{f(2k)}(2k)f(f(2k))=f^{1}(2k)f(1)=2k,$$which is a contradiction. Thus, $f(1)=1.$ Now, if $f(r)=1$ for $r\neq 1,$ then $$f^{f(r)}(r)f(f(r))=f^{1}(r)f(1)=1,$$also a contradiction. Hence, 1 is stuck. Now, we will show that if $n$ is an odd positive integer for which all odd positive integers less than $n$ are stuck, then $n$ is also stuck. We have $$f^{f(n)}(n)f(f(n))=n^2.$$Note that $f^{f(n)}(n)$ and $f(f(n))$ must then both be odd since $n^2$ is odd. However, since we are assuming all odd positive integers less than $n$ are stuck, they cannot be less than $n$, and hence $$f^{f(n)}(n)=f(f(n))=n.$$Assume FTSOC that $f(n)\neq n$. Then, $ord(n)=2$, so $f(n)$ must be even since $ord(n)\mid f(n).$ Let $f(n)=2k,$ so $f(2k)=n.$ Then, $$f^{f(2k)}(2k)f(f(2k))=f^n(2k)(2k)=2kn,$$which is a contradiction. Hence, $f(n)=n$. Then, FTSOC assume that $f(z)=n$ for some other $z$. Then, $$f^n(z)f(f(z))=n^2,$$contradiction. Hence, $n$ is stuck. Thus, by induction, all odd positive integers are stuck. Therefore, $f(1000)$ cannot be odd. For a construction for even, let $f(1000)=2k$, $f(2k)=1000$, and $f(n)=n$ for all $n\notin\{2k,1000\}.$

Answer is evens, construction is $f(1000) = k, f(k) = 1000$, and everything else fixed point. Proof Odds Don't Work: First, $f(f(1)) \cdot f^{f(1)}(1) = 1 \implies f(f(1)) = 1$. Note that if any $a > 1$ has $f(a) = 1$, plugging in $a$ to the equation gives $1 = a^2$, obviously false. So if $f(1) = a > 1$, $f(a) = 1$ which isn't allowed so $f(1) = 1$. Next, we claim if $f(f(m)) = m$ and $f^{f(m)}(m) = m$ for an odd $m$, $f(m) = m$. Suppose for contradiction, $f(m) = n$ for an even $n$ as this implies $f(n) = m$ which when plugging in $n$ into the FE, gives a contradiction. Now, induct to prove $f(m) = m$ with base case proven. Suppose until $m - 2$ it's proven. The claim each each productand in $f^{f(m)}(m) \cdot f(f(m)) = m^2$ is $m$. Note that otherwise, one of them must be less then $m$ (and odd). Therefore, this implies at some point, $f(j) = M$ for $j \neq M$ for some odd $M < m$. However, plugging in $j$ into the FE, gives $M^2 = j^2$ clearly false, so we're done.

Very cool problem! First off, we claim injectivity of $f(x)$. Say $f(a) = f(b)$, $P(a)$, $P(b)$, yield $a^2 = b^2 \implies a = b$. It follows that $f^n(x)$ is injective as well. Now, we claim that $f(1) = 1$. $P(1)$ yields $f(f(1)) = 1$. $P(f(1))$ gives: $$f(f(1))f(1) = f(1) \implies f(1) = 1$$Now, we claim that $f(x) = x$ when $2 \nmid x$ by induction. Our base case is true, so say it's satisfied for $\{1, 3, \dots, x - 2\}$. We have: $$f(f(x)){f(f(\ldots f}_{f(x)\text{ times}}(x)\ldots)) = x^2$$As $f(1), f(3), \dots f(x - 2) = 1, 3, \dots, x - 2$, we have $f(f(x)), {f(f(\ldots f}_{f(x)\text{ times}}(x)\ldots)) > x - 2$, which implies $f(f(x)) ={f(f(\ldots f}_{f(x)\text{ times}}(x)\ldots)) = x$. This means that $f$ is an involution. Take $P(f(x))$ to get: $$f^{x + 1} (x) f(x) = f(x)^2 \implies f^{x + 1} (x) = f(x) \implies f^x (x) = x = f(f(x))$$As $x$ is odd and $f$ is injective, we get $f^{x - 2} (x) = x = f(f(x)) = f^{x - 4} (x) = \dots = f(x) = f(f(x))$. Due to injectivity, we have $f(x) = x$. This means that all evens must map to evens only (due to injectivity once more), hence $f(1000)$ must be even. Now, we can take a trivial construction to finish the problem (for evens): \[f(x) = \begin{cases*} 2\alpha & $x = 1000$\\ 1000 & $x = 2\alpha$ \end{cases*}\]Hence, we are done.

This typeup is kinda bad because I am salty I didn't type this up when I first solved it. Note that $f$ is clearly injective. Now we will strong induct over the odd numbers to show that $f(f(n))=n$ for all odd $n$. Base case $n=1$ is trivial, so assume that everything below $n$ works. Then if $f(f(n))<n$ we lose by injectivity, so assume FTSOC $f(f(n))>n$, so the LHS is less than $n$, say $k$. Then the only $x$ that can have $f(f(x))=k$ is $k$, so we have $f(n)=k$ is odd. But that means $f(k)=f(f(n))$ has to be odd, meaning that $f(k)=k$ (by plugging in $k$), contradiction. Now note that if an odd $n$ is not a fixed point, then the LHS requires $f(n)$ to be even, say $m$, but then $m$ is not a fixed point either, so we need $f(m)$ to be even, contradiction, so $f(n)=n$ for all odd $n$. Now we will handle the even numbers and prove that $f(f(n))=n$ also with induction. Note that if you map to an odd number, you lose, so $f(f(2))=2$. Then for the inductive step, note that if $f(f(n))<n$ then the LHS will be stuck at that value which is too small, while if $f(f(n))>n$ then the LHS neesd to be less than $n$ which is impossible by injectivity. We can see that the even numbers can be fixed points or paired. Thus the answers are all even numbers, with construction $f(1000)=2k$, $f(2k)=1000$, and $f$ is the identity for everything else. These clearly work. $\blacksquare$

We claim the set of all possible values of $f(1000)$ is the same as the set of even natural numbers. Note that if $k$ is odd, then $f^{f(k)}(k), f^{2}(k) \equiv 1 \pmod{2}$, if we plug in $n=f(k)$. we get $f(k)=f^{f(f(k))+1}(k) \equiv f^{k+1}(k) \equiv 1 \pmod{2}$, so if $f(k)$ is odd. If $f(a) \equiv 1 \pmod{2}$ for an even $a$, then $f(f(a))f^{f(a)}(a)$ is forced to be odd and cannot equal $a^2$ which is even, so for any even $a$, $f(a) \equiv 0 \pmod{2}$. Now for a construction take $f(x) =\begin{cases} a & x= 1000 \\ x & x \neq a\\1000 & x = a \end{cases}$ for any even natural number $a$, and our proof is complete. $\blacksquare$

We claim that $f(1000)$ can be $2k$ for any positive integer $k$.The construction is $f(1000)=2k$, $f(2k)=1000$, and $f(n)=n$ for all $n\ne 1000, 2k$. We claim that if $f^{f(a)}(a)=f(f(a))=a$ for some odd $a$, then $f(a)=a$. Assume FTSOC that $f(a)=k\ne a$ and $f(k)=a$. Since $f^k(a)=a$, we must have $2|k$. We must have $f^a(k)f(f(k))=k^2$ but this isn't true as $f^a(k)=a$ and $f(f(k))=k$, as desired. We claim that if $f(a)=a$, then $f(b)\ne a$ for all $b\ne a$. Assume FTSOC that $f(b)=a$. Then, $f^a(b)f(f(b))=a^2\ne b^2$, as desired. We claim that $f^{f(a)}(a)=f(f(a))=a$ for all odd $a$ so $f(a)=a$ for all odd $a$. This is true for $a=1$ it is the only way to factor $1^2$. We see that it is true for $a=p$ for odd primes $p$ as $1$ cannot be one of the factors of $p^2$. We see that it is true for $a=p^k$ for odd primes $p$ and integers $k\ge 2$ as $p^n$ cannot be one of the factors of $p^{2k}$ for $n<k$. We see that it is true for $a=pq^k$ for odd primes $p,q$ and integers $k\ge 1$ as a power of a prime cannot be one of the factors of $p^2q^{2k}$ and $pq^n$ cannot be one of the factors for $n<k$. In general, we can first induct on the number of primes, and to prove it true for a certain number of primes, we induct on the lexicographical order of exponents when written from least to greatest. Therefore, $f(a)=a$ for all odd $a$ and we are done. edit: after reading other sols, i should've just inducted on $a$ normally instead of inducting on the prime factorization weirdly oops...