7
$\begingroup$

Find all functions $f : \mathbb{Z} \to \mathbb{Z}$ such that $f(x-f(y)) = f(f(x)) - f(y) - 1$.

So far, I've managed to prove that if $f$ is linear, then either $f(x) = x + 1$ or $f(x) = -1$ must be true. I did this by plugging in $x=0$ to the above equation, which yields $$ f(-f(y)) = f(f(0)) - f(y) - 1$$ and plugging in $x$ instead of $y$ and subtracting, this becomes $$ f(-f(y)) - f(-f(x)) = f(x) - f(y)$$ Assuming $f(x) = ax + b$ then gives \begin{align*} f(-ay-b) - f(-ax-b) = ax - ay &\Rightarrow -a^2y - ab + a^2x + ab = a(x-y) \\&\Rightarrow a^2(x-y) = a(x-y) . \end{align*} Thus $a=1$ or $a=0$. If $a=0$, then the original equation becomes $b = b - b - 1$, thus $b=-1$. If $a=1$, the original equation becomes $$ x-y-b+b = x+2b-y-b-1 \Longrightarrow b=1.$$

I briefly tried finding a quadratic function that works but didn't find anything. So my question is: how can I either show that $f$ must be linear or find all other representations?

$\endgroup$
  • $\begingroup$ This question was from IMO 2015 shortlist, which was supposed to be kept confidential until July 2016. Note that the problems are used in some IMO2016 team selection tests, so it is really important that they are kept secret. $\endgroup$ – wythagoras Aug 11 '17 at 18:07
  • $\begingroup$ Now that this is public, the official solution can be found here: imo-official.org/problems/IMO2015SL.pdf. $\endgroup$ – Sil Apr 7 '18 at 7:56
5
$\begingroup$

Let $f\colon \Bbb Z\to \Bbb Z$ be a any function function with $$\tag0f(x-f(y)) = f(f(x)) - f(y) - 1$$ for all $x,y\in\Bbb Z$. Letting $y=f(x)$ we find $$f(x-f(f(x)))=-1. $$ So for $a=-f(f(0))$ we have $f(a)=-1$. Then with $y=a$, $$\tag1f(x+1)=f(f(x)) $$ Then $(0)$ becomes $$\tag2 f(x-f(y))=f(x+1)-f(y)-1 $$ Or with $g(x):=f(x)+1$ (and $x\leftarrow x-1$) $$\tag3g(x-g(y))=g(x)-g(y)$$ From $(3)$ we see that the image of $g$ is a subgroup of $\Bbb Z$, hence it is either $\{0\}$ (in which case $f(x)=-1$), or $c\Bbb Z$ for some $c\ge 1$. In that case, for $n\in\Bbb Z$ we find $y$ with $g(y)=nc$ and so have $g(x+ nc)=g(x)+nc$. Thus $g$ is determined by the values $g(0),\ldots, g(c-1)$. On the other hand, these values can indeed be chosen freely. In other words:

Claim 1. Let $c\in\Bbb N$ and $b_0,\ldots, b_{c-1}\in\Bbb Z$. Then the function $g$ given by $$ g(x)= (n+b_r)c$$ where $x=nc+r$, $0\le r<c$ is a solution to $(3)$, and all non-zero solutions of $(3)$ are obtained this way.

Proof. Let $x=nc+r$, $y=mc+s$ with $0\le r,s<c$. Then $$\begin{align}g(x-g(y))&=g(nc+r-(m+b_s)c)\\ &=g((n-m-b_s)c+r)\\ &=(n-m-b_s+b_{r})c\\ &=(n+b_r)c-(m+b_s)c\\&=g(x)-g(y)\end{align}$$ That all non-zero solutions are of this form has been shown above. $\square$

Then the solutions $f$ of $(2)$ (apart from $f(x)=-1$) are precisely those of the form $f(x)=g(x)-1$ with $g$ as in Claim 1. Such $f$ is a solution to the original $(0)$ if and only if we additionally have $(1)$ for all $x$. Note that for $x=nc+r$, $0\le r<c$, we have $f(x)=g(x)-1=(n+b_r)c-1=(n+b_r-1)c+c-1$ so that $$f(f(x))=(n+b_r-1+b_{c-1})c-1.$$ On the other hand, $$f(x+1)=g(x+1)-1=\begin{cases}(n+b_{r+1})c-1&\text{if }r<c-1\\(n+1+b_0)c-1&\text{if }r=c-1\end{cases}$$ We conclude that $b_{r+1}=b_r+b_{c-1}-1$ for $0\le r<c-1$, and that $2b_{c-1}-1=b_0+1$. From the first we see that $b_r=b_0+rb_{c-1}-r$, so $$\begin{align}b_{c-1}&=b_0+1+(c-1)b_{c-1}-c\\ &=2b_{c-1}-1+(c-1)b_{c-1}-c\\ &=(c+1)b_{c-1}-c-1\end{align}$$ and finally $$b_{c-1} = \frac {c+1}c.$$ This is an integer only for $c=1$ and in that case we arrive at $b_0=2$ Thus the only solutions to $(0)$ apart from $f(x)=-1$ is $$f(x)=x+1.$$

