Find all $f:\mathbb{Z}\to\mathbb{Z}$ such that \[f\left(\left\lfloor\frac{f(x)+f(y)}{2}\right\rfloor\right)+f(x)=f(f(y))+\left\lfloor\frac{f(x)+f(y)}{2}\right\rfloor\]holds for all $x,y\in\mathbb{Z}$. Proposed by usjl
Problem
Source: 2022 Taiwan TST Round 1 Independent Study 1-A
Tags: algebra, functional equation, Taiwan
16.03.2022 15:15
Redacted
16.03.2022 17:03
Nice problem, the only such functions are constants, which clearly work. Let $S$ be the range of $f$. First, swapping $x,y$ gives that $f(f(x)) + f(x)$ is constant over all $x$ so $f(x) + x$ is constant over $S$, say this constant value is $N$. Rewrite the given equation as then $$f\left(\left\lfloor\frac{a+b}{2}\right\rfloor\right) - \left\lfloor\frac{a+b}{2}\right\rfloor = N-a-b$$for $a,b \in S$. This means that if $a,b \in S$, then $N-a-b+\left\lfloor\frac{a+b}{2}\right\rfloor = N - \left \lceil \frac{a+b}{2} \right \rceil \in S$ as well and since $x \in S \implies N-x \in S$ too (because $f(x) = N-x$ for $x \in S$), we have $a,b \in S \implies \left \lceil \frac{a+b}{2} \right \rceil \in S$ If $S$ has more than one element, consider the two things in it with minimum difference, if its $\ge 2$, then replace it with the ceiling of the average, which reduces the difference to them. So we can find two consecutive elements $m, m+1$ in $S$. But then substituting $a = m, b = m+1$, we get that $N-2m = f(m)-m = f\left(\left\lfloor\frac{m+m+1}{2}\right\rfloor\right) - \left\lfloor\frac{m+m+1}{2}\right\rfloor = N - 2m - 1$, a contradiction. Therefore, the range contains only one element and so $f$ is constant. $\blacksquare$
16.03.2022 17:37
L567 wrote:
I messed up because $x,y\in T$ does not necessarily imply $\frac{x+y}{2}\in T$.
16.03.2022 20:08
L567 wrote: Nice problem, the only such functions are constants, which clearly work. Let $S$ be the range of $f$. First, swapping $x,y$ gives that $f(f(x)) + f(x)$ is constant over all $x$ so $f(x) + x$ is constant over $S$, say this constant value is $N$. Rewrite the given equation as then $$f\left(\left\lfloor\frac{a+b}{2}\right\rfloor\right) - \left\lfloor\frac{a+b}{2}\right\rfloor = N-a-b$$for $a,b \in S$. This means that if $a,b \in S$, then $N-a-b+\left\lfloor\frac{a+b}{2}\right\rfloor = N - \left \lceil \frac{a+b}{2} \right \rceil \in S$ as well and since $x \in S \implies N-x \in S$ too (because $f(x) = N-x$ for $x \in S$), we have $a,b \in S \implies \left \lceil \frac{a+b}{2} \right \rceil \in S$ If $S$ has more than one element, consider the two things in it with minimum difference, if its $\ge 2$, then replace it with the ceiling of the average, which reduces the difference to them. So we can find two consecutive elements $m, m+1$ in $S$. But then substituting $a = m, b = m+1$, we get that $N-2m = f(m)-m = f\left(\left\lfloor\frac{m+m+1}{2}\right\rfloor\right) - \left\lfloor\frac{m+m+1}{2}\right\rfloor = N - 2m - 1$, a contradiction. Therefore, the range contains only one element and so $f$ is constant. $\blacksquare$
Nice one! Your solution looks really clean. There is one cleaner solution that extracts the idea in your solution---I will post this later.
16.03.2022 22:43
Here is how the problem was composed: we consider the mysterious set \[S:=\{(x-y,f(x)-f(y))|x,y\in\mathbb{Z}\}.\]It is an easy exercise to check that the condition implies: if $(a,b)\in S)$, then $(\lfloor \frac{b}{2}\rfloor,-\lceil\frac{b}{2}\rceil)\in S$. We also always have that if $(a,b)\in S$ then $(-a,-b)\in S$, and if $a=0$ then $b=0$. We will use this to show that $(a,b)\in S$ implies $b=0$, which would show that $f$ is constant. Suppose that this is not the case, let $(a,b)\in S$ be the one with the smallest non-zero $|b|$ and WLOG assume that $b$ is positive. Then we have \[(\lfloor \frac{b}{2}\rfloor,-\lceil\frac{b}{2}\rceil)\in S.\]Since $|\lceil\frac{b}{2}\rceil|\geq |b|$ by the choice of $(a,b)$, we have $b= 1$. We then have $(\lfloor \frac{1}{2}\rfloor,-\lceil\frac{1}{2}\rceil)=(0,-1)\in S$, which is a contradiction. Therefore $f$ must be constant. Also check out Section 2.5 of the note here for a more detailed story behind the scene of this problem: https://artofproblemsolving.com/community/c6h2784600p24469107
09.03.2023 16:40
Let the range of $f$ be $T$. Claim 1: $f(f(x))+f(x)=c$ for all $x$ for some constant $c$. Proof: $P(y,x)$ yields the result by symmetry. Now we have $f(a)=c-a$ for all $a\in T$. Claim 2: if $a\in T$, then $a+1\notin T$. Proof: Let $f(d)=a$ and $f(e)=a+1$ $P(d,e)$ gives us $f(a)+a=f(a+1)+a$ so $f(a)=f(a+1)$ By claim 1 we have $f(d)+f(a)=c$ But $f(e)+f(a+1)=c=f(e)+f(a)$ so $a=f(d)=f(e)=a+1$, contradiction. Claim 3: if $t,u\in T$, then $\lceil \frac{t+u}{2}\rceil\in T$ Proof: $P(t,u)$ gives $f(\lceil\frac{f(t)+f(u)}{2}\rceil)+c-t=u+c-\lfloor \frac{t+u}{2}\rfloor$. So we have $f(\lceil\frac{f(t)+f(u)}{2}\rceil)=\lceil \frac{t+u}{2}\rceil$. Now we can easily observe that claim 2 contradicts claim 3 if $|T|>1$. So $|T|=1$ and the function is constant.