Filling the cells of a $\mathbb{N} \times\mathbb{N}$ grid My roommate proposed this question to me.
"Write a natural number into each cell of a $\mathbb{N} \times\mathbb{N}$ such that each number appears exactly once in every row and column."
I think I've been over-complicating things but I haven't been able to think of a solution. I thought perhaps it would have something to do with how we show that the rationals are countable or even deals with Cantor's Pairing Function.
Any thoughts on the solution? They are much appreciated.
 A: A pure brute-force approach works here.  Put numbers into the cells one at a time, and in each cell, write the smallest number that doesn't already appear in the same row or column.
The result is:
$$\begin{array}{cccccccccc}
0& 1& 2& 3& 4& 5& 6& 7& 8& 9\ldots \\
1& 0& 3& 2& 5& 4& 7& 6& 9& 8\ldots \\
2& 3& 0& 1& 6& 7& 4& 5& 10& 11\ldots \\
3& 2& 1& 0& 7& 6& 5& 4& 11& 10\ldots \\
4& 5& 6& 7& 0& 1& 2& 3& 12& 13\ldots \\
5& 4& 7& 6& 1& 0& 3& 2& 13& 12\ldots \\
6& 7& 4& 5& 2& 3& 0& 1& 14& 15\ldots \\
7& 6& 5& 4& 3& 2& 1& 0& 15& 14\ldots \\
8& 9& 10& 11& 12& 13& 14& 15& 0& 1\ldots \\
9& 8& 11& 10& 13& 12& 15& 14& 1& 0\ldots \\
\end{array}$$
It's not immediately obvious what is happening here, but the number in the $i$th row and $j$th column turns out to be equal to $i\oplus j$, which means that you write $i$ and $j$ in base 2 and then add, but without carrying.  Alternatively, write both $i$ and $j$ as a sum of distinct powers of 2 (this can be done in only one way); then $i\oplus j$ is the sum of all the powers of 2 that appear in either $i$ or in $j$ but not in both.
For example, one can find the number in row 5 and column 6 by computing $5=2^4+2^0$ and $6=2^4+2^1$, and the powers of 2 that appear only once are $2^1+2^0 = 3$.
(If you consider $0\notin\Bbb N$ then you can simply add 1 to every element of the table above.)
As pointed out in the comments, this operation turns out to be crucial in the analysis of certain combinatorial games; see Wikipedia's article on “nimbers” for example.
A: Using Brian M. Scott's alternative hint, define the bijection $f\colon \mathbb N \to \mathbb Z$ by:
$$
f(x) = \begin{cases}
\frac{x}{2} &\text{if $x$ is even} \\
\frac{1 - x}{2} &\text{if $x$ is odd} \\
\end{cases}
$$
whose inverse is given by:
$$
f^{-1}(y) = \begin{cases}
2y &\text{if }y > 0 \\
-2y + 1 &\text{if }y \leq 0 \\
\end{cases}
$$
Then the natural number that should go in the $m^\text{th}$ row and the $n^\text{th}$ column is given by:
$$
a_{m,n} = f^{-1}(f(m) + f(n))
$$
The first few rows and columns should look like:
\begin{array}{c|cccccc}
\\\hline
& 1 & 2 & 3 & 4 & 5 & \cdots \\
& 2 & 4 & 1 & 6 & 3 & \cdots \\
& 3 & 1 & 5 & 2 & 7 & \cdots \\
& 4 & 6 & 2 & 8 & 1 & \cdots \\
& 5 & 3 & 7 & 1 & 9 & \cdots \\
& \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\
\end{array}
