Bijection on the set of integers

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Bijection on the set of integers

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: InfinityDots MO 2 Problem 2

The post below has been deleted. Click to close.

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

276 posts

talkon

#1 h Apr 9, 2018, 3:12 PM • 10 Y

Y by SAUDITYA, ThE-dArK-lOrD, SHREYAS333, anantmudgal09, Smita, Ankoganit, Mathuzb, Omeredip, GeoMetrix, Adventure10

Determine all bijections $f:\mathbb Z\to\mathbb Z$ satisfying
$f^{f(m+n)}(mn) = f(m)f(n)$ for all integers $m,n$ .

Note: $f^0(n)=n$ , and for any positive integer $k$ , $f^k(n)$ means $f$ applied $k$ times to $n$ , and $f^{-k}(n)$ means $f^{-1}$ applied $k$ times to $n$ .

Proposed by talkon

Z K Y

The post below has been deleted. Click to close.

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

250 posts

#2 h Apr 9, 2018, 3:14 PM • 3 Y

Y by zephyr7723, Adventure10, Mango247

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

698 posts

#4 h Apr 9, 2018, 6:19 PM • 2 Y

Y by Adventure10, Mango247

Let $f^{-1}=g$ . Let $c=f(0)$ . Suppose that $c\neq 0$ . Let $P(m,n)$ be the assertion $f^{f(m+n)}(mn) = f(m)f(n)$ .
$P(0,g(n))\implies f^n(0)=nf(0)=cn \implies c(n+1)=f^{n+1}(0)=f(cn)\implies f^k(nc)=f^{n+k}(0)=c(n+k)$ $P(m+c,-c)\implies f^{f(m)}(-c(m+c))=0\implies c(f(m)-m-c)=0 \implies f(m)=m+c$ Let $c=0$ . Letting $n=-m$ we have that $f(m)f(-m)=-m^2 \implies f(1)f(-1)=-1$ . Suppose that $f(1)=1$ . Let $p$ be a prime.
$P(p,-p) \implies f(p)f(-p)=-p^2 \stackrel{\text{injectivity}}{\implies} f(-p)=-f(p)$ $f(-m)=-f(m) \stackrel{\text{P(m,-1)}}{\Longleftrightarrow} f^{f(m-1)-1}(-m)=-m \Longleftrightarrow f^{f(-m-1)-1}(m)=m \stackrel{\text{P(m,1)}}{\Longleftarrow} f(-m-1)=-m-1$ Now apply Cauchy induction with base cases large primes, thus we have that $f(n)=-f(-n)\implies f(n)=\pm n$ . If there exists $u\in \mathbb{Z}/\{0\}$ such that $f(u)=-u$ , then by letting $m=u$ and $n\equiv_2 u$ we see that $f(n)=-n$ , and now by looking at $P(2k+1-u,u)$ we see that $u$ must be even and we have the solution $f(m)=(-1)^{m+1}m$ . If there doesn't exist such $u$ , then $f(m)=m$ . The case $f(1)=-1$ can be treated in the same way, but using simple induction instead of Cauchy, the latter case producing any solutions.
To sum up: the solutions are $f(m)=m+c$ , $f(m)=(-1)^{m+1}m$ , where $c\in \mathbb{Z}$ is a constant.

This post has been edited 1 time. Last edited by rmtf1111, Apr 9, 2018, 6:20 PM

Z K Y

The post below has been deleted. Click to close.

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

1979 posts

#5 h Apr 9, 2018, 9:10 PM • 1 Y

Y by Adventure10

I wonder what was the proposer's motivation

#2 wrote:

Determine all bijections $f:\mathbb Z\to\mathbb Z$ satisfying
$f^{f(m+n)}(mn) = f(m)f(n)$ for all integers $m,n$ .

Note: $f^0(n)=n$ , and for any positive integer $k$ , $f^k(n)$ means $f$ applied $k$ times to $n$ , and $f^{-k}(n)$ means $f^{-1}$ applied $k$ times to $n$ .

#2

This post has been edited 2 times. Last edited by anantmudgal09, Apr 9, 2018, 9:20 PM

Z K Y

The post below has been deleted. Click to close.

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

276 posts

talkon

#6 h Apr 12, 2018, 7:41 PM • 2 Y

Y by anantmudgal09, Adventure10

Answer: the infinite family of functions $n\mapsto n+c$ for any integer $c$ , and the function $n\mapsto (-1)^{n+1}n$ .

Official Solution. We consider two cases, depending on the value of $f(0)$ .

Case 1: $f(0)=0$ .

By plugging in $(m,n)=(k,-k)$ , we have $-k^2 = f(k)f(-k)$
for all integers $k$ . Since $f$ is bijective, by induction on $k$ , $\{f(k),f(-k)\} = \{k,-k\}$
for all positive integers $k$ . Hence $f(f(n))=n$ for all integers $n$ .

