Convolution of order f(n)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trumpeter

3332 posts

trumpeter

#1 h Apr 17, 2019, 11:04 PM • 6 Y

Y by megarnie, HWenslawski, asdf334, aaaa_27, Adventure10, NicoN9

Let $\mathbb{N}$ be the set of positive integers. A function $f:\mathbb{N}\to\mathbb{N}$ satisfies the equation $\underbrace{f(f(\ldots f}_{f(n)\text{ times}}(n)\ldots))=\frac{n^2}{f(f(n))}$ for all positive integers $n$ . Given this information, determine all possible values of $f(1000)$ .

Proposed by Evan Chen

This post has been edited 1 time. Last edited by trumpeter, Apr 17, 2019, 11:36 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

william122

1576 posts

william122

#2 h Apr 17, 2019, 11:04 PM • 21 Y

Y by kingofgeedorah, Pathological, P_ksAreAllEquivalent, samuel, Ultroid999OCPN, Naruto.D.Luffy, mathleticguyyy, Illuzion, Aryan-23, IAmTheHazard, suvamkonar, centslordm, 554183, asdf334, supercarry, ApraTrip, Lamboreghini, mathboy100, Adventure10, NicoN9, aidan0626

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#3 h Apr 17, 2019, 11:04 PM • 5 Y

Y by HardySalmon, matinyousefi, megarnie, aaaa_27, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6858 posts

v_Enhance

#4 h Apr 17, 2019, 11:04 PM • 74 Y

Y by trumpeter, yayups, Ultroid999OCPN, Ashrafuzzaman_Nafees, RAMUGAUSS, fatant, mela_20-15, notverysmart, scrabbler94, reaganchoi, MortemEtInteritum, AngleChasingXD, Cyclic_Melon, reedmj, alex_g, samuel, Wizard_32, GeneralCobra19, matinyousefi, Spiralflux789, GAAB, Omeredip, Fermat_Theorem, mathleticguyyy, ftheftics, aops29, Polynom_Efendi, Imayormaynotknowcalculus, user0003, Unum, fjm30, RubixMaster21, Pendronator, Jerry122805, Ankoganit, mlgjeffdoge21, Aryan-23, akjmop, ETS1331, tapir1729, Illuzion, OlympusHero, Ayod19, ghu2024, v4913, HamstPan38825, 606234, tigerzhang, megarnie, justJen, math31415926535, rayfish, IMUKAT, 554183, ironpanther29, Atpar, Anandatheertha, bobjoe123, Inconsistent, Tang_Tang, bobthegod78, Lamboreghini, EpicBird08, mathboy100, sabkx, ihatemath123, OronSH, Adventure10, Deadline, Sedro, aidan0626, vrondoS, NicoN9, ray66

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$

Click to reveal hidden text

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.

This post has been edited 4 times. Last edited by v_Enhance, Feb 16, 2024, 5:45 PM
Reason: add sol in

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

62861

3564 posts

62861

#5 h Apr 17, 2019, 11:06 PM • 6 Y

Y by fatant, Vietjung, Imayormaynotknowcalculus, megarnie, aopsuser305, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

budu

1515 posts

budu

#6 h Apr 17, 2019, 11:07 PM • 4 Y

Y by kevinmathz, sabkx, Adventure10, Mango247

Will this get a point?

This post has been edited 1 time. Last edited by budu, Apr 17, 2019, 11:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yrnsmurf

20555 posts

yrnsmurf

#7 h Apr 17, 2019, 11:10 PM • 3 Y

Y by SpecialBeing2017, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Generic_Username

1088 posts

Generic_Username

#8 h Apr 17, 2019, 11:18 PM • 3 Y

Y by Imayormaynotknowcalculus, Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trumpeter

3332 posts

trumpeter

#9 h Apr 17, 2019, 11:19 PM • 3 Y

Y by Adventure10, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

goodbear

1108 posts

goodbear

#10 h Apr 17, 2019, 11:21 PM • 3 Y

Y by TheUltimate123, tapir1729, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sampai7

574 posts

sampai7

#11 h Apr 17, 2019, 11:30 PM • 1 Y

Y by Adventure10

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

This post has been edited 1 time. Last edited by sampai7, Apr 17, 2019, 11:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

goodbear

1108 posts

goodbear

#12 h Apr 17, 2019, 11:31 PM • 1 Y

Y by Adventure10

sampai7 wrote:

Generic_Username wrote:

Click to reveal hidden text

Are you sure there are countably many sequences? You can map the reals to sequences of integers right?

*infinite sequences, finite okay.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Generic_Username

1088 posts

Generic_Username

#13 h Apr 17, 2019, 11:33 PM • 2 Y

Y by Adventure10, Mango247

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$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aq1048576

