Suppose a $m \times n$ table. We write an integer in each cell of the table. In each move, we chose a column, a row, or a diagonal (diagonal is the set of cells which the difference between their row number and their column number is constant) and add either $+1$ or $-1$ to all of its cells. Prove that if for all arbitrary $3 \times 3$ table we can change all numbers to zero, then we can change all numbers of $m \times n$ table to zero. (Hint: First of all think about it how we can change number of $ 3 \times 3$ table to zero.)
Problem
Source:
Tags: induction, invariant, geometry, geometric transformation, combinatorics proposed, combinatorics
19.05.2013 21:55
its IRAN 2013 national math olympiad problem 5 day 2.for 3.3 the sum of number of (1,3),(2,1),(3,2)is equal with the sum of of number of (3,1),(1,2),(2,3).prove that its if and only if . now its easy with induction .
19.05.2013 22:00
Hi ; Yes it's easy with the hint from the problem This is simple invariant and a little induction to change one row or column to zero
Best Regard
18.06.2013 21:59
Can anyone post a solution that is readable?
18.06.2013 22:00
Did you solve it for $3 \times 3$ table ???
18.06.2013 22:08
If m = n = 3 then the problem is obvious as we are assuming we can prove it for 3x3.
18.06.2013 22:16
OK , for $m,n \ge 3$ use same trick for $3 \times 3 $ table we get in each move the some of the squares of $(1,3),(2,1),(3,2)$ and $(3,1),(1,2),(2,3)$ doesn't change , now use induction and this invariant to change one column or row to zero and it will obvious .
18.06.2013 22:24
Perhaps I am misunderstanding the problem completely. First interpretation (I don't think its this one): The problem asks " Prove that if for an arbitrary 3x3 table we can change all numbers to zero, then we can change all numbers of table to zero." As noted we cannot change "an arbitrary" 3x3 table to zero, hence our statement "A =>B" has A false and hence the statement is true, as a logical statement. Second interpretation (This is how I understand the problem): Suppose that for any 3x3 SUBtable of the original nxm table we can make changes so that all of its entries are zero. THEN it follows (or at least this is what we need to show) that the entire table can be made to have only 0 entries. Are any of the above interpretations correct?
18.06.2013 22:28
Sorry , but it is for any subtable $ 3 \times 3 $ not for one . This is my mistake on translation .
18.06.2013 22:34
Perhaps, I should rephrase my question: Can anyone post a solution that does not involve saying that "it is obvious by induction", or "look at it and it will become obvious"?
18.06.2013 23:09
Solution : First of all suppose that $m,n \ge 3$ . We show the number on $(i,j)$ square with $A(i,j)$ . Suppose a $3 \times 3$ sub-table which the right-up square of this table is $(i,j)$ , and we show it with $S(i,j)$ . Suppose that : \[ A(i+1,j)-A(i+2,j)+A(i+2,j-1)-A(i+1,j-2)+A(i,j-2)-A(i,j-1)=T_{S(i,j)} \] Now it easy to see in each move $T_{S(i,j)}$ is constant. Now from the condition we can change all sub-tables to zero , it means $T_{S(i,j)}$ is zero on each moves . Now we use induction on $m+n$. For $m+n=6 \Longrightarrow m=n=3 $ we have $3 \times 3$ table which is obvious . Now assume that $m+n > 6$ which means one of them like $m$ is larger that 3 . For $n \times (m-1) $ we use induction condition to change the numbers to zero. Now we will prove that on the $m$-th column we have $A(2,m)=A(3,m)= \ldots = A(n-1,m) = A(n,m) $ . On $S(1,m) $ we have : \[ T_{S(1,m)} = A(2,m) - A(3,m) + A(3,m-1) - A(2,m-2) + A(1,m-2) + A(1,m-1) = A(2,m) - A(3,m) = 0 \] It means $A(2,m)=A(3,m)$. We can observe $S(2,m) , S(3,m) , \ldots , S(n-2,m)$ we can do simple way to get $A(3,m)=A(4,m) , A(4,m)=A(5,m) , \ldots , A(n-1,m)=A(n,m) \Longrightarrow A(2,m)=A(3,m)= \ldots = A(n,m) = \ell $. Now it's easy to see that we can use condition $\ell$ times for $A(2,m)=A(3,m)= \ldots = A(n,m)$ and $k$ times for $A(1,m)$ which change all of them to zero which as desire . For the case which one of them is less than $3$ we can proof easily.
18.06.2013 23:10
I also had another question: In the 3x3 case how do we know that the sum in cells {(1,2), (2,3), (3,1)} is equal to that of {(2,1), (3,2), (1,3)}? For example isn't the pair {(2,1), (3,2)} a diagonal (according to the definition of the problem), and hence we can add 1 to both cells and no others, thereby breaking the equality above?
18.06.2013 23:24
It's obvious because in last step all the numbers in $3 \times 3$ sub-table changes into zero so at the first we had : \[ A(i+1,j)+A(i+2,j-1)+A(i,j-2)=A(i,j-1)+A(i+2,j)+A(i+1,j-2) \]
19.06.2013 01:33
The solution you posted is correct and I understand the argument now. However, I urge you to look at your earlier post and see that it does not agree with your solution (the sum $ (1,3),(2,1),(3,2) $ does change while, as you pointed out in the proof the sum $(1,1),(2,3),(3,2) $ does not).
19.06.2013 19:47
OK , maybe it's my mistake , the correct one is on complete solution (#11) .
31.12.2023 16:27
Solved with rama1728. Very similar in taste to an IMO shortlist 1989 problem in Pranav Sriram. I assume that $m,n\ge 3$ else the problem makes no sense. First, we note that, no matter what moves are made, the difference between the sum of the numbers in $(1,1) (2,3) (3,2)$ and $(1,2) (2,1) (3,3)$ is invariant. This is because, any row/column /diagonal includes exactly 2 (or 0) of these values, one from each sum. Now, we are in a position to induct. Well, if this is true for $(m,n)$ it is trivial that it is true for $(n,m)$. Thus, we show that if it is true for $(m,n-1)$ then it is true for $(m,n)$ which will complete the induction. Note that, by the inductive hypothesis, it is possible to convert the $m \times n-1$ grid on the left-side corner of the $m\times n$ grid. Let $a_1,\dots, a_m$ be the entires of the cells of the right-most column from top-to bottom. Now, consider the top-left corner $3\times 3$ grid. By the previously described invariant, we must have \[a_2+0+0=0+0+a_3\]Thus, $a_2=a_3$. Similarly, we have that $a_i = a_{i+1}$ for all $2\leq i \leq n-1$. Thus, $a_2=a_3=\dots =a_n$. Now, we subtract $a_2$ from every entry of this column. We are then left with a grid which is all zeros, except for the top-right hand corner which may or may not be 0. If it is zero, we are done. If not note that it is a diagonal and thus, can be most easily converted to 0 and we are done. Thus, the induction is complete and by the Principle of Mathematical Induction, we have that for all $m,n\geq 3$, the required result holds on a $m\times n$ board irrespective of the original arrangement if the given condition is satisfied as desired.