Someone asked me whether sets $A,B$ of integers such that $A\cap B=\emptyset$ and $A\times B\rightarrow\mathbb{Z}$, $(a,b)\mapsto a+b$ is bijective exist. First I tried to construct such $A,B$ by the following algorithm:
SET $m=0$, $A=\{0\}$, $B=\{-1\}$;
WHILE (True) {
IF ($m\not\in A+B$) THEN {
$A \leftarrow A\cup\{m-\mathrm{Min}(B)\}$;
};
IF ($-m\not\in A+B$) THEN {
$B \leftarrow B\cup\{-m-\mathrm{Max}(A)\}$;
};
$m \leftarrow m+1$
};
Here, $A+B=\{a+b\;|\;a\in A, b\in B\}$. I confirmed this works for $m=0,1,\cdots,170$ and conjectured that the sets $A,B$ defined by this argorithm are
$$A=\{a_{0}+\sum_{i=1}^{N}a_{i}2^{2i-1}\;|\;a_{0},a_{i}\in\{0,1\}\},\quad B=\{-1-\sum_{i=1}^{N}b_{i}2^{2i}\;|\;b_{i}\in\{0,1\}\},$$
and if we change the initial settings of $A,B$ to $A=\{1\}$, $B=\{-1\}$, then we will obtain
$$A=\{1+\sum_{i=0}^{N}a_{i}2^{2i}\;|\;a_{i}\in\{0,1\}\},\quad B=\{-1-\sum_{i=0}^{N}b_{i}2^{2i+1}\;|\;b_{i}\in\{0,1\}\}.$$
For the $A,B$ just above, the injectivity of $A\times B\rightarrow\mathbb{Z}$, $(a,b)\mapsto a+b$ is obvious. Indeed, if $a+b=a'+b'$ for $a,a'\in A$, $b,b'\in B$, then by comparing each bit of both sides of $a-b'-2=a'-b-2$, we have $a=a'$, $b=b'$.
But for now, when trying to prove the surjectivity, carry/borrow processing seems complicated and I cannot complete the proof yet.
Any help would be appreciated.
Let $n$ be an arbitrary integer. Divide $n$ one after another by $-2$ and take the remainders (in $\{0,1\}$): $n=q_{0}(-2)+n_{0}$, $q_{0}=q_{1}(-2)+n_{1}$, .... Since $|n|\geq|q_{0}|\geq|q_{1}|\geq\cdots$ and if $|q_{i}|=|q_{i+1}|$ then $q_{i}=0$ or $q_{i}=-1$, we have some N such that $q_{N}=0$. Then $n=\sum_{i=0}^{N}n_{i}(-2)^{i}$.
Appendix.
After the title issue was solved, I continued to try to find out why the algorithm worked well. It was much harder than the original problem. I don't know if anyone (other than me) is interested, but I finally got it so I'll add it here.
It seems appropriate that we discuss in the case started from $A=\{1\}$, $B=\{-1\}$. Intuitively, we can overview how the algorithm works if we follow the algorithm while representing $m$ and $-m$ by negabinary. The image below is a table of first few steps (BN=binary, NB=negabinary):
To download a whole Excel file, follow this link (if you don't mind to navigate a Japanese site) and click on the blue down-arrow icon or an open-folder icon.
To show precisely that the algorithm which started from $A=\{1\}$, $B=\{-1\}$ defines $A=\{1+\sum_{i=0}^{N}a_{i}2^{2i}\;|\;a_{i}\in\{0,1\}\}$, $B=\{-1-\sum_{i=0}^{N}b_{i}2^{2i+1}\;|\;b_{i}\in\{0,1\}\}$, we arrange all integers in the lexicographic order on negabinary representations, which we denote by $\prec$. In particular, $0\prec 1\prec -2\prec -1\prec 4\prec 5\prec 2\prec 3\prec -8\prec\dotsb$. This is a (strict) total order on $\mathbb{Z}$.
We add labels ($\ast$), ($\ast\ast$), and ($\ast\ast\ast$) to three places in the algorithm:
Put $\mathfrak{A}:=\{\sum_{i=0}^{N}a_{i}2^{2i}\;|\;a_{i}\in\{0,1\}\}$, $\mathfrak{B}:=\{-\sum_{i=0}^{N}b_{i}2^{2i+1}\;|\;b_{i}\in\{0,1\}\}$, and define $\alpha : \mathbb{Z}\rightarrow\mathfrak{A}$, $\beta : \mathbb{Z}\rightarrow\mathfrak{B}$ so that $n=\alpha(n)+\beta(n)$ for all $n\in\mathbb{Z}$. For $m=0,1,2,\dotsc$, set $$ M_{m}:=\mathrm{Max}_{\prec}(\{\alpha(n)\;|\;n\in\mathbb{Z}, |n|\leq m\}\cup\{\beta(n)\;|\;n\in\mathbb{Z}, |n|\leq m\}). $$ We want to prove by an induction on $m$, that $$ A=\{1+\alpha'\;|\;\alpha'\in\mathfrak{A},\,\alpha'\preceq M_{m}\},\quad B=\{-1+\beta'\;|\;\beta'\in\mathfrak{B},\,\beta'\preceq M_{m}\} \tag{1} $$ holds at ($\ast\ast\ast$) in every WHILE loop.
When $m=0$, $(1)$ clearly holds at ($\ast\ast\ast$). Let $m>0$ in the following. We will discuss the four cases below separately:
(i) $m\in A+B$ and $-m\in A+B$ at ($\ast$),
(ii) $m\not\in A+B$ and $-m\in A+B$ at ($\ast$),
(iii) $m\in A+B$ and $-m\not\in A+B$ at ($\ast$),
(iv) $m\not\in A+B$ and $-m\not\in A+B$ at ($\ast$).
(i) In this case, $A,B$ do not change. By the induction hypothesis, $\alpha(m),\beta(m)\preceq M_{m-1}$, $\alpha(-m),\beta(-m)\preceq M_{m-1}$, and then $M_{m}=M_{m-1}$. Hence $(1)$ still holds at ($\ast\ast\ast$).
(ii) Since $m>0$, $\alpha(m)>-\beta(m)$, and then $\alpha(m)\succ\beta(m)$. If $\alpha(m)\preceq M_{m-1}$, then $m\in A+B$ by the induction hypothesis. Thus $M_{m-1}\prec\alpha(m)$ in this case (ii). Furthermore, there is no $\beta'\in\mathfrak{B}$ such that $\beta(m)\prec\beta'\prec\alpha(m)$: if such a $\beta'$ exists, $0<\alpha(m)+\beta'<m$ and then $\alpha(m)=\alpha(\alpha(m)+\beta')\preceq M_{m-1}\prec\alpha(m)$, a contradiction. Hence if we write $\alpha(m)=\sum_{i=0}^{N}a_{i}2^{2i}$ ($a_{i}\in\{0,1\}$, $a_{N}=1$), we have $\beta(m)=-\sum_{i=0}^{N-1}2^{2i+1}$ (when $N>0$) or $0$ (when $N=0$). So we see $\alpha(m)+\sum_{i=0}^{N}(1-a_{i})2^{2i}+2\beta(m)=1$. Thus $-m+1=\sum_{i=0}^{N}(1-a_{i})2^{2i}+\beta(m)$. In particular, we have $\beta(m)=\beta(-m+1)\preceq M_{m-1}$. Hence $-1+\beta(m)\in B$ at ($\ast$) by the induction hypothesis. As we already shown, there is no element in $\mathfrak{B}$ between $\beta(m)$ and $M_{m-1}$ with respect to the order $\prec$. This implies $\beta(m)=\mathrm{Min}(B)+1$. On the other hand, there is no $\alpha'\in\mathfrak{A}$ such that $M_{m-1}\prec\alpha'\prec\alpha(m)$: if such an $\alpha'$ exists, $0<\alpha'+\beta(m)<m$ since $\beta(m)\prec\alpha'\prec\alpha(m)$, and then $\alpha'=\alpha(\alpha'+\beta(m))\preceq M_{m-1}$, a contradiction. Therefore $m-\mathrm{Min}(B)=1+\alpha(m)$ is added to $A$ by the assignment in the algorithm, and there is no element in $\mathfrak{A}\cup\mathfrak{B}$ between $M_{m-1}$ and $\alpha(m)$ with respect to $\prec$. Since $-m\in A+B$ at ($\ast$), $\alpha(-m),\beta(-m)\preceq M_{m-1}$ by the induction hypothesis. Therefore $M_{m}=\alpha(m)$ and $(1)$ holds at ($\ast\ast\ast$) again.
(iii) Since $-m<0$, $\alpha(-m)<-\beta(-m)$, and then $\alpha(-m)\prec\beta(-m)$. If $\beta(-m)\preceq M_{m-1}$, then $-m\in A+B$ by the induction hypothesis. Thus $M_{m-1}\prec\beta(-m)$ in this case (iii). There is no $\alpha'\in\mathfrak{A}$ such that $\alpha(-m)\prec\alpha'\prec\beta(-m)$: if such an $\alpha'$ exists, $-m<\alpha'+\beta(-m)<0$ and then $\beta(-m)=\beta(\alpha'+\beta(-m))\preceq M_{m-1}\prec\beta(-m)$, a contradiction. Hence if we write $\beta(-m)=-\sum_{i=0}^{N}b_{i}2^{2i+1}$ ($b_{i}\in\{0,1\}$, $b_{N}=1$), we have $\alpha(-m)=\sum_{i=0}^{N}2^{2i}$. So we see $2\alpha(-m)+\beta(-m)-\sum_{i=0}^{N}(1-b_{i})2^{2i+1}=0$. Thus $m=\alpha(-m)-\sum_{i=0}^{N}(1-b_{i})2^{2i+1}$. In particular, we have $\alpha(-m)=\alpha(m)$. Since $m\in A+B$ at ($\ast$), $\alpha(m)\preceq M_{m-1}$ by the induction hypothesis. As we already shown, there is no element in $\mathfrak{A}$ between $\alpha(-m)$ and $M_{m-1}$ with respect to $\prec$. This implies $\alpha(-m)=\mathrm{Max}(A)-1$. On the other hand, there is no $\beta'\in\mathfrak{B}$ such that $M_{m-1}\prec\beta'\prec\beta(-m)$: if such a $\beta'$ exists, $-m<\alpha(-m)+\beta'<0$ since $\alpha(-m)\prec\beta'\prec\beta(-m)$, and then $\beta'=\beta(\alpha(-m)+\beta')\preceq M_{m-1}$, a contradiction. Therefore $-m-\mathrm{Max}(A)=-1+\beta(-m)$ is added to $B$ by the assignment in the algorithm, and there is no element in $\mathfrak{A}\cup\mathfrak{B}$ between $M_{m-1}$ and $\beta(-m)$ with respect to $\prec$. Hence we have $M_{m}=\beta(-m)$ and $(1)$ holds at ($\ast\ast\ast$) again.
(iv) By a similar argument to (ii), we have $\beta(m)=\mathrm{Min}(B)+1\preceq M_{m-1}\prec\alpha(m)$ and there is no element in $\mathfrak{A}\cup\mathfrak{B}$ between $M_{m-1}$ and $\alpha(m)$ with respect to $\prec$. Then, $1+\alpha(m)$ is added to $A$ by the assignment; since this number does not add any negative number to $A+B$, $-m\not\in A+B$ still holds at ($\ast\ast$). By a similar argument to (iii), we have $\alpha(-m)=\alpha(m)\prec\beta(-m)$ and there is no element in $\mathfrak{A}\cup\mathfrak{B}$ between $\alpha(m)$ and $\beta(-m)$ with respect to $\prec$. At ($\ast\ast$), we have $\alpha(-m)=\alpha(m)=\mathrm{Max}(A)-1$ with respect to the changed $A$. Hence $-m-\mathrm{Max}(A)=-1+\beta(-m)$ is added to $B$ by the assignment. Therefor $M_{m}=\beta(-m)$ and $(1)$ holds at ($\ast\ast\ast$) again.