Now suppose that $m,n$ are integers with the same parity, so $f(m+n)$ is even. Hence,
$mn=f^{f(m+n)}(mn) = f(m)f(n),$ so either both $f(m)=m$ and $f(n)=n$ or $f(m)=-m$ and $f(n)=-n$ . Therefore there are four solutions left to check: $n\mapsto n, n\mapsto -n, n\mapsto (-1)^nn$ , and $n\mapsto (-1)^{n+1}n$ , and by considering $m$ even and $n$ odd, we can see that only two work: $n\mapsto n$ and $n\mapsto (-1)^{n+1}n$ .

Case 2: $f(0)\neq 0$ .

Plug in $(m,n)=(f^{-1}(k),0)$ to get $f^k(0)=kf(0)$ for all integers $k$ . In particular, when $k=-1$ we have $f^{-1}(0) = -f(0)$ . Now substitute in $(m,n)=(m,-f(0))$ to get, for all integers $m$ ,
$f^{f(m-f(0))}(-mf(0)) = 0. \qquad \text{\_\_\_ (1)}$
Now note that the orbit $\ldots\to f^{-2}(0)\to f^{-1}(0)\to 0\to f(0)\to f(f(0))\to\ldots$ contains all multiples of $f(0)$ , so it is unbounded and not periodic. Hence from

$f^{f(n)-n-f(0)}(0) = f^{f(n)}\big(f^{-n-f(0)}(0)\big)= f^{f((n+f(0))-f(0))}\big((-n-f(0))\cdot f(0)\big) = 0$ where the second equation follows from $f^k(0)=kf(0)$ and the third equation follows from (1), we have $f(n)-n-f(0)=0$ for all integers $n$ . Hence the function $f$ must be of the form $n\mapsto n+c$ for some constant $c$ , and it's easy to see that all such functions work. $\blacksquare$

Comments. There are several possible ways to proceed in Case 2. For example, another way is to plug in $m=0, f(0)$ and $2f(0)$ .

anantmudgal09 wrote:

I wonder what was the proposer's motivation

Let's say I've always liked FEs with expressions like $f^{f(x)}$ , so from the equation
$mn + k(m+n+k) = (m+k)(n+k)$ there is the natural equation
$f^{f(m+n)}(mn) = f(m)f(n).$ As for the bijection condition, first I actually thought about the above equation in $\mathbb Z^+$ without getting anything, and when I revisited it later I just somehow thought that making it a bijection will allow changing the equation to $\mathbb Z$ and that worked out perfectly. The solution $n\mapsto (-1)^{n+1}n$ wasn't planned but it just popped out, which in my opinion makes it even nicer.

This post has been edited 1 time. Last edited by talkon, Apr 12, 2018, 7:42 PM

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#7 h Aug 19, 2019, 4:10 AM • 2 Y

Y by Adventure10, Mango247

We claim the solutions are $f(x)=x+c$ and $f(x)=(-1)^{x+1}x$ , both of which can easily be checked to work.

Now suppose that $f$ is some solution to the FE $P(m,n)$ . Let's start by solving the problem assuming $f(0)\ne 0$ . Note that
$P(m,0)\implies f^{f(m)}(0)=f(m)f(0)\implies \boxed{f^x(0)=xf(0)}$ for all $x$ , since $f$ is bijective so $f(m)$ is any integer $x$ .

Let $a=f^{-1}(0)=-f(0)$ . Then, we have
$f^{f(m+a)}(ma)=0\implies ma=f^{-f(m+a)}(0)\implies -mf(0)=-f(0)f(m+a),$ so $f(m+a)=m$ , or $f(m)=m-a=m+f(0)$ , so $f(x)=x+c$ for some $c\ne 0$ .

We will now assume that $f(0)=0$ . We have that
$P(n,-n)\implies f^0(-n^2)=f(n)f(-n)\implies\boxed{f(n)f(-n)=-n^2}.$ In particular, $f(1)f(-1)=-1$ , so $\{f(1),f(-1)\}=\{1,-1\}$ .

We claim that $\{f(n),f(-n)\}=\{n,-n\}$ , where we prove this by induction. The base case of $n=1$ is clear. Now suppose $\{f(m),f(-m)\}=\{m,-m\}$ for all $m<n$ . Then, if $f(n)\ne\pm n$ , we must have one of $f(n)$ or $f(-n)$ have absolute value $0<m<n$ . But if $f(\pm n)=\pm m$ , then $\pm n=\pm m$ for some choice of signs since $\pm m=f(\pm m)$ , which is a contradiction. Thus, $\{f(n),f(-n)\}=\{n,-n\}$ . This also implies that $f^2(x)=x$ .