32 posts

aq1048576

#14 h Apr 17, 2019, 11:35 PM • 4 Y

Y by Arrowhead575, Adventure10, Mango247, Mango247

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

f is an involution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathguy623

1855 posts

mathguy623

#15 h Apr 17, 2019, 11:39 PM • 2 Y

Y by budu, Adventure10

budu wrote:

Will this 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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bever209

1522 posts

bever209

#63 h Mar 18, 2023, 8:19 PM

Y by

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.

This post has been edited 1 time. Last edited by bever209, Mar 18, 2023, 8:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3430 posts

ihatemath123

#64 h May 22, 2023, 2:10 PM • 1 Y

Y by megarnie

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.

This post has been edited 3 times. Last edited by ihatemath123, May 22, 2023, 2:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4170 posts

john0512

#67 h May 27, 2023, 8:22 PM

Y by

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\}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi_is_3.14

1437 posts

pi_is_3.14

#68 h Jun 23, 2023, 1:51 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ATGY

2502 posts

ATGY

#69 h Feb 2, 2024, 8:57 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1867 posts

cj13609517288

#70 h Apr 16, 2024, 6:06 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

965 posts

bjump

#71 h Apr 18, 2024, 1:37 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4216 posts

RedFireTruck

#72 h Jun 27, 2024, 6:31 AM

Y by

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...

This post has been edited 2 times. Last edited by RedFireTruck, Jun 27, 2024, 2:26 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

298 posts

Ilikeminecraft

#73 h Mar 6, 2025, 3:30 PM

Y by

Claim: $f$ is injective
Proof: Assume $f(a) = f(b).$ Then, $a^2 = f(\dots f(a)) f(f(a)) = f(\dots f(b))f(f(b)) = b^2$ . Thus, $a = b$ since all of range/domain are positive.
Claim: $f(n) = n$ for all odd $n$
Proof: We prove this by induction. For the base case, note that if $f(1) = k,$ we have $f(k) = 1$ from $n = 1.$

Taking $n = k,$ we get $k = 1$ or $k^2,$ which tells us $k = 1.$ Now, assume $f(n) = k \neq n.$ We get that $f(k) f(\dots f(n)\dots) = n^2.$ Hence, if $k\neq n,$ then either $f(k) < n$ or $f(\dots f(n)\dots) < n.$ In the former case, this is impossible since this implies $f(k) = f(n).$ The latter case implies $n = k.$

Observe that any involution function $f$ works. Hence, we can take the construction:
$f \equiv \begin{cases} 2k & x = 1000 \\ 1000 & x = 2k \\ x & x \neq 2k, 1000 \end{cases}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8853 posts

HamstPan38825

#74 h Mar 15, 2025, 4:09 PM

Y by

The answer is all even integers $n$ .

Construction: Let $2n$ be any even positive integer, and consider a function $f$ defined by $f(1000) = 2n$ , $f(2n) = 1000$ , and $f(k) = k$ for all other positive integers $k$ .

Then, the assertion holds vacuously for $n = k$ . We also have $f^{f(1000)}(1000) = 1000$ and $f^{f(2n)}(2n) = 2n$ , so the assertion holds for $2n$ and $1000$ too, which completes the verification.

Bound: The main claim is the following:

Claim: For all odd positive integers $n$ , $f(n) = n$ .

Proof: We will perform a direct induction on the value of $n$ . For our base case, suppose $\eta(n) = 0$ , i.e. $n = 1$ . Then $f(f(1)) = 1$ ; let $u = f(1)$ , such that $f(f(u)) = u$ . The assertion applied to $u$ yields $uf(u) = f(u) f(f(u)) = u^2$ , hence $u = 1$ .

Now, for the inductive step, suppose that the result is true for all $n \leq k$ for a nonnegative integer $k$ . First, I claim that if $n \leq k$ and a positive integer $m$ satisfies $f^c(m) = n$ for a positive integer $c$ , then $m = n$ . It suffices to prove the case $c=1$ . Applying the given assertion to $m$ yields $n^2 = f^n (m) f(f(m)) = m^2$ as $n \geq 1$ , which yields $m = n$ , as needed.

Next, let $n$ be a positive integer and assume that $f(k) = k$ for all odd positive integers less than $n$ . Then, we have two cases:

If $f(f(n)) \neq f^{f(n)}(n)$ , then one of these two quantities is an odd integer $m$ strictly less than $n$ , as they multiply to $n^2$ . By the result we proved earlier and the inductive hypothesis, it follows $n = m$ , which is clearly impossible.
If $f(f(n)) = f^{f(n)}(n) = n$ , then $f(n)$ can be odd or even. If $f(n)$ is odd, then $n=f\left(f^{f(n) - 1}(n)\right) = f(n)$ and we have the result. If $f(n) = 2m$ is even, then applying the assertion to $2m$ yields $n = f^n(2m) = 2m$ , which is a clear contradiction.

