BMO 2010 Shortlist

a) We shall prove that for a table $m\times m$ ($m\ge 2$) the answer is $n=2m-2$; in particular $n=4018$ for $m=2010$.

Denote by $a_{ij}$ the number written in the cell $(i,j)$ ($1\le i,j\le m$). Let $a$, $b$, $c$ and $d$ be numbers written in cells, which centers form a rectangle with the sides parallel to those of the table. Note that any move preserves the number $a-b+c-d$. Hence for any equilibrium table one has that $$a_{ij}-a_{kj}=c_{ik},a_{ji}-a_{jk}=d_{ik}(1)$$ Therefore, such a table is determined by $2m-1$ arbitrary parameters; for example, the numbers in the first row and the first column. Any such table is equilibrium. Indeed, by moves on the columns we may obtain equal numbers in the first row. It follows from (1) that the numbers in any row are equal. Then by moves on the rows we may achieve all the numbers in the table to be equal. As a consequence, for $n=2m-2$ we can construct an equilibrium table, containing $2m-1$ numbers: $2^0,2^1,\dots ,2^n$.

We shall show that this is the largest integer $n$, i.e. the numbers $2^0,2^1,\dots ,2^{2m-1}$ cannot be placed in an equilibrium table $m\times m$. We shall show a more general statement.

Lemma. The integers $b_1,\dots ,b_{2m}$ ($m\ge 2$) can be placed in a $m\times m$ equilibrium table if and only if there exists $p$, $2\le p\le m$, such that after a permutation of these numbers one has that $$b_1+\cdots +b_p=b_{m+1}+\cdots +b_{m+p}(2)$$ Proof. Assume that such a location is possible. We shall prove (2) by induction on $m$. For $m=2$ this follows from (1) for $p=2$.

Suppose that our statement is true for some $m-1\ge 2$. Consider an equilibrium table $m\times m$, containing the numbers $b_1,\dots ,b_{2m}$.

If some row and some column contains each at most one of these numbers, we delete this row and this column and we get an equilibrium table $(m-1)\times (m-1)$, containing at least $2m-2$ of the $b$'s. Applying the induction after a permutation of $b$'s the hypothesis gives (2).

Let some row contain at most one $b$, but none of the columns has this property. This means that every column contains exactly two $b$'s. We delete our row and the column that contains the respective $b$ if there is such $b$, or any column if there is no such $b$, and we get an equilibrium table $(m-1)\times (m-1)$, containing $2m-2$ of the $b$'s, and then we continue as above.

The situation is the same if some column contains at most one $b$, but no rows have this property.

It remains to consider the case, when any row and any column contain exactly two $b$'s. After permutations of the rows and columns we may assume that (after a permutation of $b$'s) $a_{ii}=b_i$ and $a_{i,i+1}=b_{m+i}$ for $1\le i\le p-1$, $a_{p1}=b_{m+p}$ for some $p\in \{2,\dots ,m\}$. Then $$a_{i1}+a_{1i}-a_{11}=b_i,a_{i1}+a_{1,i+1}-a_{11}=b_{m+i}(1\le i\le p-1),a_{p1}+a_{1p}-a_{11}=b_p.$$ Hence $b_i-b_{m+i}=a_{1i}-a_{1,i+1}$ for $1\le i\le p-1$ and $b_p-b_{m+p}=a_{1p}-a_{11}$. Summing up these equalities we get that $$\sum _{i=1}^p(b_i-b_{m+i})=\sum _{i=1}^{p-1}(b_i-b_{m+i})+(b_p-b_{m+p})=\sum _{i=1}^{p-1}(a_{1i}-a_{1,i+1})+(a_{1p}-a_{11})=0$$ and (2) is proved.

Conversely, if (2) holds for some $p\in \{2,\dots ,m\}$ (possible not unique), we set $a_{ii}=b_i$ and $a_{i,i+1}=b_{m+i}$ for $1\le i\le p-1$, $a_{p1}=b_{m+p}$. If $p<m$, we place others $b$'s by following: $a_{i1}=b_i$, $a_{1,i}=b_{m+i}$ for $p+1\le i\le m$. Using (1) we determine consecutively the missing elements in the first row and the first column $a_{21},a_{13},a_{31},\dots ,a_{1p}$. It is easy to check that (1) "completes" the table to an equilibrium one. The Lemma is proved. $\square$

Now suppose that there exists a $m\times m$ equilibrium table containing the numbers $2^0,2^1,\dots ,2^{2m-1}$. By Lemma it follows that for some $2p$ numbers among them the equality (2) holds. Dividing the both parts of the equality by the least term, we obtain an equality, where one term equals $1$ and all others are even, a contradiction.

b) Assume that the $m\times m$ equilibrium table contains the numbers $2^0,2^1,\dots ,2^{2m-1},k$. According to Lemma the equality (2) holds for some $2p$ numbers with $p\in \{2,\dots ,m\}$. By similar to given above reasons one concludes that the number $k$ must be involved in this equality. Assume that $k=b_1$. Then $k=(b_{m+1}+\cdots +b_{m+p})-(b_2+\cdots +b_p)$. The maximal value of $k$ is reach for $p=m$, and it is equal to $$k=(2^{m-1}+\cdots +2^{2m-2})-(2^0+\cdots +2^{m-2})=2^{2m-1}-2^m+1.$$ In particular, for $m=2010$ we obtain $k=2^{4019}-2^{2010}+1$. $\square$