Thus, if $m$ and $n$ are of the same parity, then $P(m,n)$ implies $mn=f(m)f(n)$ , so $f(m)/m$ and $f(n)/n$ are the same. Therefore, by fixing the values of $f(1)$ and $f(2)$ , we uniquely determine $f$ . The four choices give us
$f(x)\equiv x,-x,(-1)^xx,(-1)^{x+1}(x).$ One can check that only the first and the last work, which solves the problem.

Z K Y

The post below has been deleted. Click to close.

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

1576 posts

#8 h Oct 4, 2019, 10:58 PM • 2 Y

Y by Adventure10, Mango247

Denote the assertion as $P(m,n)$ . Suppose that $f(0)=0$ . Then, $P(m,-m)$ yields $-m^2=f(m)f(-m)$ . Plugging in $m=1$ , we get $f(1)f(-1)=-1$ , so $\{f(1),f(-1)\}=\{-1,1\}$ . Similarly, $f(2)f(-2)=-4$ . However, since neither can have magnitude $1$ , due to injectivity, we must have $\{f(2),f(-2)\}=\{2,-2\}$ . We can induct upwards to get $f(x)=\pm x\forall x$ , and $f(f(x))=x$ . Now, if we consider $P(m,n)$ for $2|m+n$ , note that LHS is just $mn$ , so $f(m),f(n)$ must be $m,n$ or $-m,-n$ , implying that we take the same sign for all numbers of the same sign. Checking the 4 cases yields the solutions $f(x)=x$ and $f(x)=\begin{cases}x\text{ if }x\equiv 1\pmod 2\\ -x\text{ otherwise}\end{cases}$ .

If $f(a)=0$ for $a\neq 0$ , consider $P(a,n)$ . We have $f^{f(a+n)}(an)=0$ . Thus, there exists some $k$ for all multiples of $a$ , $an$ , such that $f^k(an)=0$ . Furthermore, since $f$ is a bijection, $f(a+n)$ cycles through all the integers, implying that $f^k(0)$ for any $k$ is always a multiple of $a$ . Now, consider $P(am,a(1-m))$ . Similar to before, we get the relation $a^2m(1-m)=f(am)f(a(1-m))$ , and using the fact that $a|f(am),f(a(1-m))$ , we get a similar induction as before, yielding $f(ax)=-ax$ or $(a-1)x$ . Now, if we take $2|x+y$ , and consider $P(ax,ay)$ , we get $a^2xy=f(ax)f(ay)$ . Checking all 4 cases (i.e. $f(ax)=-ax,(a-1)x$ , $f(ay)=-ay,(a-1)y$ ), we find that the only solution is if $f(ax)=(a-1)x$ , $f(ay)=(a-1)y$ . So, we get that $f(ax)=(a-1)x\forall x$ . Finally, note that we had $f^{f(a+n)}(an)=0$ . The previous statement tells us, however, that $f^n(an)=0$ . As $0$ does not occur in a cycle (i.e. there does not exist $k$ such that $f^k(0)=0$ ), we must have that $n=f(a+n)$ , or $f(x)=x-a$ . All $a$ produce valid solutions.

Thus, our solution set is $f(x)=x+c$ for $c\in\mathbb{Z}$ , and $f(x)=\begin{cases}x\text{ if }x\equiv 1\pmod 2\\ -x\text{ otherwise}\end{cases}$ .

Z K Y

The post below has been deleted. Click to close.

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

206 posts

#9 h Oct 14, 2019, 2:20 PM • 1 Y

Y by Adventure10

We divide into two cases: $f(0)=k\neq 0$ or $f(0)=0$ .

If $f(0)=k\neq 0$ , plug in $m=0 \Longrightarrow f^n(0)=kn$ $\forall n\in\mathbb{Z}$ , which implies $f(nk)=(n+1)k$ . Specially, $f(-k)=0$ . Plug in $n=-k$ , then we have $f^{f(m-k)}(-mk)=0$ , and since $f$ is bijective we have $f(m-k)=m$ . This gives us one solution: $f(m)=m+k$ for all $m$ .

