Let $f: \Bbb{R} \rightarrow \Bbb{R}$ be a function such that (i) For all $x,y \in \Bbb{R}$, \[ f(x)+f(y)+1 \geq f(x+y) \geq f(x)+f(y) \] (ii) For all $x \in [0,1)$, $f(0) \geq f(x)$, (iii) $-f(-1) = f(1) = 1$. Find all such functions $f$.
Problem
Source: APMO 1994
Tags: function, induction, algebra unsolved, algebra
11.03.2006 20:56
by plugging $x=-1$, $y=1$ we get $f(0)\geq0$, by plugging $(0,0)$ we get $f(0) \leq 0$ so $f(0)=0$. You can easy prove that for all $x \in [0,1)$ we have $f(x)=0$ (it's a key step ) Now we'll prove by induction that $f(x)=[x]$. Our inductive sentence $T_n$ is: $f(x)=[x]$ for all $x<n$. Suppose we have proved it for some $n$. Now we have for $n-1 \leq x < n$ and $\epsilon$ such that $x+\epsilon<n$: $[x+1]=[x]+1=f(x+\epsilon)+f(1-\epsilon)+1 \geq f(x+1) \geq f(x)+1=[x]+1=[x+1]$. So we have proved $T_{n+1}$. QED
05.10.2021 01:13
My solution from WOOT: Let $P(x,y)$ denote the assertion of $(\text i)$. $P(0,0),P(1,-1)\Rightarrow f(0)=0$ $P(x,1)\Rightarrow f(x+1)\ge f(x)+1$ $P(x+1,-1)\Rightarrow f(x)\ge f(x+1)-1$ Then equality must hold, so $f(x+1)=f(x)+1$. For $x\in[0,1)$, $f(x)\le0$. Then: $P(x,1-x)\Rightarrow f(x)+f(1-x)\ge0$, but since $f(x)+f(1-x)\le0+0$ equality holds for each and $f(x)=0$ for $x\in[0,1)$. Then by induction on $f(x+1)=f(x)+1$ we obtain $\boxed{f(x)=\lfloor x\rfloor}$, which fits.
05.10.2021 01:38
05.10.2021 01:56
As everybody else is posting solutions, I'll also post mine: We claim that $f(x)=\lfloor x \rfloor$ is the only solution. It clearly works. Claim: $f(x+1)=f(x)+1$ for all real $x$. Notice that plugging in $x=1$ gives $$1+f(y)\le f(1+y)\le 2+f(y).$$On the other hand, plugging in $x=-1$ gives $$f(y)-1\le f(y-1)\le f(y)\Rightarrow f(y-1)\le f(y) \le f(y-1)+1\Rightarrow f(y)\le f(y+1)\le f(y)+1.$$The result follows from these two inequalities. $\blacksquare$ Thus it suffices to find the values of $f(x)$ for $0\le x<1$; then we can use the claim to find the rest of the function. Using the claim, we get $f(0)=0$. Let $0<a<1$ and plug $x=a, y=1-a$ to get $$f(a)+f(1-a)\le 1\le 1+f(a)+f(1-a).$$In particular, we get $0\le f(a)+f(1-a)$. However, from condition (ii) we get $0\ge f(a), f(1-a)$, thus we have $f(a)=f(1-a)=0$. Hence, for all $0\le x<1$, $f(x)=0$. Using the claim, we get $f(x)=\lfloor x \rfloor$, and we are done.
29.12.2021 05:57
The answer is $f(x) = \lfloor x \rfloor$, which works. Step 1: Extracting $f(0)$. We claim that $f(0)=0$. First, by setting $x=y=0$, $$2f(0)+1 \geq f(0) \geq 2f(0) \iff -1 \leq f(0)\leq 0.$$On the other hand, letting $x=1$ and $y=-1$, $$f(-1)+f(1)+1=1\geq f(0) \geq 0.$$Combining these two inequalities gives $f(0)=0$. Step 2: Getting $f$ over $[0, 1)$. Now, we claim that $f(x)=0$ for all $x \in [0, 1)$. The idea here is similar to the idea in the first step: by condition (ii), we know that $f(x) \leq 0$ for $x \in [0, 1)$, but on the contrary, letting $y=1-x$ gives us $$f(x)+f(1-x)+1\geq f(1) = 1 \iff f(x)+f(1-x) \geq 0.$$For $x \in [0, 1)$, this is only possible if $f(x)=f(1-x)=0$, as required. Step 3: Inducting upwards/downwards. Finally, we are ready to finish. Letting $y=1$ gives us $$f(x+1) \geq f(x)+1$$for all $x$, and setting $y=-1$ and $x=x+1$ gives us $$f(x+1)+f(-1)\leq f(x) \iff f(x+1)\leq f(x)+1.$$Therefore, $f(x+1)=f(x)+1$ for all $x$. Inducting upwards and downwards gives us the result.
29.12.2021 06:13
Let $P(x,y)$ denote the given assertion. Claim: $f(0)=0$. Proof: $P(0,0): 2f(0)+1\ge f(0)\ge 2f(0)\implies -1\le f(0)\le 0$. $P(1,-1): f(0)\ge 0$, so $f(0)=0$. Claim: $f(k)=0\forall 0\le k<1$. Proof: Note that $f(k), f(1-k)\le 0$. $P(k,1-k): f(k)+f(1-k)+1\ge 1\implies f(k)+f(1-k)\ge 0\implies f(k)=f(1-k)=0$. Claim: $f(x+1)=f(x)+1$. Proof: $P(x,1): f(x)+2\ge f(x+1)\ge f(x)+1$. $P(x+1,-1): f(x)\ge f(x+1)-1\implies f(x)+1\ge f(x+1)$. This proves our claim. We can also find that $f(x)-1=f(x-1)$. From this claim, $f(x)=\lfloor x \rfloor +\{x\}\implies \boxed{f(x)=\lfloor x\rfloor}$, which works.