A $9\times 9$ table is filled with zeroes.In every step we can either take a row add $1$ to every cell and shift it one unit to right or take a column reduce every cell by $1$ and shift it one cell down. Can the table with the top right $-1$ and bottom left $+1$ and all other cells zero be reached?
Problem
Source: Iranian RMM TST Day2 P5
Tags: combinatorics
Pathological
15.01.2020 06:21
Funny problem! We'll assume that when we shift the row to the right, the rightmost number in that row ends up in the leftmost position of the row, and likewise for shifting columns. We claim that the answer is actually no. We will consider the entries of the table modulo $9$, and show that it is impossible to reach a state where the top right corner is $8 \pmod{9}$, the bottom left corner is $1 \pmod{9}$, and all other corners are $0 \pmod{9}$. Let's label the table with $[9]^2$ in the obvious manner so that the bottom left corner is $(1, 1)$ and the top right corner is $(9, 9)$ (and going right increases the $x-$coordinate). For all $(i, j) \in [9]^2$, let $a_{i, j}$ be a variable which denotes the value of the number which was originally on cell $(i, j).$ Let's now place a tablet on each cell of the table. Let $t_{i, j}$ denote the tablet which was originally on cell $(i, j).$ At any moment, $t_{i, j}$ will display the number $a_{i, j} - i' - j',$ where $(i', j')$ is the current location of the tablet. We claim that the number on each tablet is invariant modulo $9$. Indeed, working in modulo $9$, when we apply the first operation, $a_{i, j}$ is increased by one, $i'$ is increased by one, and $j'$ is unchanged. Analogously, when working in modulo $9$, when the second operation is applied, $a_{i, j}$ is decreased by one, $i'$ is unchanged, and $j'$ is decreased by one. It is therefore clear that the number on each tablet is always invariant modulo $9$. Initially, for each residue class modulo $9$, there are precisely nine tablets which display a number belonging to that residue class. Hence, this must always be the case. However, in the end state desired in the problem, there are ten tablets which display a number which is $6 \pmod{9}$, namely the nine tablets on all cells $(i, j)$ with $i + j \equiv 3 \pmod{9}$ and the one on $(1, 1).$ This implies that the end state we want cannot be obtained, and so the problem is solved. $\square$
stroller
17.01.2020 20:26
Start from the configuration with $1,-1$ at two corners and see if it can go back to the configuration with all $0$'s when doing all moves in reverse. As in the above solution, view the shifts as moving some tablets. The tablet initially labelled 1 becomes 0 after the operations (supposing such a set of operations exist). This implies that it has moved left once more than it has moved down, which sends it to the diagonal one square to the left of the "main diagonal". However, all squares along this diagonal in the [$1,-1$] configuration are 0, and they end up being 0 as well, which means that each of them has remained in their diagonal, leaving no space for the square labelled $1$ at the beginning to fit in at the end of the operations, contradiction.
CabinetMatesha
13.02.2020 12:42
Let $a(i,j)$ be the number in the cell with row number $i$ and column number $j$. Now let $\omega$ be a complex root of the equation $x^2 +x + 1 = 0$. Let $V(i,j) = a(i,j) * \omega^{i-1 + 2j-1}$. Initially $\sum V(i,j) = 0$. In every step we: $1)$ Add $1$ to every cell of a column which doesn't change the sum , and shift the columns to the right which multiplies the sum $\sum V(i,j)$ by $\omega$. $2)$ Add $-1$ to every cell of a column which doesn't change the sum , and shift the rows down which multiplies the sum $\sum V(i,j)$ by $\omega^2$. Since $\sum V(i,j) $ is initially $0$, it will stay $0$ , but we get that the final value it should take is $\omega - \omega^2$.
chirita.andrei
24.01.2022 00:29
The answer is no. Label the lines and columns $ 0,1,...,8 $. We view the process of shifting numbers in rows/columns as shifting their corespondent cells. For each cell we keep track of it's initial position.
The main claim is:
Claim. If at some moment a cell $ (x;y) $ contains number $z$ and the original cell $ (x_0;y_0) $ contained number $ z_0 $, then $ (x-y)+z\equiv(x_0-y_0)+z_0 \pmod{9}$ i.e. the quantity $ x-y+z \pmod{9} $ is invariant.
Proof: If we apply the row operation the cell becomes $ (x;y+1) $ (we work$\pmod{9}$) and the number is increased by $1$, so $ x-y+z \pmod{9} $ doesn't change. Similarly for the column operation.
Assume we can reach the configuration with $-1$ in $ (8,0) $ and $1$ in $(0,8)$.
Look at the bottom left corner. The claim gives that the original cell belongs to the diagonal $ x-y\equiv7\pmod{9} $. On the other side, the claim also implies that the original cells of all squares on this diagonal have to also belong to this diagonal. That is a contradiction, because each original cell on the $ x-y\equiv7\pmod{9} $ diagonal must stay on this diagonal and, at the same time, one of them goes to $(8,0)$.
Shayan-TayefehIR
27.07.2022 11:03
Consider all entries mod $9$ and suppose there is number $x_{(i , j)}$ on the cell $(i , j)$ in one of the moves. then assign the number $x_{(i , j)}-i-j$ to cell $(i , j)$ and one can see that the set of all assigned numbers is invariant. Comparing this set for these cases , leads to a contradiction.