Find all nondecreasing functions $f:\mathbb R\to \mathbb R$ such that, for all $x,y\in \mathbb R$, $$f(f(x))+f(y)=f(x+f(y))+1.$$ Proposed by Carl Schildkraut
Problem
Source: 2019 ELMO Shortlist A4
Tags: algebra, functional equation
28.06.2019 04:20
Let's only consider non constant functions, since $f\equiv 1$ is the only constant function. First plugging in $x=y-f(y)$ gives $1\in f(\mathbb{R})$ Take $g(x)=f(x+1)-1$, then we have $0\in g(\mathbb{R})$, and $$g(g(x-1))+g(y-1)+2=g(f(x)-1)+1+f(y-1)+1=f(f(x))+f(y)=f(x+f(y))+1=g(x-1+f(y))+2=g(x+g(y-1))+2$$, or $g(g(x))+g(y)=g(x+1+g(y))$. Substituting $y=t\in g^{-1}(\{0\})$ yields $g(g(x))=g(x+1)$, thus $g(x+g(y))=g(x)+g(y)$, which is a well-known FE(with the non-decreasing condition). Let $P(x,y)$ be the assertion $g(x+g(y))=g(x)+g(y)$. Observe that $$g(x-g(y))=g(x)-g(y), g(x+\sum_{i=0}^{m}{g(y_i)})=g(x)+\sum_{i=0}^{m}{g(y_i)}$$, so if $\frac{g(a)}{g(b)}$ for some $a,b\in\mathbb{R}$, then the set $\{mg(a)+ng(b)| m,n\in\mathbb{Z}\}$ is dense on $\mathbb{R}$, thus $g(x)=x+c$ for some $c\Longrightarrow c=1$, which is indeed a solution. Now assume that there exists $A\in \mathbb{R}$ such that $\frac{g(x)}{A}\in\mathbb{Q}$ for all $x$. Note that $g(x)$ is a solution if and only if $h(x)=\frac{1}{A}g(Ax)$ is a solution, so we can assume that $g(\mathbb{R})\in \mathbb{Q}$. Again, if there does not exist an integer $m$ such that $mg(x)\in\mathbb{Z}$ for all $x$, then the set $\{\sum_{i=0}^{m}{g(y_i)}-\sum_{j=0}^{n}{g(z_j)}|m,n\in \mathbb{Z}, y_i,z_j\in\mathbb{R}\}$ is dense on $\mathbb{R}$. (why?) Hence $g(x)=x+c$ for some $c$, a contradiction. Using the same method, we can assume that $g(\mathbb{R})\in \mathbb{Z}$, and $1\in g(\mathbb{R})$. ($\because h(x)=\frac{1}{B}g(Bx)$, where $B$ is the smallest positive integer such that $Bg(x)\in\mathbb{Z}$ for all $x$.) We have that $g(x+1)=g(x)+1$, and since $g$ is non-decreasing, $g(x)=\lfloor x+\alpha\rfloor $ for some $\alpha$, or $g(x)=\lceil x+\beta \rceil$ for some $\beta$, and letting $C=AB$, we have that $$g(x)=\frac{1}C\left(\left\lfloor C({x+\alpha})\right\rfloor\right)$$works. We further have $g(g(x))=g(x+1)$, thus $C=\lfloor \alpha\rfloor$. Hence all solutions are $\boxed{f\equiv 1},\boxed{f(x)=x+1}, \boxed{f(x)=\frac{1}{n}\lfloor{nx+\alpha}\rfloor}, \boxed{f(x)=\frac{1}{n}\lceil {nx+\beta}\rceil}$ for $n>0, n=\lfloor \alpha\rfloor, n=\lceil \beta\rceil$
28.06.2019 04:41
MNJ2357 wrote: We have that $g(g(x))=g(x+1)=g(x)+1$, and since $g$ is non-decreasing, $g(x)=\lfloor x+\alpha\rfloor +1$ for some $\alpha \in [0,1)$, or $g(x)=\lceil x+\beta \rceil$ for some $\beta\in(0,1]$... I believe this part is not correct; try $g(x)=\frac{1}{2}\left\lfloor 2x\right\rfloor+1$.
28.06.2019 04:42
Yes, I messed up the last few lines. I'm editing Edit: Fixed!
28.06.2019 04:50
28.06.2019 16:39
Uhh... How are people so creative in making problems (seriously, despite looking at it, we would consider $f(\mathbb{R})$ most of the time)? Yet another, but not just another, functional equation with a non-trivial solution...
04.07.2019 03:42
22.08.2019 04:37
We claim the solutions are $f(x)=1$, $f(x)=x+1$, $f(x)=\frac{1}{n}\lceil n(x-r)\rceil+1$, and $f(x)=\frac{1}{n}\lfloor n(x+r)\rfloor+1$ for any $n\in\mathbb{N}$ and $r\in[0,1/n)$. With enough work, these can be checked to satisfy the FE. Let $P(x,y)$ be the given FE. Note that \[P(0,y)\implies f(f(0))+f(y)=f(f(y))+1,\]and in particular setting $y=0$ gives $f(0)=1$. Thus, letting $k=f(1)-1$, we have \[f(f(y))=f(y)+k.\]We also see that \[P(x,0)\implies f(f(x))+1=f(x+1)+1\implies f(x+1)=f(x)+k.\]Note that $k\ge 0$ from the non-decreasing condition. If $k=0$, then $f(0)=f(1)=1$, so $f(x)=1$ for all $x\in[0,1]$. Combined with $f(x+1)=f(x)$, we would get $f\equiv 1$, which is a solution. Thus, we may assume now that $k>0$. We'll now show that $k=1$ (which is the same as $f(1)=2$). Iterating $f(x+1)=f(x)+k$, we see that $f(n)=1+nk$ for all integers $n$. Thus, \[f(1+nk)=f(f(n))=f(n)+k=1+(n+1)k.\]We now take $n$ to be large. We see that \[f(\lfloor 1+nk\rfloor)=1+k\lfloor 1+nk\rfloor>1+(n+1)k\]for large enough $n$ if $k>1$. This violates the non-decreasing condition, so we must in fact have $k=1$. At this point, everything becomes much nicer, and we're left with solving the equations \[f(f(x))=f(x)+1,\quad f(x+1)=f(x)+1,\quad f(x+f(y))=f(x)+f(y)\]where $f(0)=1$. Call the last condition $Q(x,y)$. Let $S:=\{x\in\mathbb{R}:f(x)=x+1\}$. The condition $f(x+1)=f(x)+1$ and $f(0)=1$ implies that $\mathbb{Z}\subseteq S$. Furthermore, if $a,b\in S$, then \[Q(a,b-1)\implies f(a+b)=a+1+b=(a+b)+1,\]so $a+b\in S$. To summarize, we see that $\mathbb{Z}\subseteq S$ and $S$ is closed under addition. If $S$ is dense in $\mathbb{R}$, then we're done as the non-decreasing condition would imply $f(x)\equiv x+1$. We claim that if $S$ contains any irrational number $\alpha$, then it is dense. To see this, note that $\alpha\in S$ implies that $m+n\alpha\in S$ for any $m,n\in\mathbb{Z}$. In particular, the set of the fractional part of $n\alpha$ for all integers $n$ is dense in $[0,1)$, so $m+n\alpha$ is dense in $\mathbb{R}$. So WLOG, we may assume that $S\subseteq \mathbb{Q}$. Note that if $a/b\in S$ where $\gcd(a,b)=1$, then by Bezout's lemma, we can pick $m$ and $n$ such that $ma+nb=1$. Thus, $m\cdot(a/b)+n=1/b\in S$, so all fractions with denominator $b$ are in $S$. Thus, if we have numbers in $S$ with arbitrarily large denominator, then $S$ is again dense. So WLOG, we may assume that $S$ contains bounded denominators, so in fact $S=\frac{1}{n}\mathbb{Z}$ for some positive integer $n$. Note that $f(f(x))=f(x)+1$, so $f(x)\in S$ for all $x$. Furthermore, $f(a/n)=1+a/n$ since $a/n\in S$. Also, determining $f$ in the interval $[0,1/n)$ suffices, since \[Q(x,1/n-1)\implies f(x+1/n)=f(x)+1/n.\]Note that $f(0)=1$ and $f(1/n)=1+1/n$, and $f$ is non-decreasing, so the only possibilities for $f$ in this interval are \[ f(x)=\begin{cases} 1 & 0\le x\le r \\ 1+1/n & r<x< 1/n \end{cases} \]and \[ f(x)=\begin{cases} 1 & 0\le x< 1/n-r \\ 1+1/n & 1/n-r\le x< 1/n \end{cases} \]where $r$ is any real number in the interval $[0,1/n)$. Extending these solutions to the entire real line, we get $f(x)=\frac{1}{n}\lceil n(x-r)\rceil+1$ and $f(x)=\frac{1}{n}\lfloor n(x+r)\rfloor+1$ for any $n\in\mathbb{N}$ and $r\in[0,1/n)$ as our final two solutions.
03.11.2019 15:43
may f(x)=x+1 be a solution ?
26.01.2020 15:00
Excellent problem! Denote $P(x,y)$ as the assertion of $x$ and $y$ to the given functional equation: \[ P(x,y) : f(f(x)) + f(y) = f(x+f(y)) + 1 \]Consider $P(0,0)$, we then have $f(0) = 1$. Notice that $P(x,0)$ gives us \[ f(f(x)) = f(x+1) \]Consider $P(0,x)$, we then have \[ f(1) + f(x) = f(f(x)) + 1 = f(x+1) + 1 \]Hence, $f(x+1) - f(x) = f(1) - 1 = f(1) - f(0) \ge 0 $. Suppose $f(x + 1) - f(x) = 0$. Then we have that $f(\mathbb{Z}) = 1$ and by the nondecreasing property, we have $f(\mathbb{R}) = 1$. This gives us $\boxed{f(x) = 1}$ as a solution. Now suppose that \[ f(x+1) - f(x) = c > 0 \]Consider a new function $g(x) = f(x) - 1$, and therefore rewrite the above condition to \[ g(x+1) + g(y) = g(x+g(y) + 1) \]We have $g(x+1) - g(x) = g(1)$. Hence, \[ g(x) + g(y) = g(x+g(y)) \ \forall x,y \in \mathbb{R} \]Denote this assertion as $Q(x,y)$. Notice that $Q(0,y)$ gives us $g(g(y)) = g(y)$ for all $y$. $\textbf{Claim 01.}$ $g(1) = 1$. $\textit{Proof.}$ Suppose $g(1) = c < 1$. Then consider $g(g(n)) = g(n) = ng(1) = nc$. Thus $g(n) = g(nc) = nc$. Taking $n \to n + 1$, we have $g(nc + c) = nc + c$. But taking large $n$ such that $1 - \frac{1}{n + 1} \ge c$. We can force \[ cn < nc + c \le n\]which gives us \[ cn = g(cn) \le g(nc + c) \le g(n) = cn\]A contradiction. Similarly, when $g(1) = c > 1$. We have $g(n) = g(nc) = nc$. Taking $n \to n - 1$, we have $g(nc - c) = nc - c$. But taking large $n$ such that $c \ge 1 + \frac{1}{n - 1}$. We can force \[ n \le cn - c < cn \]which gives us \[ cn = g(n) \le g(cn - c) \le g(cn) = cn \]a contradiction. $\textbf{Claim 02.}$ Let $S = \text{Im}_g$. Then $S$ is closed under subtraction. $\textit{Proof.}$ Take $Q(x - g(y), y)$, we then have \[ g(x - g(y)) = g(x) - g(y) \]which proved that $S$ is closed under subtraction. $\textbf{Claim 03.}$ $S$ is either dense or has a minimum positive element. $\textit{Proof.}$ Let $a = \inf \{ g \in S, g >0 \}$. Suppose that $a \notin G$. This implies that for each $\varepsilon > 0$ there is $g \in S$ such that $a < g < a + \varepsilon$. The same argument gives the existence of $g'$ such that $a < g' < g < a + \varepsilon$. Thus we found $h_{\varepsilon} = g - g'$ which belongs to $S$ and hence fulfills $0 < h_{\varepsilon} < \varepsilon$. Hence, taking the set of $z \cdot h_{\varepsilon} ; z \in \mathbb{Z}$, it is easy to see that $S$ is then dense. $\textbf{Claim 04.}$ If $S$ is dense, then $g$ is linear. $\textit{Proof.}$ Since $g(g(n)) = g(n)$ for all $n$. This gives us that $g(a) = a$ for $a \in S$. Suppose we want to find $g(x)$ where $r < x < s$ and $r,s \in S$. Since $S$ is dense in $\mathbb{R}$ and $g$ is nondecreasing, this gives us $r < g(x) < s$ as well. Taking $0 < s - r < \varepsilon$ as small as possible, we then have $g(x) = x$. This forces $g$ being linear, which gives us $g(x) = x$ when plugging to the original equation. Hence, $\boxed{f(x) = x + 1}$ is another valid solution. $\textbf{Claim 05.}$ If $S$ is not dense, then $S = \frac{1}{n} \mathbb{Z}$, $n \in \mathbb{N}$. $\textit{Proof.}$ Suppose otherwise, that the minimum positive element is $a \not= \frac{1}{n}$, where $n \in \mathbb{N}$. This means that all other elements in set $S$ can be formed with just $a$, as $S$ is closed under subtraction and addition. Now, notice that this gives us $1 = ka$ for $k \in \mathbb{N}$, a contradiction. Now, suppose that we partition the $\mathbb{R}_{\ge 0}$ into intervals of: $\bigcup_{i \in \mathbb{N}_0} [a_i, a_{i + 1})$ with each interval $[a_i, a_{i + 1})$ being mapped to $\frac{i}{n}$. $\textbf{Claim 06.}$ Every interval $[a_i, a_{i + 1})$ has the same length. $\textit{Proof.}$ Now, notice that by the condition \[ Q(x,y) : g(x+g(y)) = g(x) + g(y) \]and \[ Q'(x,y) : g(x - g(y)) = g(x) - g(y) \]We have that $[a_j, a_{j + 1}) + \frac{i}{n} \in [a_{i + j}, a_{i + j + 1} ) $ and $[a_{i + j}, a_{i + j + 1}) - \frac{i}{n} \in [a_j, a_{j + 1})$. This gives us $a_{j + 1} - a_j \le a_{i + j + 1} - a_{i + j} \le a_{j + 1} - a_j$, which is what we wanted. Moreover, since $g(x+1) = g(x) + 1$, then the length of these intervals, must not exceed $1$. Therefore, we can classified the other solutions as: \[ \boxed{ f(x) = \frac{1}{n} \lfloor nx + \alpha\rfloor + 1} \]\[ \boxed{f(x) = \frac{1}{n} \lceil nx - \alpha \rceil + 1} \]for any $\alpha \in [0,1)$ and any positive integer $n$.
28.05.2020 12:47
simpler sol: claim1:$f(f(x))=f(x)=f(f(0))-1+f(x)$ $(*)$ claim2:$f(f(x)+y)=f(f(y)+x)$ $(**)$ according claim1 problem change to: $f(x)+f(y)+f(f(0))-1=f(x+f(y))+1.$ so plug $x=0$ we get :$f(0)+f(y)+f(f(0))-1=f(f(y))+1 \implies f(f(0)=f(0)+1 (***)$ so according $(***)$ problem change to: $f(x)+f(y)+f(0)=f(x+f(y))+1.$ check $P(0,0) \implies f(0)=1$ so problem change to $f(x+f(y))=f(x)+f(y)$ so put $x=y-f(y) \implies f(y-f(y))=0$ $(****)$ claim3:only exist one number like $r$ which $f(r)=0$ or $f(x)=0$ for all $x \in r \in \mathbb R$ according $(****) \implies f(y)-y=f(x)-x $ So fix $ y \implies f(x)=x+c \implies f(x)=x+1$ $DONE$
28.05.2020 13:22
As TLP.39 pointed out on the other thread, you did not prove Claim 3 and more severely, it's invalid. The answer is not just $f(x)=x+1$. There is the constant solution $f(x)=1$ and even more solutions (which I don't want to tell as realizing it is the main difficulty of this problem).
24.06.2021 17:14
Am I missing a point, it says it is a nondecreasing function so how can f(X)=1 be a solution.
15.10.2021 22:38
CahitArf wrote: Am I missing a point, it says it is a nondecreasing function so how can f(X)=1 be a solution. its non-decreasing, not strictly increasing ; so the solution is fine.
14.06.2023 20:17
Denote the assertion with $P(x, y)$. By $P(y - f(y), x)$ it follows that there exists a $c$ such $f(c) = 1$. Then, $P(x, c)$ implies that \[ f(f(x)) = f(x + 1). \]By $P(f(x), y)$ it follows that \[ f(x + 2) + f(y) = f(f(x) + f(y)) + 1 \]so if $f$ has a root $r$, then letting $y = r$ implies that $f(x + 2) = f(x + 1) + 1$ and thus $f(x) = x + 1$, which works. Else, assume that $f$ is never zero. Since the assertion is equivalent to \[ f(x + 1) + f(y) = f(x + f(y)) + 1 \]it follows that for any $x, y$ \[ f(y) - 1 = f(x + f(y)) - f(x + 1) \] Claim: Either $f(x) = x + 1$ or there exists some $d$ such $\text{Im}(f)$ is a subset of $\{ nd + 1 \mid n \in {\mathbb Z} \}$. Proof. Let $S$ be the set of reals such \[ f(x + s) = f(x) + s \]It follows from the assertion that $f(x) - 1 \in S$ for all $x$. Further note that $S$ forms a ${\mathbb Z}$-module. If there exists arbitrarily small positive values in $S$, then this constricts values of $f$ between some $x + c$ so by density $f(x) = x + c$, of which $x + 1$ works. Else, let $d$ be the minimal value in $S$. It follows that all elements in $S$ are multiples of $d$ by a variant of the division algorithm. $\blacksquare$ It follows that $f(nd) = (n + k)d + 1$ for integers $n$ and some $k$. Thus, \[ f(x) = d \cdot h(x) + 1 \]for some nondecreasing $h(x) \colon {\mathbb R} \to {\mathbb Z}$ such $h(x + d) = h(x) + 1$. Then, the original assertion becomes \begin{align*} h(d \cdot h(x) + 1) + h(y) &= h(x + d \cdot h(y) + 1) \\ h(1) + h(x) + h(y) &= h(x + 1) + h(y) \\ h(x) + h(1) &= h(x + 1) \end{align*}$h$ is well defined then if and only if $\frac{d}{1} = \frac{1}{h(1)}$ so $h(1) = \frac{1}{d}$, thus $d$ must be the reciprocal of a nonzero integer. Note that if that holds, then since $h(1) = h(1)^2 \cdot d$, it follows that the assertion holds. Simplifying a bit more, the solution set is thus $f(x) = x + 1$ and \begin{align*} f(x) &= \frac{1}{k} \cdot \left\lfloor kx + c\right\rfloor + 1 \\ f(x) &= \frac{1}{k} \cdot \left\lceil kx - c\right\rceil + 1 \end{align*}for some nonzero integer $k$ and real $0 \le c < 1$. (Some of the above solutions only assume $k$ is positive I think, which is technically incorrect since the functions don't match at one point)
30.12.2023 21:01
The answer is $f \equiv 1$, $f(x)=x+1$, and $f(x)=\tfrac{1}{n} \lfloor nx+a\rfloor+1$ along with $f(x)=\tfrac{1}{n} \lceil nx-a\rceil+1$ where $n \in \mathbb{Z}^+$ and $a \in [0,1)$, which can be manually verified. Let $x=y=0$ to obtain $f(0)=1$. Let $y=0$ to obtain $f(f(x))=f(x+1)$, so we can rewrite the assertion as $f(x+1)+f(y)=f(x+f(y))+1$. Plugging in $x=0$ implies $f(1)+f(y)=f(f(y))+1=f(y+1)+1$, so $f(y+1)-f(y)=f(1)-1$. If there exists any $x$ with $|f(x)-(x+1)| \geq 1$, then since $f(f(x))=f(x+1)$, $f$ is constant on the closed interval with endpoints $f(x)$ and $x+1$, and since $f(y+1)-f(y)$ is constant we find that $f$ is constant. It's easy to check that in this case $f \equiv 1$ is the only solution. If $f$ is nonconstant, then $|f(x)-(x+1)|<1$ for all $x$, which implies $f(1)-1=1$. Thus $f(n)=n+1$ for all $n \in \mathbb{Z}$, so by nondecreasingness $\lfloor x \rfloor+1 \leq f(x) \leq \lfloor x\rfloor+2$ for all $x$. Let $f(x)=\lfloor x\rfloor+1+g(x)$, so $g$ is a $1$-periodic function whose range is a subset of $[0,1]$ such that $g(0)=0$. Furthermore, $g$ should be nondecreasing on $[0,1)$. The assertion implies $g(x)+g(y) \equiv g(x+g(y)) \pmod{1}$. Let $S$ be the range of $g$. Then for any $y \in S$ we have $g(x+y)-g(x) \equiv y \pmod{1}$, so (by starting with $x=0$) any positive integer linear combination of elements of $S$ is sent to itself modulo $1$ by $g$. If $S$ contains an irrational number $y$, then $\{ky\}$ is dense in $[0,1)$ across $k \in \mathbb{Z}$, so $g(ky) \equiv ky \pmod{1} \implies g(x) \equiv x \pmod{1}$ for all $x$ by nondecreasingness and thus $g(x)=\{x\} \implies f(x)=x+1$. Otherwise, let $n$ be the least positive integer such that $nS$ is a set of integers. Then we have $g(x+\tfrac{1}{n})-g(x) \equiv \tfrac{1}{n} \pmod{1}$, and $g$ is uniquely determined by the length-$\tfrac{1}{n}$ semi-open interval on which it's $0$. This interval must contain $0$, so we readily extract the advertised solutions for $f$. $\blacksquare$