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

3334 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 • 23 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, Funcshun840, krithikrokcs

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 • 6 Y

Y by HardySalmon, matinyousefi, megarnie, aaaa_27, Adventure10, Goodguy8809

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

6906 posts

v_Enhance

#4 h Apr 17, 2019, 11:04 PM • 76 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, Funcshun840, krithikrokcs

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 • 7 Y

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

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

23753 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

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

john0512

4194 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

1940 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

1070 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

4269 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

738 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

8904 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

109 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

5459 posts

peace09

#76 h Mar 17, 2025, 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

15 posts

jcoons91

#77 h Mar 17, 2025, 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

1772 posts

EpicBird08

#78 h Mar 17, 2025, 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, Mar 18, 2025, 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

161 posts

quantam13

#79 h Mar 19, 2025, 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

The post below has been deleted. Click to close.

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

ray66

113 posts

ray66

#80 h May 23, 2025, 3:55 PM

Y by

The answer is all even integers $k$ .

First we prove that $f$ is injective. Suppose that $f(a)=f(b)$ . Then $a^2 = f^{f(a)}(a) f^2(a) = f^{f(b)}(b) f^2(b) = b^2$ , so this implies $a=b$ .
Next we prove that $f(x)=x$ for all odd $x$ . We do this by induction. Let $P_x$ denote the assertion that $f(i)=i$ for all odd $I <x$ . Suppose that there exists an odd integer $x$ such that $f(x) \neq x$ , and assume that $P_x$ is true. Then one of $f^2(x)$ or $f^{f(x)}(x)$ must be an odd integer $k$ than $x$ because they multiply to $x^2$ . However $f$ is injective, so this would imply $x=k$ , contradiction. This completes the induction with base case $f(1)=1$ (because f(1) cannot map to any other odd number by test), so $f(x)=x$ for all positive odd integers $x$ .

This implies that $f(y)$ must map to an even integer for any even $y$ because $f$ is injective. Now to prove that $f(1000)$ ranges over all even numbers, consider $f(f(1000))=1000$ . Each even element is a part of a cycle of length 2, and this clearly works, so we finish.

Z K Y

The post below has been deleted. Click to close.

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

eg4334

745 posts

eg4334

#81 h Jun 24, 2025, 6:58 PM

Y by

We have $f^{f(n)}(n) f^2(n) = n^2$ . Obviously, $f$ is injective.

Next we find $f(1)$ . Note that $f(f(1))=1$ and $f^{f(1)}(1)=1$ . $f(1)=1$ works fine, and clearly $f(1)$ must otherwise be even. Now if $f(1)=2a$ then $f(2a)=1$ and we have $4a^2 = f^{f(2a)}(2a) f^2(2a)$ which is not true. Hence, $f(1)=1$ .

Then I claim $f(2k+1)=2k+1$ for all integers $k$ . We prove this using induction. We thus assume the statement is true for $0, 1, \dots, k-1$ . Then we have $f^{f(2k+1)}(2k+1) f^2(2k+1)=(2k+1)^2$ . Both terms on the LHS must be $2k+1$ . if, for the sake of contradiction some term is an odd number $a$ less than $2k+1$ . That then implies that $f(2k+1)=a$ which violates injectivity. Thus our induction is complete.

To show all even numbers work, $f(\text{odd}) = \text{odd}$ , $f(1000)=2k$ , $f(2k)=1000$ , and $f(\text{other evens}) = \text{other evens}$ works.

Z K Y