$\endgroup$
  • $\begingroup$ How do you know from (3) that the image is a subgroup, and not just contained in one? (maybe this is not essential) $\endgroup$ – Mattia Talpo Dec 10 '15 at 9:35
  • $\begingroup$ @MattiaTalpo From the subgroup criterion. If $G$ is a group and $S\subseteq G$ is a subset that is nonempty and such that $a,b\in S$ implies $ab^{-1}\in S$ (or $a-b\in S$ if $G$ is written additively) then $S$ is a subgroup. Here $S=g(\Bbb Z)$ is certainly nonempty, and $a=g(x)\in S$, $b=g(y)\in S$ implies $a-b=g(x-g(y))\in S$. $\endgroup$ – Hagen von Eitzen Dec 10 '15 at 21:23
  • $\begingroup$ Ok, makes sense. $\endgroup$ – Mattia Talpo Dec 10 '15 at 21:29
3
$\begingroup$

if we can say that $f$ is polynomial, then since $f(-f(y))-f(-f(x))=f(x)-f(y)$, we can say that $f(-f(y))+f(y)=f(-f(x))+f(x)$ for any $x,y \in Z$. Hence, $f(-f(x))+f(x)$ is constant for all $x \in Z$.

If $deg(f) >0$ then $f$ has infinitely many values, so we can say $f(-x)+x$ is constant, say $f(-x)+x=c$.

Then $f(-x)=c-x$, or $f(x)=c+x$

If $deg(f)=0$ then $f$ is constant and you know the answer.

$\endgroup$
  • $\begingroup$ How did you get from $f(-f(x)) + f(x)$ (1st paragraph) to $f(-x) + x$ (second paragraph)? $\endgroup$ – aras Dec 9 '15 at 21:01
  • $\begingroup$ @aras that is because if $f(-y)+y$ is the polynomial which have the value $c$ at infinitely many points (in our case it is when y=f(x)), then it is equal to $c$ in the whole domain. $\endgroup$ – Jane Dec 9 '15 at 21:05
  • $\begingroup$ @aras this is because nonconstant polynomial can have only finite number of roots. But $f(-y)+y=c$ implies that $f(-y)+y-c=0$ has infinite number of roots, hence it is constant. $\endgroup$ – Jane Dec 9 '15 at 21:08
3
$\begingroup$

If the functions attains $0$ at some point, it is linear and $f(n)=n+1$.

Suppose $f(y)=0$, for some $y \in \mathbb{Z}$ then we find for $x \in \mathbb{Z}$ $$f(x)=f(x-f(y))=f(f(x))-f(y)-1 = f(f(x))-1$$ So in particular $x=y$ gives $f(0)= 1$.
Now, if $f(n)=n+1$, then $x=n$ gives $$n+1 = f(n) =f(f(n))-1= f(n+1)-1$$ So $f(n+1) = n+2$, thus for $n \in \mathbb{N}$ we have $f(n) = n+1$.
For the other way, let $x=0$ and $y=n-1$ then $$f(-n) = f(x - f(n-1)) = f(f(x)) -f(n-1) -1 =f(1) - n-1 =-n+1$$ So we see that if $f(y) =0$ for some $y \in \mathbb{Z}$, we have $f(x) = x+1$.

So we can now assume $f(x) \neq 0$ for all $x \in \mathbb{Z}$.
If there exists an $y \in \mathbb{Z}$ such that $y=f(y)$, then $f(x) =-1$.

Suppose there exists an $y \in \mathbb{Z}$ such that $f(y)=y$, then with $x=y$ $$f(0) = f(y-f(y)) = f(f(y)) - f(y) - 1 = y-y-1 =-1$$ So we have $f(0)=-1$. Then we have if $f(y+n)=y$ for $n \ge 0$ that $$f(y+n+1) = f(y+n-f(0)) = f(f(y+n)) -f(0)-1 = f(y) =y$$ So we see that $f(y+n) = y$ for every $n \in \mathbb{N}$.
Now, if $y>0$, we would find with $x=2y$ $$y = f(y)=f(2y -f(y)) = f(f(2y))-f(y)-1 = f(y)-f(y)-1 =-1$$ So $y <0$, and then we have $-1 = f(0) = f(y +(-y)) =y$ and so we find $y=-1$.

