
Problem 2. Let $n$ be a positive integer. Find the greatest possible integer $m$, in terms of $n$, with the following property: a table with $m$ rows and $n$ columns can be filled with real numbers in such a manner that for any two different rows $\left[a_{1}, a_{2}, \ldots, a_{n}\right]$ and $\left[b_{1}, b_{2}, \ldots, b_{n}\right]$ the following holds:

$$
\max \left(\left|a_{1}-b_{1}\right|,\left|a_{2}-b_{2}\right|, \ldots,\left|a_{n}-b_{n}\right|\right)=1
$$

## Origin. Poland (Tomasz Kobos).


Solution 1 (submitter). 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 $\left[a_{k}^{i}\right]$ 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 $i j \in E\left(G_{k}\right)$ if and only if $\left|a_{k}^{i}-a_{k}^{j}\right|=1$ (by $E\left(G_{k}\right)$ 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, i j \in E\left(G_{k}\right)$ for some $k$. This follows directly from the problem statement.

For every graph $G_{k}$ fix some bipartition $\left(A_{k}, B_{k}\right)$ 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 $i j$ cannot be present in any of the graphs $G_{1}, G_{2}$, $\ldots, G_{n}$, which contradicts (2). Therefore, $m \leq 2^{n}$.
