Spring 2017, problem 48

Show that every bijective function $ f: \mathbb{Z}\rightarrow\mathbb{Z}$ can be written in the way $ f=u+v$ where $ u,v: \mathbb{Z}\rightarrow\mathbb{Z}$ are bijective functions.

Comments

1 year ago

This problem will be solved if we can find an $S\subseteq \mathbb Z\times \mathbb Z$ such that every row, column, and diagonal of the infinite grid $ \mathbb Z\times \mathbb Z$ contains exactly one point of $S$, where the $z^{th}$ diagonal of $\mathbb Z\times \mathbb Z$ is defined as $\{(x,y):x+y=z\}$. Supposing such an $S$ exists, then we can find bijections $u,v$ for which $f=u+v$ by letting $(u(z),v(z))$ be the unique point in $S$ on the diagonal $\{(x,y):x+y=f(z)\}$, for all $z\in \mathbb Z$.

We will contruct $S=\{s_1,s_2,s_3,\dots\}$ one point at a time. Order the integers by $0\prec 1\prec -1\prec 2\prec -2\prec\dots$.

Suppose $s_1,\dots,s_{n-1}$ have already been determined.

  1. If $n\equiv 1$ (mod 3): Let $z$ be the $\prec$-smallest integer such that the $z^{th}$ row of the infinite grid contains none of $\{s_1,\dots,s_{n-1}\}$. Choose $s_n$ to be any point in that row which does not share a column or diagonal with any of $\{s_1,\dots,s_{n-1}\}$.
  2. If $n\equiv 2$ (mod 3): Let $z$ be the $\prec$-smallest integer such that the $z^{th}$ column of the infinite grid contains none of $\{s_1,\dots,s_{n-1}\}$. Choose $s_n$ to be any point in that column which does not share a row or diagonal with any of $\{s_1,\dots,s_{n-1}\}$.
  3. If $n\equiv 0$ (mod 3): Let $z$ be the $\prec$-smallest integer such that the $z^{th}$ diagonal of the infinite grid contains none of $\{s_1,\dots,s_{n-1}\}$. Choose $s_n$ to be any point in that diagonal which does not share a row or column with any of $\{s_1,\dots,s_{n-1}\}$.

This construction ensures that for all $n$, the points $s_1,\dots,s_n$ are all in different rows, columns and diagonals, and furthermore that every row, column and diagonal is eventually occupied for large enough $n$.

1 year ago

Is this trivial?

If $f(x)$ is bijective, then both $f(x) \pm 1$ are bijective. We can then decompose $f(x)$ into $f(x)=(f(x)+1)+(f(x)-1)$

Post an answer:

To post an answer, please log in