Silk Road Mathematics Competition competition problems

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$ which is divisible by $2002$. By definition, $d(m) = |a_m - a'_m| < 2002$. Set $a_m - a'_m = 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 < 2002(k+1)$. Thus, we can reach a desired configuration repeating this procedure finitely many times.