, 2012

Solution:
The largest possible $m$ is equal to $2^{n}$.

In order to see that the value $2^{n}$ can be indeed achieved, consider all binary vectors of length $n$ as rows of the table. We now proceed with proving that this is the maximum value.

Let $[a_{k}^{i}]$ be a feasible table, where $i=1, \ldots, m$ and $k=1, \ldots, n$. Let us define undirected graphs $G_{1}, G_{2}, \ldots, G_{n}$, each with vertex set $\{1,2, \ldots, m\}$, where $ij \in E(G_{k})$ if and only if $|a_{k}^{i}-a_{k}^{j}|=1$ (by $E(G_{k})$ we denote the edge set of the graph $G_{k}$). Observe the following two properties.

(1) Each graph $G_{k}$ is bipartite. Indeed, if it contained a cycle of odd length, then the sum of $\pm 1$ along this cycle would need to be equal to $0$, which contradicts the length of the cycle being odd.

(2) For every $i \neq j$, $ij \in E(G_{k})$ for some $k$. This follows directly from the problem statement.

For every graph $G_{k}$ fix some bipartition $(A_{k}, B_{k})$ of $\{1,2, \ldots, m\}$, i.e., a partition of $\{1,2, \ldots, m\}$ into two disjoint sets $A_{k}, B_{k}$ such that the edges of $G_{k}$ traverse only between $A_{k}$ and $B_{k}$. If $m>2^{n}$, then there are two distinct indices $i, j$ such that they belong to exactly the same parts $A_{k}, B_{k}$, that is, $i \in A_{k}$ if and only if $j \in A_{k}$ for all $k=1,2, \ldots, n$. However, this means that the edge $ij$ cannot be present in any of the graphs $G_{1}, G_{2}, \ldots, G_{n}$, which contradicts (2). Therefore, $m \leq 2^{n}$.

Solution 2:
In any table with the given property, the least and greatest values in a column cannot differ by more than $1$. Thus, if each value that is neither least nor greatest in its column is changed to be equal to either the least or the greatest value in its column (arbitrarily), this does not affect any $|a_{i}-b_{i}|=1$, nor does it increase any difference above $1$, so the table still has that given property. But after such a change, for any choice of what the least and greatest values in each column are, there are only two possible choices for each entry in the table (either the least or the greatest value in its column); that is, only $2^{n}$ possible distinct rows, and the given property implies that all rows must be distinct. As in the previous solution, we see that this number can be achieved.

Solution 3:
We prove by induction on $n$ that $m \leq 2^{n}$.

First suppose $n=1$. If real numbers $x$ and $y$ have $|x-y|=1$ then $\lfloor x\rfloor$ and $\lfloor y\rfloor$ have opposite parities and hence it is impossible to find three real numbers with all differences $1$. Thus $m \leq 2$.

Suppose instead $n>1$. Let $a$ be the smallest number appearing in the first column of the table; then every entry in the first column of the table lies in the interval $[a, a+1]$. Let $A$ be the collection of rows with first entry $a$ and $B$ be the collection of rows with first entry in $(a, a+1]$. No two rows in $A$ differ by $1$ in their first entries, so if we list the rows in $A$ and delete their first entries we obtain a table satisfying the conditions of the problem with $n$ replaced by $n-1$; thus, by the induction hypothesis, there are at most $2^{n-1}$ rows in $A$. Similarly, there are at most $2^{n-1}$ rows in $B$. Hence $m \leq 2^{n-1}+2^{n-1}=2^{n}$. As before, this number can be achieved.

Solution 4:
Consider the rows of the table as points of $\mathbb{R}^{n}$. As the values in each column differ by at most $1$, these points must lie in some $n$-dimensional unit cube $C$. Consider the unit cubes centred on each of the $m$ points. The conditions of the problem imply that the interiors of these unit cubes are pairwise disjoint. But now $C$ has volume $1$, and each of these cubes intersects $C$ in volume at least $2^{-n}$: indeed, if the unit cube centred on a point of $C$ is divided into $2^{n}$ cubes of equal size then one of these cubes must lie entirely within $C$. Hence $m \leq 2^{n}$. As before, this number can be achieved.

Solution 5:
Again consider the rows of the table as points of $\mathbb{R}^{n}$. The conditions of the problem imply that these points must all lie in some $n$-dimensional unit cube $C$, but no two of the points lie in any smaller cube. Thus if $C$ is divided into $2^{n}$ equally-sized subcubes, each of these subcubes contains at most one row of the table, giving $m \leq 2^{n}$. As before, this number can be achieved.