Silk Road Mathematics Competition

Consider any number $a_1$ which is not divisible by $2002$. Then there exists a number $a_2$ not divisible by $2002$ lying on the same row with $a_1$. In turn, there exists a number $a_3$ not divisible by $2002$ lying on the same column with $a_2$. We continue this process till we first reach a number $a_k$ which lies on the same row or column with some number $a_l$, $1\le l\le k-2$.

Take $l$ as a maximal number with this property. One easily sees that the collection $C$ of numbers $a_l,a_{l+1},\dots ,a_k$ includes an even number of elements.

For each number $a_i$, $l\le i\le k$ set $d(i)={\min }_{k\in \mathbb{Z}}|a_i-2002k|$.

Take $m\in \{l,\dots ,k\}$ with $d(m)\le d(i)$, $l\le i\le k$ and replace $a_m$ with the closest integer number $a_m^{\prime }$ which is divisible by $2002$. By definition, $d(m)=|a_m-a_m^{\prime }|<2002$. Set $a_m-a_m^{\prime }=d$ and replace the remaining elements in $C$ as follows: if $|i-m|$ is even, replace $a_i$ by $a_i-d$; if $|i-m|$ is odd, replace $a_i$ by $a_i+d$.

It can be easily seen that after these replacements the number of integers not divisible by $2002$ is decreased at least by one, the sums of rows and columns are unchanged, and if $2002k<a_j<2002(k+1)$ then $2002k<a_j^{\prime }<2002(k+1)$. Thus, we can reach a desired configuration repeating this procedure finitely many times.