Find all functions $f:\mathbb Z\to \mathbb Z$ such that for all surjective functions $g:\mathbb Z\to \mathbb Z$, $f+g$ is also surjective. (A function $g$ is surjective over $\mathbb Z$ if for all integers $y$, there exists an integer $x$ such that $g(x)=y$.) Proposed by Sean Li
Problem
Source: 2019 ELMO Shortlist A2
Tags: algebra, functional equation
28.06.2019 07:09
What happens if $g=-f$?
28.06.2019 07:18
@Above it would raise a contradiction if $f$ is surjective, but doesn't give us any information otherwise.
28.06.2019 08:53
28.06.2019 14:54
Only constant functions satisfy the requirements. It's trivial to check the constant functions do the job. Suppose now now $f$ is not constant. We seek a surjective function $g$ , such that $f+g$ is not surjective. It's enough to construct a surjective function $g:\mathbb{Z}\to \mathbb{Z}$ such that $g(x)\neq -f(x),\forall x\in \mathbb{Z}$. Consider a bipartite graph $G=(Y,X), X=Y=\mathbb{Z}$. We interpret $X$ as the domain set of the function $g$ and $Y$ the image of $g$. There is edge between $y\in Y$ and $x\in X$ iff $y=-f(x)$. We can consider the edges of $G$ as the not possible edges and want to construct another graph $G'=(Y,X)$, such that: i) $G'$ does not contain edges in $G$ and any $y\in Y$ is connected with some $x\in X$ (surjectivety). ii) Any $x\in X$ is connected with only one $y\in Y$. ($g$ is a function). Clearly $G'\subset \overline{G}$, where $\overline{G}$ is the complement of $G$. Now, $\overline{G}$ has a simple property: all vertices of $Y$, except eventually one, have infinite degrees in $\overline{G}$. Indeed, assume there is $y_0\in Y$ with a finite degree in $\overline{G}$. It means $f(x)=-y_0$ for all $x\in\mathbb{Z}$ except finitely many integers. Hence, all other $y\in Y,y\neq y_0$ have finite degrees in $G$ and infinite degrees in $\overline{G}$. This property allows us easily to construct $G'$. First, take $y_0$ and mark some edge of $\overline{G}$ incident with $y_0$ ($\deg_{\overline{G}} y_0>0$, since $g$ is not a constant). Then for every next $y\in Y$ we can mark some edge in $\overline{G}$ that connects $y$ with some $x\in X$ not yet exhausted. In that way we exhaust all $y\in Y$. If some $x\in X$ is still not incident to a marked edge, we can mark any edge of $\overline{G}$ incident with $x$. So, the marked edges represent a graph $G'\subset \overline{G}$ that satisfies i) and ii). Finally, if $g$ is a function that corresponds to $G'$, $f+g$ doesn't take value $0$.
29.06.2019 09:22
pieater314159 wrote: Find all functions $f:\mathbb Z\to \mathbb Z$ such that for all surjective functions $g:\mathbb Z\to \mathbb Z$, $f+g$ is also surjective. (A function $g$ is surjective over $\mathbb Z$ if for all integers $y$, there exists an integer $x$ such that $g(x)=y$.) Proposed by Sean Li Solution. (fakesolve) If $f$ is a solution, then clearly $f'$ is also a solution where $f'(n) = f(n)$ for all $n\neq a,a+1$ and $f'(a)=f(a+1),f'(a+1) = f(a)$ (as the order doesn't matter and we can swap the values in $g$ also). Therefore WLOG we assume that $f$ is a non-decreasing function. Now choose $g(n) = n$. Therefore we have $f+g$ is a strictly increasing function and as $f+g$ is surjective, we have $f(n) + g(n) = n+c$ for some constant $c$, therefore $f$ is a constant function which is clearly a solution. $~\square$ Will edit this later if I come up with a solution.
30.06.2019 18:42
Some random BS was written here.
30.06.2019 19:09
TheDarkPrince wrote: pieater314159 wrote: Find all functions $f:\mathbb Z\to \mathbb Z$ such that for all surjective functions $g:\mathbb Z\to \mathbb Z$, $f+g$ is also surjective. (A function $g$ is surjective over $\mathbb Z$ if for all integers $y$, there exists an integer $x$ such that $g(x)=y$.) Proposed by Sean Li Solution. If $f$ is a solution, then clearly $f'$ is also a solution where $f'(n) = f(n)$ for all $n\neq a,a+1$ and $f'(a)=f(a+1),f'(a+1) = f(a)$ (as the order doesn't matter and we can swap the values in $g$ also). Therefore WLOG we assume that $f$ is a non-decreasing function. Now choose $g(n) = n$. Therefore we have $f+g$ is a strictly increasing function and as $f+g$ is surjective, we have $f(n) + g(n) = n+c$ for some constant $c$, therefore $f$ is a constant function which is clearly a solution. $~\square$ Actually, you cannot swap $f(x)$ to a non-decreasing function if $f^{-1}(1),f^{-1}(2),f^{-1}(3)$ are all infinite sets.
30.06.2019 21:11
Suppose FTSOC $f$ is non-constant. Let $S_n=\{x \mid f(x)=n\}$ for any $n\in \mathbb{Z}.$ If $f$ is surjective, take $g=-f$ to achieve a contradiction, so assume WLOG that $f$ is not surjective. Case 1 There is an $m$ such that $S_m$ is infinite. Let $g$ be a function such that $g(S_m)=\mathbb{Z}/\{-m\}$ and $g(y)=-m$ for some $y\notin S_m.$ Clearly $g$ is surjective, but $0\notin \text{Im}(f+g).$ Case 2 $S_m$ is finite for all integers $m.$ Let $g$ be a surjective function such that $g(x)=-m$ iff $x=1+\max_{s\in S_m}(s)$ . However, $0\notin \text{Im}(f+g),$ hence we achieve a contradiction.
30.06.2019 21:43
Can we take the problem even a step further.Find all surjective fns f and g.from Z to Z such that f+g is surjective.Also what if we replace Z with R?
30.06.2019 22:18
@TheDarkPrince: I really don't understand why you deleted post #6! It can still be seen in #9. I liked your idea and btw, it can be saved.
03.07.2019 21:00
math_pi_rate wrote: since the only bijective integer function is of the form $p(n)=n+c$. Not true? (Take $x \mapsto -x$, or actually any involution.)
05.07.2019 14:03
In this problem it's useful the function $f$ to be viewed primary as the set of its functional values and the corresponding sets of $x$'s for which $f$ takes the same value. The idea in #6 - to arrange $f$ in increasing order and use $g\equiv \text{ id}$ to extract a conclusion - may still be carried out, providing $f$ has some properties. For the other cases of $f$ it may be modified accordingly. See here. Putting $\mathbb{R}$ instead of $\mathbb{Z}$ doesn't change the claim. The same graph theory approach may be used as in #5, but in this case, in order to cover the continuum nature of the domain, the vertices will be some ordinal numbers. The details here.
22.05.2020 20:47
pieater314159 wrote: Find all functions $f:\mathbb Z\to \mathbb Z$ such that for all surjective functions $g:\mathbb Z\to \mathbb Z$, $f+g$ is also surjective. (A function $g$ is surjective over $\mathbb Z$ if for all integers $y$, there exists an integer $x$ such that $g(x)=y$.) Proposed by Sean Li Answer- $f(x)=t$ for some constant $t\in\mathbb{Z}$ Proof- Let $f$ be a function satisfying given conditions , we try to construct a $g$ inductively such that $0$ does not belong to range of $f+g$ First let $\phi :\mathbb{N}_0\rightarrow\mathbb{Z}$ be the standard bijection given by $\phi (n)=(-1)^{n+1}\lfloor \frac{n+1}2\rfloor$ Now define $g(0)=k$ where $k$ is such that $k+f(0)\neq 0$ and $\phi^{-1}(k)$ is min. Define $g(\phi(n))=k$ such that $k$ is not already taken and $f(\phi(n))+k\neq 0$ and $\phi^{-1}(k)$ is least. But by assumption we get that such a $g$ cannot be surjective . Hence there exists a $c\in \mathbb{Z}$ such that $c$ does not lie in range of $g$ . Consider a $n>\phi^{-1}(c)$ then while defining $g(\phi (n))$ we have that $c$ is not already taken and as $n>\phi^{-1}(c)$ and already $n$ numbers have been defined we have that $c$ has least $\phi^{-1}(c)$ and hence the only way that $g(\phi (n))\neq c$ is if $f(\phi (n))=-c$ So for $n>\phi^{-1}(c)$ we have $f(\phi (n))=-c$ , now by looking at definition of $\phi$ we get that There exists a $M$ such that for all $n$ with $|n|>M, f(n)=-c$ If possible let $f(a)\neq -c$ for some $a$ then we define $g$ as follows Let $N=max(a,M)+1$ Define $g(a)=c$ and for $n<N ,n\in\mathbb{Z}, n\neq a$ define $g(n)=-f(n)+1$ so that $f(n)+g(n)=0$ does not hold for any $n<N$. Now define $g(N+n)=\phi(n)$ for all $n\in\mathbb{N}_0$ and $n\neq \phi^{-1}(c)$ and define $g(\phi^{-1}(c))=-c+1$ As $f(m)=-c$ $ \forall m\geq N$ we get that $f(m)+g(m)\neq 0$ $ \forall m\in \mathbb{Z}$ Moreover as $\phi$ is a bijection and $g(a)=c$ we get that $g$ is surjective whereas $f+g$ is not Contradiction Hence $f(n)=-c $ for all $n\in\mathbb{Z}$ Hence proved.
27.12.2020 06:55
The only function $f$ is a constant function, which obviously works. Assume $f$ takes on more than $1$ value. Consider all the values $f$ takes; we can create a graph on them such that each value has outdegree $1$. We will construct a "bad" $g$. For each value $v$, let $S$ be the set such that for every $x\in S$, we have $f(x) = v$. Now, choose an arbitrary $x$ in $S$, if $k$ was the endpoint of the edge starting at $v$, let $g(x)$ be $-k$. Now, consider every $y$ such that $g(y)$ hasn't been defined yet. Define the set $T$ as the set such that for all $k\in T$, $f$ does not take on $-k$. For each $y$ such that $g(y)$ hasn't been defined, we take a mapping from $g$ to $T$. This means there are no $y$ such that $g(y) + f(y) = 0$, so it's not surjective.
01.07.2021 23:17
I claim that the only solutions are when $f$ is constant, which clearly work. Otherwise, let $F$ be the range of $f$, where $|F|\geq 2$, and for all $y_i \in F$ consider the $x_i$ with smallest absolute value such that \[f(x_i)=y_i\]Then, we construct a function $g$ such that for all $x_i$, taking mod $|F|$, let \[g(x_i) = -y_{i+1}\]Thus, for all $x_i$, \[f(x_i)+g(x_i)= y_i - y_{i+1} \neq 0 \text{ , since $|F|\geq 2$}\]Then, for all other $a\in \mathbb{Z},a\notin -F$, there for all $b$, $f(b)\neq -a$, choose one and let $g(b)=a$. Thus, we may hit all $a$ not in $-F$, and our cyclic $g(x_i)=-y_{i+1}$ hits all values in $-F$. Thus, we have constructed a surjective function $g$, which does not satisfy $f+g$ is surjective because 0 is never hit, so we are done. Remark: This may be a fakesolve due to the $|F|=\infty$ case being a bit unstable.
14.08.2021 15:17
Let g be a surjective function $\Rightarrow f+g $ is surjective $\Rightarrow f+g+g$ is surjective $ f+f+g+g$ but $(f+f+g+g)(x)=2(f(x)+g(x))$ thus this function cannot equal any odd integers $\Rightarrow\Leftarrow$
22.09.2021 20:40
Can someone please check if this proof works: It is easy to check that constant function works.We will prove that no non-constant function $f$ satisfies the problems condition.Let $f$ be any non-constant function.We will construct a surjective function $g:\mathbb Z\to \mathbb Z$ such that $f+g$ is not surjective. Since $f$ is non-constant there is distinct $a,b\in R_f$.For any $a\in R_f$ let, $$T_a=\{x|f(x)=a-x\}$$Observe that any $T_a,T_b$ are disjoint. If atleast one of $T_a,T_b$ is empty then take $g(x)=x,\forall x\in \mathbb Z$.Then atleast one of $a,b\not\in R_{f+g}$.Otherwise assume both are non-empty.Now few cases may arise. Case-1 First assume that $T_a\cup T_b$ is an infinite set.So atleast one of $T_a,T_b$ is infinite.Observe that for any $x\in T_a\cup T_b$ there are atmost 2 integers $m_x,n_x$ in $T_a\cup T_b$ such that $f(x)+m=a\ \text{or}\ \ b$ and $f(x)+n=a\ \text{or}\ \ b$ Construct $g$ such a way that $g(T_a\cup T_b)=T_a\cup T_b$ and $f(x)\ne m_x,n_x$ in $A\cup B$.This is possible since $T_a\cup T_b$ is countable infinite set.Also set $g(x)=x$ outside $T_a\cup T_b$.Observe that $f(x)+g(x)\ne a,b$ for all $x\in \mathbb Z$.But $g$ is surjective,by construction. Case-2 In this assume both $T_a,T_b$ are finite and $|T_a\cup T_b|\ge 3$.The idea is to construct $g(x)=x$ outside $T_a\cup T_b$ and $g(T_a\cup T_b)=T_a\cup T_b$ so that $g(x)+f(x)\ne a$.Observe that $\forall x\in \mathbb Z-(T_a\cup T_b),f(x)+g(x)\ne a$.So we need to work only within $T_a\cup T_b$. For any $x\in T_a\cup T_b$ there is atmost one $m_x\in T_a\cup T_b$ such that $f(x)+m_x=a$.So for any $x\in T_a\cup T_b$ there is atleast $|T_a\cup T_b|-1\ge 2$ integers $t_x\in T_a\cup T_b$ such that $g(x)+t_x\ne a$.Construct the graph joining this $x$ to all these $t_x$.From here there is a perfect matching $H$ with 2 parts $T_a\cup T_b$ and $T_a\cup T_b$. So take $g$ to be the function which maps $x$ to its corresponding element wrt. $H$. $g$ is surjective but $a\not\in R_{f+g}$. Case-3 Assume $|T_a\cup T_b|=2$.If we can find any other distinct $m,n\in R_f$ so that $T _m\cup T_n\ge 3$ then we will start our work with this $T_m,T_n$ and proceed like previous cases.Otherwise for all $m\ne n\in R_f$ respective $T_m,T_n$ are singleton set.So $T_m=\{r_m\} ,T_n=\{r_n\} $,So $f(r_m)=m-r_m.f(r_n)=n-r_n$. If we can find $m,n\in R_f$ such that $m-r_m\ne n-r_n$,then take $g(x)=x\forall x\in\mathbb Z-(T_m\cup T_n)$ and $g(r_m)=r_n,g(r_n)=r_m$.Then $$f(r_m)+g(r_m)=m-r_m+s_n\ne n,\qquad f(r_n)+g(r_n)=n-r_n+r_m\ne n$$so $n\not\in R_{f+g}$ Otherwise assume that, for any distinct $m,n\in R_f, m-r_m=n-r_n$.Fix any $m\ne n\in R_f$ Let there is $c\ne r_m,r_n$ such that $f(c)\ne f(r_m)$.Then take $g(c)=r_m,g(r_m)=c$ and g(x)=x for any other $x$. Then, $$f(c)+g(c)=f(c)+r_m\ne f(r_m)+r_m=m$$$$f(r_m)+g(r_m)=m-r_m+c\ne m$$And $f(x)+g(x)=f(x)+x=m$ can,t hold outside $T_m$ Finally assume no such $c$ exists.Then $f(x)=f(m)$ for all $x\ne r_m.r_n$.So atmost $2$ numbers are in the range of $f$,with $f(x)=f(m)$ for all $x\ne r_m,r_n$ and $f(r_m)=f(r_n)=m-r_m=n-r_n$ Then take $g(r_m)=g(r_n)=-f(m)$ and $g(\mathbb Z-\{r_m,r_n\})=\mathbb Z-\{f(m\}$. In this case $0\not\in R_{f+g}$.$\blacksquare$
16.10.2021 04:53
The answer is all $f$ which is a constant, the checking is trivial. Now suppose $f$ is non-constant. For each integer $c$ define $$S_c=\{x:f(x)<c\}$$$$T_c=\{x:f(x)\geq c\}$$We divide into three cases: Case I: There exists $c$ such that both $S_c$ and $T_c$ are infinite sets Label the elements in $S_c$ and $T_c$ by $a_1,a_2,...$ and $b_0,b_1,b_2,...$, define $g$ by $$g(a_i)=-i$$$$g(b_i)=i$$Then it is easy to see that $c-1$ does not belong to the range of $f+g$, contradiction. Now $f$ is bounded, by multiplying $-1$ and shifting if necessary we may assume it is bounded below by $0$. Case II: $S_c$ is infinite for some $c$ Then from Case $I$ $T_c$ must be finite, so $f$ must be bounded above. Suppose $0\leq m\leq f\leq M$. Pick $n=M+1$. If there exists two numbers say $c_1,c_2$ which is the image of infinitely many integers under $f$, define $g$ by setting $g(c_1+an)\equiv c_2\pmod n $ and $g(c_2+bn)\equiv c_1 \pmod n$ then $f+g$ is not surjective mod $n$, contradiction. Therefore, $f$ is a constant except finitely many values. Suppose $f(x_i)=y_i$ for some $y_1<...<y_m$ and $f(k)=0$ if $k\neq x_1,...,x_m$. Suppose $x_{b_1}\leq x_{b_2}\leq...\leq x_{b_m}$, define $$g(x)=\begin{cases}x &\text{ if $x\neq x_1,...,x_m$}\\ x_{b_i}&\text{ if $x=x_i$}\end{cases}$$, then we need $$(x_1+y_{b_1},x_2+y_{b_2},...,x_m+y_{b_m})=(x_1,...,x_m)$$hence $y_{b_i}=0$ as desired. Case III: $S_c$ is finite for all $c$. Then the preimage of all integers is finite. We order the preimage of integers under $g$ with the order $1,-1,2,-2,...$. For the first unordered integer $x$ we assign it to the smallest unoccupied integer $y$ such that $x+y>0$. Then obviously the image of $f+g$ must be positive, contradiction.
22.10.2021 01:16
Only the constants work; proving their validity is trivial, so we will assume FTSOC that a nonconstant $f$ exists, and we will construct a surjective $g$ such that $f+g$ has no zeroes. Define the x-bin as the set of all integers $n$ such that $f(n)=x$. Suppose that we have at least two but finitely many bins indexed $a_1,a_2\ldots a_m$, then we can let $g$ access the value $-a_m$ in bin $a_{m+1}$ (where indices are cyclic mod $m$). Otherwise, if there is a countably infinite amount of bins, we can line up the bins in an arbitrary order and assign the value $0,1,-1,2,-2\ldots$ in this order to the frontmost bins that don't have indices $0,-1,1,-2,2\ldots$.
25.01.2022 01:36
Fix $f$. We may as well assume $f$ and $g$ have domain $\mathbb{N}$ instead of $\mathbb{Z}$ since all that matter is both are countable. We will try to construct a surjective function $g$ for which $f+g$ never hits the value $100$, i.e. $g(a)\not = 100-f(a)$ for all $a\in \mathbb{Z}$. Define $r_a=100-f(a)$, so then we want to construct a surjective $g$ for which each value $a$ in $\mathbb{Z}$ has one restricted value $r_a$ that cannot be the $g$-value. Case 1: $f$ is not eventually constant. BASIC ALGORITHM: We will demonstrate an algorithm to construct a surjective function $\mathbb{N} \to \mathbb{Z}$. Essentially the interval of the range is initially empty, and then expand it on either side at each step. If the current range of $g$ is an interval, we can always continue such an algorithm by adding onto either side of the interval on later steps. MODIFIED ALGORITHM: Say at some point during the basic algorithm you have to map a value $x$ to its restricted value $r_x$. Let $y$ be the maximal number for which $r_x=r_{x+1}=\cdots=r_y$. This exists since $f$ is not eventually constant. If $r_x$ is positive, instead map $x \to r_x+1$ and $x+1\to r_x+2$, and so on till $y\to r_x+(y-x+1)$, and if $x$ is negative, instead map $x\to r_x-1$ and $x+1\to r_x-2$ and so on till $y\to r_x-(y-x+1)$. Then map $y+1\to r_x$. These are all valid since $r_x,r_{x+1},\ldots,r_y=r_x$. The final step is valid since $r_{y+1}\not = r_x$. Now, $1,\ldots,y$ map to a new interval which the interval that $1,\ldots,x-1$ mapped to but with one side of the interval extended some. So we can continue with the basic algorithm, and refer to the modified algorithm in case of another issue. Case 2: $f$ is eventually constant. The above algorithm fails when $f$ is eventually constant. WLOG $f$ is eventually constant at the value $0$. Suppose $f(n)=0$ for all $n\ge N$. If $f$ is not constant at $0$, there exists some $k<N$ for which $f(k)\not = 0$. Let $M=\max \{ f(0),\ldots,f(N-1)\}$. Construct $g$ as follows: first let $g(k)=f(k)$, and let $g(x)=-M-10^6|f(k)|$ for $x\in [0,N)\setminus \{k\}$. So basically we leave $(f+g)(k)$ at $f(k)$, and move all other things in $x=0,\ldots,N-1$ to well below $f(k)$. Now starting at $x=N$, do the normal bijection $\mathbb{N}\to \mathbb{Z}$, i.e. $(N,N+1,N+2,\ldots)\mapsto (0,1,-1,2,-2,\ldots)$, but skip the value $f(k)$ in the output. So now $g$ outputs every integer -- including $f(k)$. But $f+g$ never outputs the value $f(k)$, since $(f+g)(k)=f(k)+g(k) \not = 0 + f(k) = f(k)$, and we skip $f(k)$ in the final step, and every value before the final step is well below $f(k)$. Hence $f+g$ is not surjective. We just have to deal with the case $f$ constant, and in fact those work.
25.01.2022 07:32
The answer is only constant $f$, which clearly work. Let $a$ be some constant, if $f$ is nonconstant, we will construct a $g$ such that $g(x) \neq a- f(x)$ so $f+g$ is not surjective. Clearly, this is just saying, for each value of $n$, there is exactly one value, call it $h(n)$, which is not allowed to be assigned to $g$. If $f$ is nonconstant, this $h$ is not constant either. Consider the following algorithm, we'll start with $0, 1, -1, 2, -2, 3, -3, \cdots$ and so on. Each time, suppose the number we're at is $k$, because $h$ is not constant there exists a $z$ such that $h(z) \neq k$, so we'll make $g(k) = z$, the only problem is if every possible $z$ was already assigned earlier, to say $m$, let $p$ be a number with $h(p) = k$ (if no such $p$ then we could have chosen a $z$ since only finitely many have been chosen so far). So now just swap them, as in change $g(m) = p$ and $g(k) = z$, which is possible. This way, we may define $g$ on every number such that $f+g$, so we are done. $\blacksquare$
12.06.2023 17:18
\[\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\] The answer is constant functions only, which all work. Assume now that $f$ is nonconstant. We show there exists a surjective function $g$ such that $f+g$ has no zeroes. Case 1: The image of $f$ is a finite set. Let $a_1, a_2, \ldots, a_n$ denote the values in the image of $f$. Let $b_1, b_2, \ldots, b_n$ be a fixed sequence of integers such that $f(b_i) = a_i$ for all $1\le i\le n$. We construct $g$ in the following way: i) $g(b_i) = -a_{i+1}$ for all $1\le i\le n$ (indices taken modulo $n$) ii) $g(x) = x$ for all integers $x$ not in the multiset $\{-a_1, -a_2, \ldots, -a_n, b_1, b_2, \ldots, b_n\}$. iii) Define $g(x)$ over $x\in \{-a_1, -a_2, \ldots, -a_n\}$ to take all values of $b_i$ not yet taken by $g$, and for all remaining values anything larger than $|\max(a_i)| + |\max(b_i)|$. The function is surjective and $f + g $ has no zeroes. Case 2: The image of $f$ is an infinite set. Call the image of $f$ $a_1, a_2, \ldots,$ We perform the following algorithm: At the $n$th step, assign $g$ to all $x$ such that $f(x) = a_n$, and let $g(x) = C$, where $C$ is an integer with minimal absolute value such that $C$ is not taken by $g$ already and $C\ne -a_n$. We can see this function works.
09.09.2023 23:07
The answer is all constant functions. Assume that $S = \operatorname{img } f$ has at least two distinct elements. Let $k_1$ and $k_2$ be two that are consecutive when $S$ is ordered. I claim that we can make $f+g$ omit $(k_1, k_2]$. This can be done as follows: for any $k < k_1 \in S$ and $f(x) = k$, allocate to $g(x)$ the largest negative value not already in the image of $g$. Similarly, for $k > k_2 \in S$ and $f(x) = k$, allocate to $g(x)$ the smallest nonnegative value not already in the image of $g$. Then it is clear that $g$ is surjective, but $f+g$ omits $(k_1, k_2]$, thus done.
10.12.2023 19:28
The answer is constant functions only, which clearly works. Claim: If $f(x)=c$ for infinitely many $x$, then we must have $f(x)=c$ for all $x$. Suppose otherwise. Then, let $g(x)=-c$ for all $x$ with $f(x)\neq c$, and on the infinitely many values of $x$ for which $f(x)=c$, we can have $g$ cover all integers other than $-c$ to make it surjective. However, $f+g$ never equals 0, contradiction. From now on, assume that each value occurs only finitely many times in $f$. In particular, for each value, there are infinitely many inputs for which it does not occur. We will employ a "just do it" approach, where we make $g$ attain each positive integer without ever reaching $f+g=0$. We need $g$ to attain 0, so we let that happen on any of the infinitely many places where $f$ is not 0. Then, we need $g$ to attain $1$, so let that happen in any of the infinitely many places where $f$ is not $-1$ and is not taken yet. Repeat the same with $-1,2,-2,3,-3\dots.$ At any point, when we are adding $c$, there are infinitely many inputs where $f$ is not equal to $-c$, and at most finitely many have already been "taken". Since there are countably many things to achieve here, we can construction such a surjective function $g$, so we are done.
29.01.2024 13:12
Answer: All constant functions. It's obvious that constant function works. Now assume $|\text{Im}(f)| > 1$. Let $a < b$ be two elements that are consecutive when $\text{Im}(f)$ is ordered. We'll construct $g$ such that $f+g$ omits $(a, b]$. For any $k < a \in \text{Im}(f)$ and $f(x) = k$, put $g(x)$ to be largest negative value not already in the image of $g$. Similarly, for $k > b \in \text{Im}(f)$ and $f(x) = k$, put $g(x)$ to be the smallest nonnegative value that not already in the image of $g$. Then $g$ is obviously surjective and omits $(a, b]$. $\blacksquare$
29.02.2024 08:31
We show that only constant functions work. If $f$ is surjective, take $f=-g$. Assume that $f$ is non-constant. Suppose there is some number $c$ such that the set $\{x:f(x)=c\}$ is infinite. Note that since $f$ is non-constant, there is some $d$ such that $f(d)\ne c$. Now take a function $g$ such that the image of set $\{x:f(x)=c\}$ is $g$ takes all integers except $-c$. Take $g(d)=-c$. For all other numbers take image as $1-f$. Then, $0$ is not taken by any number but $g$ is surjective. So we are done with this case. The function we consider now has a finite pre-image at every image. So, for any $c$, take the smallest number $M$ such that $f(x)\ne c$ if $x\geq M$. Then, set $g(x)=-c$ for each $x\geq M$. We get the contradiction.
17.10.2024 05:41
Suppose $f$ is not constant, than we can find at least two different values, now let $S$ be a dictionary of values $a:b$ such that $f(a)=b$, now suppose the set of obtained values is finite than we can clearly make a surjective function such that the result holds. If it is infinite, than we can pick positions for $-b$ where there is some $a$ in $S$ such that $a:b$, than we know that either the positive or negative direction contains infinitely many different values in its image, let that direction be the positive direction and consider the positive values, for each value that appears in the image we can always find a value that isn't the same as it in the positive direction, suppose we choose the first value to be $i$, than we let $g(i)$ be the negative of that first value in the image, than for the next value in the image we can find a value past $i$ such that its not the same as that value, and by repeating this process we get that the positive contains the negatives of all the values in the image and now we can place the remaining values wherever we want.
08.11.2024 19:04
The answer is just when $f$ is constant, which clearly works. Otherwise, let's construct a function $g$ such that $f-g$ never reaches $0$, then $-g$ works. So $g(x)\ne f(x)$ for all $x$. Let's casework on whether there is some $y$ such that $f(x)\ne y$ for only finitely many $x$. If not, then we will go in the order $n=0,1,-1,2,-2,3,-3,\dots$ and just choose some $x$ to let $g(x)=n$. We'll never run out since we only used finitely many $x$ before and infinitely many of them work. If yes, then choose something to map to $y$ first, then do the rest of the numbers the same way as the previous case. $\blacksquare$