Thus it follows that $f(n) = n$ too, which completes the proof. $\blacksquare$

So now assume that $f(1000) = n$ is an odd integer. Then $f^n(1000) = f(f(1000)) = n$ , hence $n = 1000$ , which is impossible. Thus $f(1000)$ must be even, and this concludes the proof.

This post has been edited 1 time. Last edited by HamstPan38825, Mar 15, 2025, 4:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chenghaohu

68 posts

chenghaohu

#75 h Mar 16, 2025, 3:07 AM

Y by

I claim that $f(1000)$ could be any even positive integer.

To show that there exist a function for $f(1000) = k$ , for every even positive integer $k$ , consider $f(x)$ such that $f(1000) = k$ , $f(k) = 1000$ , and $f(n) = n$ for all other integers $n$ . Then for all other integers $n$ , $f^k(n) = n$ for any positive integer $k$ , so indeed the definition of the function holds. Since $f(1000) = k$ is even, the LHS of the equation for $n = 1000$ becomes $1000$ , as $f^{2j}(1000) = 1000$ for all positive integers $j$ , so the given equation becomes $1000=\frac{1000^2}{1000}$ , which holds. Similarly, when we have $n = k$ , the $f^{2i}(k) = k$ for all positive integers $i$ , so the equation for $n = k$ becomes $k = \frac{k^2}{k}$ , which holds. Thus all the solutions we described have functions that satisfy them.

Now, I prove the following: If $f(a) = z$ , where $z$ is an odd number, then we must have that $a = z$ .

We do induction on the number of primes dividing $z$ with multiplicity.

The base cases are $z = 1$ and $z = p$ , where $p$ is an odd prime. $z = 1$ gives that $f(f(1)) = 1$ . If $f(1) = b$ , where $b$ is odd, then $\frac{b^2}{f(f(b))} = b = f(b) = 1$ , due to the fact that $f(b) = 1$ , forcing $b = 1$ . If $f(1) = c$ , where $c$ is even, then $\frac{c^2}{f(f(c))} = c = f(c) = 1$ , creating a contradiction. Thus $1$ is indeed the only $a$ such that $f(a) = a$ .

For $z = p$ , we have that $f(f(p)) = p$ is forced, as neither $f^{f(p)}(p)$ nor $f(f(p))$ can equal to $1$ . If $f(p) = a$ , where $a$ is odd, then $f(a) = p$ gives that $p = \frac{a^2}{a}$ , forcing $a = p$ . Similarly, if $a$ is even, we also force $a = p$ , creating contradiction. Thus the only $a$ such that $f(a) = p$ is $p$ . So we proved the base cases.

For the inductive step, let the inductive hypothesis be true for all $n$ which have $j$ primes dividing it, counting multiplicity. We will show that it also holds for all $n$ which have $j+1$ primes dividing it. By the inductive hypothesis, we must have $f(f(qn)) = qn$ for any $q$ a prime. If $f(qn) = b$ , where $b$ is odd, then $f(b) = qn$ gives that $qn = \frac{b^2}{b}$ , forcing $b = qn$ . Similarly, if $b$ is even, we also force $b = qn$ , creating contradiction. Thus the only positive integer $b$ such that $f(b) = qn$ is $b = qn$ , and by induction our claim holds.

Thus, we showed that $f(1000)$ cannot be odd, and we finished the problem.

This post has been edited 1 time. Last edited by chenghaohu, Mar 16, 2025, 3:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peace09

5411 posts

peace09

#76 h Monday at 9:27 PM

Y by

The answer is even integers.

Construction. Swap $2k$ with $1000$ and fix everything else; for $n=2k,1000$ we have
$f^{f(n)}(n)=f^{\text{even}}(n)=n=\tfrac{n^2}{n}=\tfrac{n^2}{f^2(n)}$ and other $n$ satisfy the FE clearly.

Necessity. We inductively show that each odd integer is its own unique preimage. For the base case, setting $n:=1$ implies that $f^2(1)\mid 1^2$ , and so $f^2(1)=1$ with $f(1)$ the unique preimage of $1$ . Then $n:=f(1)$ produces
$f^{f^2(1)+1}(1)=\tfrac{f(1)^2}{f^3(1)}\implies 1=\tfrac{f(1)^2}{f(1)}=f(1).$ Now, assume the inductive hypothesis holds for all odds less than some $m$ . Setting $n:=m$ gives $f^{f(m)}(m)f^2(m)=m^2$ , and since both the values on the LHS are odd, the inductive assumption implies that they are at least $m$ . So they are exactly $m$ , and in particular $f^2(m)=m$ with $f(m)$ the unique preimage of $m$ . Then $n:=f(m)$ results in
$f^{f^2(m)+1}(m)=\tfrac{f(m)^2}{f^3(m)}\implies f^{m+1}(m)=f(m),$ and since $m$ is odd the LHS becomes $m$ , completing the inductive step. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jcoons91

