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 .

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

Click to reveal hidden text

Best Regard

Can anyone post a solution that is readable?

Did you solve it for $3 \times 3$ table ???

If m = n = 3 then the problem is obvious as we are assuming we can prove it for 3x3.

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 .

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?

Sorry , but it is for any subtable $ 3 \times 3 $ not for one . This is my mistake on translation .

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"?

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.

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?

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) \]

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).

OK , maybe it's my mistake , the correct one is on complete solution (#11) .

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.