If $f(0)=0$ , then plug in $n=-m$ we get $f(m)f(-m)=-m^2$ . By induction we see that $|f(m)|=m$ and $f(m)=-f(-m)$ . If $m+n$ is even, then by the original equation $mn=f(m)f(n)$ , meaning that if $m\equiv n\mod 2$ , then $f(m)$ and $f(n)$ have the same signs. If $m+n$ is odd (let's say $m$ is even and $n$ is odd), then $f(mn)=f(m)f(n)$ . This gives us two solutions $f(x)=x$ and $f(x)=(-1)^{x+1}x$ .

Z K Y

The post below has been deleted. Click to close.

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

691 posts

#10 h Jan 24, 2020, 8:27 AM • 1 Y

Y by Adventure10

The solutions are $f(n) = n + c$ and $f(n) = (-1)^{n + 1} \cdot n$ . It is easy to check that both of them satisfy. Now we'll prove that those are the only ones.
Let $P(m,n)$ denote the assertion of $m$ and $n$ to the given functional equation.
$P(m,n) : f^{f(m+n)} (mn) = f(m) f(n)$ We'll consider two cases:
$\textbf{Case 01.}$ When $f(0) = 0$ .
$P(m,-m) : -m^2 = f^{f(0)}(-m^2) = f(m)f(-m)$ Simple induction gives us $\{ f(m), f(-m) \} = \{ -m, m \}$ for all $m \in \mathbb{N}$ . In both case, we get $f(f(m)) = m$ .

Take $m,n$ such that $m+n$ even, then
$mn = f^{f(m+n)} (mn) = f(m) f(n)$

Suppose that $f(1) = 1$ , then we have
$f^{f(m+1) - 1} (m) = m$ If $m$ is odd, then $f(m+1) - 1$ is odd, this gives us $f(m) = m$ .
Hence, if $f(2) = 2$ , then $f(n) = n$ for all even $n$ . This gives us the solution $\boxed{f(x) = x}$ which is indeed true.

If $f(2) = -2$ , then $f(n) = -n$ for all even $n$ . This gives us the solution $\boxed{f(x) = (-1)^{x+1} \cdot x}$ which is indeed true.

Suppose that $f(1) = -1$ , then $f(x) = -x$ for all odd $x$ . Similar reasoning as before, we gain two possible functions: $f(x) = -x$ or $f(x) = (-1)^x \cdot x$ .
Take $m$ and $n$ having different parity, this gives us
$mn = f^{f(m+n)} (mn) = f(m) f(n) = -mn$ for the latter case and
$-mn = f^{f(m+n)}(mn) = f(m) f(n) = mn$ for the former case.

$\textbf{Case 02.}$ When $f(0) \not= 0$ , then suppose that $f(c) = 0$ for $c \not= 0$ .
$P(k,0)$ gives us
$f^{f(k)}(0) = f(k)f(0)$ By surjectivity, we have $f^m (0) = mf(0)$ for all $m \in \mathbb{Z}$ .
$f^{f(m+n)}(mn) = f(m)f(n)$ $P(m, -f(0))$ gives us
$f^{f(m - f(0))} (-mf(0)) = f(m) f(-f(0)) = f(m)f(f^{-1} (0)) = 0$ We then have
$f^{f(m - f(0))} ( f^{-m} (0) ) = 0$ Hence, $0 = f^{f(m - f(0)) - m} (0) = ( f(m - f(0)) - m)f(0)$ , which gives us $f(m - f(0)) = m$ for all $m \in \mathbb{Z}$ . This gives the solution $\boxed{ f(n) = n + c}$ , which satisfies the original equation.

This post has been edited 1 time. Last edited by IndoMathXdZ, Jan 24, 2020, 8:44 AM

Z K Y

The post below has been deleted. Click to close.

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

2726 posts

#11 h Mar 19, 2020, 7:53 PM • 2 Y

Y by cosmicgenius, Mango247

Solution w/ cosmicgenius

Let $P(n, m)$ be the assertion. We repeatedly take advantage of the fact that $f$ is bijective. $P(f^{-1} (a), 0)$ gives $f^a (0) = af(0)$ for all integers $a$ . Thus $f^{-1} (0) = -f(0)$ and $f(-f(0))= 0$ . Furthermore, $P(-f(0), x)$ gives
$f^{f(-f(0)+x)} (-f(0)x) = 0.$ But the LHS can be simplified as follows: $\begin{align*} f^{f(-f(0)+x)} (-f(0)x) &= f^{f(-f(0)+x)} (-xf(0))\\&= f^{f(-f(0)+x)} (f^{-x} (0))\\&= f^{-x + f(-f(0)+x)} (0)\\&= f(0) (-x + f(-f(0)+x)) = 0\end{align*}$ where we repeatedly took advantage of $P(f^{-1}(a), 0)$ . Hence, for each individual $x$ , we must have $f(x - f(0)) = x$ or $f(0)=0$ . If $f(0) \neq 0$ , then we must have $f(x - f(0)) = x$ for all $x \in \mathbb{Z}$ , which yields the solutions $f(x) = x + c, c \in \{\mathbb{Z}^+, \mathbb{Z}^-\}$ for nonzero integers $c$ .

If $f(0) = 0$ , then $P(x, -x)$ gives $-x^2 = f(x)f(-x)$ . From $x = 1$ , note that $f(1)f(-1) = -1$ , hence $f(-1), f(1) \in \{-1, 1\}$ since $f$ brings integers to integers. In fact, we can show that, for all integers $n$ , $f(-n), f(n) \in \{-n, n\}$ . We only have to consider positive $n$ , since then negative $n$ must follow by symmetry and $f(0) = 0$ is already assumed.

We will use strong induction. Our base cases of $n = 1, 2$ are obvious. For the inductive step, assume that for all positive integers $n < k$ , $f(-n), f(n) \in \{-n, n\}$ . $P(k, -k)$ yields $-k^2 = f(k)f(-k)$ . If $|f(k)| > k$ , then $|f(-k)| < k$ , a contradiction since all integers in the range $(-k, k)$ are already attained by $f$ at some value $v \in (-k, k)$ . For the same reason, $|f(k)| < k$ cannot hold. Hence, we must have $|f(k)| = |f(-k)| = k$ as desired. $\square$

Thus, for all $n \in \mathbb{Z}$ , $f(n) = -n$ or $n$ , so $f(f(n)) = f^2(n) = n$ . Now, back to the original assertion $P$ , consider all pairs $(m, n)$ with same parity $\implies m+n$ even. $f^{f(m+n)}(mn) = mn = f(m)f(n)$ . Either $f(m) = m$ and $f(n) = n$ , or $f(m) = -m$ and $f(n) = -n$ . Now, we just have to consider all four possibilities regarding $f(1) \in \{-1, 1\}$ and $f(2) \in \{-2, 2\}$ . Checking all such possibilities, we see that it is only possible for $f(1) = 1$ and $f(2) = 2$ , or $f(1) = 1$ and $f(2) = -2$ , hence the solutions $f(x) = x$ and $f(x) = x$ when $x$ odd and $f(x) = -x$ when $x$ even.

in summary, our solutions are $\boxed{f(x) = x + c, c \in \mathbb{Z}}$ , and $\boxed{f(x)=\begin{cases} x &\text{ if } x \text{ is odd} \\ -x &\text{ if } x \text{ is even} \end{cases}}$ , as desired. $\blacksquare$

This post has been edited 3 times. Last edited by jj_ca888, Mar 19, 2020, 7:56 PM

Z K Y

The post below has been deleted. Click to close.

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

1671 posts

pad

#13 h Sep 2, 2020, 9:12 PM

Y by

Let $P(m,n)$ denote the FE. Note $P(m,0)$ gives $f^{f(m)}(0)=f(m)f(0)$ , and since $f$ is surjective, $f^x(0)=xf(0)$ for any $x$ . In particular,

$f^{-1}(0)=-f(0)$ , i.e. $f(-f(0))=0$ , and
$0=f^{-x}(xf(0))$ , so $f^y(-yf(0))=0$ for any $y$ .

Now, $P(m+f(0),-f(0))$ gives $f^{f(m)}\big( -f(0)(m+f(0)) \big) =0.$ But $f^{f(m)}(-f(m)f(0))=0$ by using the second bullet above. Since $f$ is bijective, this implies $-f(m)f(0)=-f(0)[m+f(0)]$ . If $f(0)\not = 0$ , then $f(m)=m+f(0)$ , i.e. $f(m)=m+c$ for some constant $c$ . It is easy to check that this works in general.

Now assume $f(0)=0$ . $P(n,-n)$ gives $-n^2=f(n)f(-n).$ Let $g(n)=|f(n)|$ . Then $g(n)\ge 0$ and $n^2=g(n)g(-n)$ for all $n$ . We claim $g(n)=|n|$ for each $n$ . Induct on $|n|$ . For $n=1$ , $1=g(1)g(-1)$ , so $g(1)=g(-1)=1$ . WLOG $n$ is positive. We have $g(n)=k$ and $g(-n)=n^2/k$ for some positive $k\mid n^2$ . If $k\not = n$ , then WLOG $k<n$ . But $g(k)=|k|=k$ , contradicting injectivity. Hence $g(n)=|n|$ , i.e. $f(n)=\pm n$ for each $n$ .

So $\{f(n),f(-n)\}=\{n,-n\}$ , which implies $f(-n)=-f(n)$ .
If $f(n)=n$ , then $f(f(n))=f(n)=n$ , and if $f(n)=-n$ , then $f(f(n))=f(-n)=-f(n)=n$ . In all cases, $f(f(n))=n$ .
Now, if $m+n$ even, then $mn=f(m)f(n)$ .

So if $s(n)=f(n)/n$ , then $s(m)=s(n)$ for $m\equiv n \pmod2$ . If $s(1)=1$ and $s(2)=1$ , then $f(n)=n$ . If $s(1)=1$ and $s(2)=-1$ , then $s(n)=(-1)^{n+1}$ , i.e. $f(n)=(-1)^{n+1}n$ . The other two cases are symmetric.

In conclusion, the solutions are $f(n)=n+c, \qquad f(n)=(-1)^{n+1}n,$ for any $c$ , both of which work.

Remarks

This post has been edited 3 times. Last edited by pad, Sep 2, 2020, 9:14 PM

Z K Y

The post below has been deleted. Click to close.

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

1065 posts

Eyed

#14 h Dec 22, 2020, 9:19 PM • 2 Y

Y by kevinmathz, RedFlame2112

The two solutions are $f(x) = x + c$ , or $f(x) = x$ for odd $x$ and $f(x) = -x$ for even $x$ . It's not hard to see that these both work.

If $f(x) = 1, f(y) = 0$ , we have $f(m(x-m)) = f(m)f(x-m)$ , $m(y-m) = f(m)f(y-m)$
$f(y(x-y)) = 0$ , so by bijectivity, $y(x-y) = y$ . Either $y = 0, x = y+1$ .

If $y = 0$ , we have $-m^{2} = f(m)f(-m)$ , so $f(1) = \pm1$ and $x = \pm1$ . If $x = -1$ , then $f(m(-1-m)) = f(m)f(-1-m)$ , plug in $m = 1$ for contradict.
Thus, $y = 0, x = 1$ , $f(0) = 0, f(1) = 1, f(-1) = -1$ . inducktively, prove that $f(x) = \pm x$ (true through bijectivity), (induckt on $x$ ). Repeat proof that if $x$ odd, then $f(x) = x$ , otherwise $f(x)$ can be either $x$ or $-x$ .

If $x = y+1$ , we have $x(y-x) = f(x)f(y-x)$ implies $f(-1) = -x$ , also $1(y-1) = f(1)f(y-1)$ so $x | y-1, y+1 | y-1$ . Take some $n$ such that $f(n) = -1$ , then $f^{-1}(0) = f(0)(-1) \Rightarrow f(0) = -y$ . Observe that
$f^{f(n)}(0) = f(n)f(0) = f(n)\cdot -y, f^{c}(0) = c\cdot -y$ We can prove $f(ky) = (k-1)y$ for integer $k$ , by inducktion. Our base case is $k = 1$ , which is true since $f(y) = 0$ . Now, assume it's true for $k$ , we will prove that it is true for $k + 1$ . Using the observation, since $f^{-k}(0) = ky$ , this means
$f^{-1}(f^{-k}(0)) = f^{-1}(ky) = f^{-k-1}(0) = (k+1)y$ This implies $f((k+1)y) = ky$ .

Now we can prove $f(ky + 1) = (k-1)y + 1$ . This is because, consider $m = y+1, n = (k-1)y$ . Now,
$f^{f(ky + 1)}(y(k-1)(y+1)) = y((k-1)(y+1) - f(ky+1))$ $= f(y(k-1))f(y+1) = y(k-2)$ This means $ky - y + k - 1 - (k-2) = f(ky+1) = (k-1)y + 1$ . A useful corollary is $f^{r}(ky + 1) = (k-r)y + 1$ .

Now, we will use inducktion on $r$ . to show that $f(ky + r) = y(k-1) + r$ . Our base case is already proven, for $r = 0, 1$ . Assume that it is true for all $i < r$ , such that $f^{c}(ky + i) = (k-c)y + i$ . We prove the same for $r$ . We have:
$f^{f(ky + r)}(((k-1)y + (r-1))(y + 1)) = f((k-1)y+(r-1))f(y+1)$ $= f((k-1)y+(r-1)) = (k-2)y + r-1$ $= f^{f(ky + r)}(y((k-1)y + (r-1) +(k-1)) + (r-1))$ $= y((k-1)y + (r-1) + (k-1) - f(ky + r)) + r-1$ $\Longrightarrow f(ky + r) = (k-1)y + (r-1) + (k-1) - (k-2) = (k-1)y + r$ Thus, our inducktive step is proven.

We conclude that $f(x) = x - y$ . Thus, our only two solutions are the ones listed here.

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7305 posts

DottedCaculator

#15 h Sep 26, 2021, 3:13 PM • 2 Y

Y by centslordm, RedFlame2112

Solution

Z K Y

The post below has been deleted. Click to close.

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

1385 posts

#16 h Aug 7, 2023, 9:22 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

654 posts

#17 h Dec 25, 2023, 6:44 AM

Y by

Observe that $f(x)=x+k$ works. Furthermore, if $f(0)=k\ne 0$ , then we get $f^{f(m)}(0)=kf(m)$ . Now, as $f$ is a bijection, we can replace $f(m)$ with $m$ , and we get $f^{m}(0)=km$ . Then $f(x)=x+k$ holds for $x=km$ . Then plugging in $n=-k$ , we get $f^{f(m-k)}(-km)=0=f^{m}(-km)$ . so $f(m-k)=m$ for all $m$ , thus implying that we have $f(x)=x+k$ . Hence this is the only solution unless $f(0)=0$ .

We now take the $f(0)=0$ case: then $m=-n$ gives $-m^2=f(m)f(-m)$ . Now, we claim that we have $|f(\pm k)|=k$ where $k\ge 0$ . Suppose not. First observe that for $k=0$ this holds and for $k=1$ this must also hold from $m=1$ implying $-1=f(m)f(-m)$ and $1$ and $-1$ are the only divisors of $-1$ . Thus, taking the smallest counterexample for $k$ , we have $k\ge 2$ . Then $f(k)f(-k)=-k^2$ . Now, as $k$ is the smallest counterexample, we know that $|f(k)|\ge k$ as all values with lower absolute value are mapped to values with those absolute values and are thus in orbits with values of lower absolute value. Similarly, $|f(-k)|\ge k$ . Now, at least one of these inequalities must be strict in order for $k$ to be a counterexample, but this contradicts $f(k)f(-k)=-k^2$ . Thus, we have $|f(\pm k)|=k$ . Now, we just need to determine when $f(x)=x$ and when $f(x)=-x$ . Observe that if $m$ and $n$ have the same parity, the original FE just says that $mn=f(m)f(n)$ indicating that either there is a sign change for both $m$ and $n$ or for neither. Thus, sign change or not is dependent only on the parity of the input. For $m+n$ odd, the original FE just says $f(mn)=f(m)f(n)$ . Now say $m$ is the even one and $n$ is the odd one; then $f(mn)$ and $f(m)$ are either both sign changed or both left alone so $f(n)=n$ (assuming we choose $m$ to be not $0$ which we may do). Thus, $f$ of any odd number is equal to that number and then we can either have the same be true for evens or we can have it such that $f$ of any even is negative that even. This is two possible solutions for $f$ ; we see that both work.

Z K Y

The post below has been deleted. Click to close.

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

1868 posts

#18 h Apr 11, 2024, 8:35 PM

Y by

The answer is $\boxed{f(x)=x+c}$ for all integers $c$ , along with
$\boxed{f(x)=\begin{cases}x&x\text{ is odd}\\-x&x\text{ is even}\end{cases}}\,.$ These "clearly" work(the last function is easier to check after the reductions in case 2). For the proof, we split into cases.

Case 1. $f(0)\ne 0$ . Let $f(0)=c$ . Then $P(m,0)$ gives
$f^{f(m)}(0)=cf(m)\Longrightarrow f^m (0)=cm.$ Thus the chain through $0$ goes $\cdots\rightarrow -2c\rightarrow -c\rightarrow 0\rightarrow c\rightarrow 2c\rightarrow\cdots$ .

Now $P(m,c)$ gives
$f^{f(m+c)}(mc)=f(m)f(c)\Longrightarrow mc+cf(m+c)=2cf(m)\Longrightarrow m+f(m+c)=2f(m).$ Let $g(x):=f(x)-x-c$ . Then
$m+g(m+c)+m+2c=2g(m)+2m+2c\Longrightarrow g(m+c)=2g(m).$ Thus by $\nu_2$ we have $g\equiv 0$ , so $f(x)=x+c$ for all $x$ , which works.

Case 2. $f(0)=0$ . Then $P(m,-m)$ gives $-m^2=f(m)f(-m)$ . Therefore, $\{f(1),f(-1)\}=\{1,-1\}$ , so $\{f(2),f(-2)\}=\{2,-2\}$ , so $\{f(3),f(-3)\}=\{3,-3\}$ , etc, so $f(m)=\pm m$ for all $m$ . Therefore, $f^2(m)=m$ for all $m$ , so the two possible values of $f(m+n)$ do the same thing. Therefore,
$f^{m+n}(mn)=f(m)f(n).$ Let $g(n):=\frac{f(n)}{n}$ be defined for all nonzero integers. Then
$g(mn)^{m+n}=g(m)g(n).$ If $m$ and $n$ have the same parity, then $g(m)g(n)=1$ . Therefore, $g$ is identical for each individual parity. Now let $m=1$ and $n=2$ , then
$g(2)=g(1)g(2)\Longrightarrow g(1)=1,$ as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

300 posts

#19 h Mar 9, 2025, 2:04 AM

Y by

We do casework on if $f(0) = 0$ or not.

If $f(0) = 0,$ take $m = 1, n = -1$ to get $(f(1), f(-1)) = (1, -1), (-1, 1).$ Take $(m, n) = (2, - 1)$ to get $f(-2) = f(2)f(-1).$ By induction, we can force $f(k)\in\{k, -k\}$ and $f$ is an involution. We do casework on $f(1), f(2)$ :

If $f(1) = 1, f(2) = 2:$ take $(2, 2^{k})$ to get that $2^{k + 1} = f(2)f(2^k),$ and so $f(2^k) = 2^k.$ take $(1, 2\ell - 1)$ to get $f(2\ell - 1) = 2\ell - 1.$ Then, take $(2^k, 2\ell - 1)$ to get $f\equiv x$
If $f(1) = -1, f(2) = 2:$ take $(2, 4)$ to get that $f(4) = 4$ . take $(4, 1)$ to get $f(4) = f(4)f(1),$ contradiction.
if $f(1) = 1, f(2) = -2:$ take $(2, 2^k)$ to get $2^{k + 1} = f(2)f(2^k),$ so $f(2^k) = -2^k.$ $(1, 2\ell - 1)$ to get $f(2\ell - 1) = 2\ell - 1.$ take $(2^k, 2\ell - 1), f(2^k(2\ell - 1)) = -2^k(2\ell - 1).$ thus, $f\equiv (-1)^xx$ .
if $f(1) = -1, f(2) = -2:$ do a ``merging'' of case 1 and case 3 to get $f\equiv -x.$

Now, assume $f(0) = k \neq 0.$ Take $m = 0$ and we get $f^{f(n)}(0) = kf(n),$ or $f^n(0) = nk.$ Furthermore, $f(-k) = 0$ (from $n = -1$ ). Take:
$\begin{align*} f^{f(n) - n - k}(0) & = f^{f(n)}(f^{-n-k}(0)) \\ & = f^{f((n + k) - k)}(-(n + k)k) \\ & = 0 \end{align*}$ so $f(n) = n + k.$

Z K Y

The post below has been deleted. Click to close.

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

1456 posts

#20 h Mar 9, 2025, 6:22 AM

Y by

Denote $P(m,n)$ to be the assertion of the given F.E.
From $P(0,n)$ and bijectivity we get $f^t(0)=f(0) \cdot t$ for all $t \in \mathbb Z$ and from here we can get that $f(t \cdot f(0))=(t+1)f(0)$ but also that $f^{u}(t \cdot f(0))=(t+u)f(0)$ for all $t,u, \in \mathbb Z$ . Setting $u=1, t=-1$ gives $f(-f(0))=0$ .
Now from $P(m+f(0), -f(0))$ we get that $f^{f(m)}(-(m+f(0))f(0))=f(m+f(0))f(-f(0))=0$ and thus $(f(m)-m-f(0))f(0)=0$ , now if $f(0) \ne 0$ then trivially we have $f(x)=x+c$ for all $x \in \mathbb Z$ and some integer $c \ne 0$ which works.
Now if $f(0)=0$ were to hold then $P(m,-m)$ gives $f(m)f(-m)=-m^2$ , now let $m=p$ for $p$ being a prime number then this means for all primes except on the case of whether $f(-p)=1$ or $f(p)=1$ for exctly one prime $p$ , it holds that $\{ f(p), f(-p) \}= \{ p, -p \}$ .
This should hold for all primes $p$ because $P(1,-1)$ gives $f(1)f(-1)=-1$ and therefore one of these has to be $1$ and in either case they are not a prime number, now notice that from induction and these finding we can now easly conclude that $\{f(n), f(-n) \}= \{ n, -n \}$ for all $n \in \mathbb Z$ , and thus this means $f(f(x))=x$ for all integers $x$ and now from $P(m,n)$ for $m \equiv n \pmod 2$ gives that $f(n)f(m)=mn$ and this can only mean either $f(m)=m, f(n)=n$ or $f(m)=-m, f(n)=-n$ and for $m-n$ odd we have that $f(n)f(m)=f(mn)$ so setting $m$ to be a non-zero even number and $n=1$ gives that $f(1)=1$ and therefore we either have $f(x)=x$ for all $x \in \mathbb Z$ or $f(x)=(-1)^{x+1} x$ for all $x \in \mathbb Z$ which can be seen to work as well, thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

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

8855 posts

#21 h Mar 17, 2025, 10:18 PM

Y by

The answers are $f(n) = n + c$ for integers $c$ and the intriguing $f(n) = (-1)^{n+1}n$ .

Based on the solution set, we will split into cases based on whether $f(0) = 0$ .

First Case: Suppose that $f(0) = 0$ . Then setting $m=-n$ yields $f(n) f(-n) = -n^2$ . Because $f$ is bijective, it is easy to see that $\{f(1), f(-1)\} = \{-1, 1\}$ and inductively $\{f(n), f(-n)\} = \{n, -n\}$ for all positive integers $n$ , otherwise the smaller of the two yields a contradiction by injectivity.

In particular, $f(f(n)) = n$ for all positive integers $n$ , so if $m + n$ is even, it follows that $f(m)f(n) = mn$ . It follows that $\tfrac{f(n)}n$ is constant for $n$ of the same parity, and it is not hard to show by setting $m+n$ odd that either $f(n) = n$ for all $n$ or $f(n) = -n$ only when $n$ is even.

Second Case: Suppose now that $f(0) = c \neq 0$ . By setting $m = 0$ , we get $f^{f(n)}(0) = cf(n)$ , implying that $f^n(0) = cn$ for all integers $n$ as $f$ is bijective. In particular, $f(kc) = (k+1)c$ for all integers $k$ , and thus $f(-c) = 0$ .

Now, for an integer $a$ , letting $(m, n) = (-c, a)$ now yields $0 = f^{f(a-c)}(-ac) = -ac + f(a-c)c$ which implies $f(a-c) = a$ , as needed.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a