3 posts

jcoons91

#77 h Monday at 9:32 PM

Y by

We are given a function $f: 2\mathbb{N} \to 2\mathbb{N}$ that is an involution, meaning that applying $f$ twice returns the original input, i.e., $f(f(n)) = n$ . We claim that such a function must be of the form

$f(n) = \begin{cases} n, & \text{if } n \text{ is odd}, \\ g(n), & \text{if } n \text{ is even}. \end{cases}$
To establish this, we first demonstrate that $f$ is injective. Suppose that $f(a) = f(b)$ . Applying $f$ again, we get

$f(f(a)) = f(f(b)),$
which implies that $a = b$ due to the properties of an involution. Thus, $f$ is injective. Next, we show that $f$ is indeed an involution by considering a set $S = \{n, f(n), f(f(n)), f(f(f(n))), \dots\}$ and proving that $|S| \leq 2$ . Taking a minimal element $m$ in $S$ , we find that if $f(f(m)) < m$ , then $f(f(m))$ belongs to $S$ , contradicting the minimality of $m$ . If $f(f(m)) > m$ , then applying $f$ once more gives $f(f(m)) = \frac{m^2}{f(m)} < m$ , which is again a contradiction. Therefore, we must have $f(f(m)) = m$ , confirming the claim that $|S| \leq 2$ , which ensures $f$ is an involution.

Furthermore, we establish that $f$ maps even numbers to even numbers. If $f(2k)$ were odd, then applying $f$ twice would yield $f(f(2k)) = 2k$ , contradicting our assumption that $f(2k)$ was odd. Hence, $f(2k)$ must also be even. Finally, we verify that $f$ fixes all odd numbers. If $f(2k+1)$ were even, then applying $f$ would lead to a contradiction, as $f(\text{even}) = 2k+1$ contradicts our earlier finding that even numbers map to even numbers. If $f(2k+1)$ were odd, then applying $f$ twice gives $f(f(2k+1)) = 2k+1$ , ensuring $f(2k+1) = 2k+1$ , which confirms that odd numbers remain unchanged under $f$ . This completes the proof. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1732 posts

EpicBird08

#78 h Monday at 11:09 PM • 1 Y

Y by giratina3

Answer is all even positive integers; the construction is to let $f(n) = n$ for all $n$ but we swap $f(1000) = 2k$ and $f(2k) = 1000.$ This can be checked to work.

Now we will prove that all odd integers are fixed via induction. For the base case, we use $n=1$ to get $\frac{1}{f(f(1))}$ is an integer, so $f(f(1)) = 1.$ Using $n = f(1)$ gives $f^{f(f(1))} (f(1)) = f(f(1)) = 1 = \frac{f(1)^2}{f(f(f(1)))} = \frac{f(1)^2}{f(1)} = f(1),$ so $f(1) = 1.$

Now assume $f(n) = n$ for all odd $n \le 2k - 1.$ Using $n = 2k+1$ in the equation gives $f^{f(2k+1)} (2k+1) \cdot f(f(2k+1)) = (2k+1)^2.$ Clearly $f$ is injective, and one of the factors is at most $2k+1.$ If it were less than $2k+1,$ then it must be at most $2k-1,$ and spamming injectivity gives a contradiction. Thus $f(f(2k+1)) = 2k+1.$ Using $n = f(2k+1)$ gives $f^{f(f(2k+1))} (f(2k+1)) = f^{2k+2} (2k+1) = \frac{f(2k+1)^2}{f(f(f(2k+1)))}.$ Since $f^{2k+2} (2k+1) = 2k+1$ and $f(f(f(2k+1))) = f(2k+1),$ we get $f(2k+1) = 2k + 1.$ This completes the induction, so $f(n) = n$ for all odd $n.$ In particular, since $f$ is injective, $f(1000)$ can never be odd, as desired.

Motivation

This post has been edited 2 times. Last edited by EpicBird08, Yesterday at 1:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

quantam13

90 posts

quantam13

#79 h Today at 3:04 AM

Y by

The answer is all even integers $k$ , which can be achieved by setting $f(1000)=2k$ , $(2k)=1000$ and making $f$ fix everything else, which clearly works.

Now to see that it can only achieve even numbers, firstly notice that $f$ is both injective and surjective. Thus it suffices to prove that $f$ fixes all odd numbers. Though this is not so hard with a simple induction.

Z K Y