Integers are written in the cells of a table $2010 \times 2010$. Adding $1$ to all the numbers in a row or in a column is called a move. We say that a table is equilibrium if one can obtain after finitely many moves a table in which all the numbers are equal. Find the largest positive integer $n$, for which there exists an equilibrium table containing the numbers $2^0, 2^1, \ldots , 2^n$. For this $n$, find the maximal number that may be contained in such a table.
Problem
Source: Balkan MO 2010 ShortList C4
Tags:
Gomes17
08.04.2020 18:44
A table $T$ with entries of the form $T[i][j]$ for $1 \le i,j \le n$ is equilibrium iff $T[i][j]+T[k][l]=T[i][l]+T[k][j] (*)$ for any $i,j,k,l$.
If a Table is equilibrium, there are $A,B,C,D$ (the number of times we made a move in Lines $i,k$ and columns $l,j$ respectively) such that:
$$T[i][j]+A+D=T[i][l]+A+C=T[k][l]+B+C=T[k[j]+B+D$$
(1)+(3)=(2)+(4) gives the result.
Now we prove by induction that this is sufficient. The case $n=2$ is straightforward.
To go from $n$x$n$ to $(n+1)$x$(n+1)$, we apply the induction hypothesis ignoring the last row and column. Notice that after making a move, the (*) condition is preserved. Therefore, we see that $T[n+1][1]=T[n+1][2]=...=T[n+1][n]=a$ and $T[1][n+1]=...=T[n+1][n]=b$. If $T[1][1]=c$, we have that $T[n+1][n+1]=a+b-c$. But notice that this is exactly doing the case $2$x$2$, however, in this case we change all columns $1,2,3,...,n$ if we want to make a move in the " $2$x$2$ column 1" and so on.