Now, we have for all $x \in \mathbb{Z}$ $$-1 = f(0) = f(f(x) -f(x)) = f(f(f(x))) - f(x)-1$$ And so $f(x) = f(f(f(x)))$, and so if $f(-1-k)=-1$ for $k\ge 0$ we have $$ f(-1-k) = f(-1-k-1 -f(0)) = f(f(-1-k-1)) -f(0)-1 = f(f(-1-k-1))$$ Then we let $f$ act on both sides and we get $$-1 = f(-1) = f(f(-1-k)) = f(f(f(-1-(k+1)))) = f(-1-(k+1))$$ So we see $f(-1-n)=-1$ for all $n \in \mathbb{N}$.
So we have $f(x) = -1$ for all $x \in \mathbb{Z}$.

$\endgroup$
  • $\begingroup$ What if there does not exist a $y \in \mathbb{Z}$ such that $f(y)=y$? $\endgroup$ – aras Dec 11 '15 at 18:26
  • $\begingroup$ I am not sure, but we have in those case either $f(-1)=0$ or $f(-1)=-1$. So I suppose that when you assume $f(-1) \not\in \{0,1\}$, you should be able to find a counterexample. $\endgroup$ – Hetebrij Dec 12 '15 at 11:48
2
$\begingroup$

I think $f$ has to be linear. You derived the expression

$$ f(-f(y)) = f(f(0)) - f(y) -1. $$ Now let $a=f(0)$ and $t=-f(y)$. Then

$$ f(t) = f(a)+t-1 $$

Edit: plugging in $t=0$ we obtain $f(a)=a+1$, while plugging in $t=a$ we find $a=1$, which gives $f(t)=t+1$, in agreement with what you found.

Edit: As pointed out by Najib Idrissi I did not check for constant solutions. The only constant solution is clearly $f(t)=-1$ as it is promptly inferred from the original equation. However, I believe the expression $f(t) = f(0)+t$ is still the general expression of any non constant solution, regardless of surjectivity. As a matter of fact, we are only interested to see what's the action of $f$ on its range (cause we need to be able to apply $f$ twice). If $f(f(x)) = g(f(x))$ for every $x$, then $f=g$ on $Range(f)$. If after finding $g(x)$ we see that $Range(g)=\mathbb{Z}$, then $f(x)=g(x)$ on $\mathbb{Z}$.

Edit: I finally get completely the point of Najib and Mattia. The expression I found works only if $t$ is in the Range of $f$. Unfortunately, there is no way from there to infer how big $Range(f)$ is. As a matter of fact, it could consist of simply one point. Please, disregard this answer (but keep it as an example of bad reasoning!).

$\endgroup$
  • $\begingroup$ The first expression should read $f(-f(t)) = f(a) - f(t) -1$ instead of $f(f(t))$. $\endgroup$ – Hetebrij Dec 9 '15 at 20:47
  • $\begingroup$ Correct. I changed my answer. $\endgroup$ – bartgol Dec 9 '15 at 20:55
  • 5
    $\begingroup$ This answer is incomplete. What if $f$ is not surjective? You only know $f(t) = f(a) + t - 1$ when $t = f(y)$ for some $y$, but what if there's no $y$? For example you're missing the solution $f(x) = -1$. $\endgroup$ – Najib Idrissi Dec 9 '15 at 21:02
  • $\begingroup$ Good point. I edited the answer. I still believe that the only non-constant solution is given by $f(t)=t+1$ though... $\endgroup$ – bartgol Dec 10 '15 at 16:53
  • $\begingroup$ @bartgol your last paragraph is not correct. Let $f\colon \mathbb{Z}\to \mathbb{Z}$ be the function $f(k)=k$ if $k\geq 0$ and $-k$ else, and let $g\colon \mathbb{Z}\to \mathbb{Z}$ be the identity. Then $f(f(x))=g(f(x))$ for every $x$, and the range of $g$ is $\mathbb{Z}$, but $f(x)\neq g(x)$ on $\mathbb{Z}$. $\endgroup$ – Mattia Talpo Dec 10 '15 at 17:59
0
$\begingroup$

Here's a partial solution.

If $0$ is a possible value of $f$, then by taking $f(y) = 0$ we get $f(f(x)) = f(x) + 1$. That is, $f(t) = t + 1$ for $t \in f(\mathbb Z)$, and in particular $f(\mathbb Z)$ contains all nonnegative integers. If we define $g(x) = f(x) - x$, the equation becomes $$ g(x - f(y)) = g(x) + g(x + g(x)) - 1$$ But note that the right side does not depend on $y$. Thus, since $f(y)$ can be any nonnegative integer, $g$ must be constant, and taking $x = 0$ we see that this constant must be $1$. So the only solution where $0$ is a possible value of $f$ is $f(x) = x + 1$.

$\endgroup$
  • $\begingroup$ The partial result is the same partial result as that of Hetebrij $\endgroup$ – Hagen von Eitzen Dec 9 '15 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.