Korean Mathematical Olympiad Final Round

Let $a_{ij}$ be the number in the box at the intersection of the $i$-th row and $j$-th column in the present phase. For each $s$ and $t$ with $1\le s,t\le n$, let $c_s$ be the number of times the button in the $s$-th row is pushed, and $d_t$ the number of times the button in the $t$-th column is pushed. Then one may easily show that $a_{st}=c_s+d_t(\mathrm{mod}k+1)$.

Hence, if $a_{1i}=a_{1j}$, then $a_{wi}=a+wj$ for every $w=1,2,\dots ,n$. The same holds for any two rows. Let $a_{11}=\alpha$ for convenience. For any positive integers $i,j$ ($0\le i,j\le k$), let $a_i$ be the number of $i$'s in the first row and $b_j$ be the number of $j$'s in the first column.

Now for each $w$ with $0\le w\le k$, consider the smallest number of processes pushing suitable buttons in the columns so that every number in the first row is changed to $w$. Note that the total number of processes to do this is $$\sum _{i+j\equiv w(\mathrm{mod}k+1)}j{a}_i=w{a}_0+(w-1)a_1+\cdots +a_{w-1}+k{a}_{w+1}+\cdots +(w+1)a_k.$$ Since $\alpha$ is changed to $w$, the number of times the button in the first column is pushed is $w-\alpha$ (mod $k+1$). Therefore the number $i$ in the first row is changed to $w-\alpha +i$ (mod $k+1$) during the processes. Now we push the buttons in the columns so that every number in the chess board is changed to $0$. The total number of times the buttons in the rows or columns are pushed during the processes is $$S_w=\sum _{i+j\equiv \alpha -w(\mathrm{mod}k+1)}j{b}_i+\sum _{i+j\equiv w(\mathrm{mod}k+1)}j{a}_i.$$ For each $w=0,1,\dots ,k$, these are possible methods of changing all numbers in the boxes to $0$. Summing up all $S_w$'s for every $w$, we have $$\sum _{w=0}^k{S}_w=\{\begin{array}{l}{\sum }_{w=0}^k\left({\sum }_{i+j\equiv \alpha -w(\mathrm{mod}k+1)}j{b}_i+{\sum }_{i+j\equiv w(\mathrm{mod}k+1)}j{a}_i\right)\\ \\ \approx {\sum }_{w=0}^k\left({\sum }_{j\equiv \alpha -i-w(\mathrm{mod}k+1)}j\right)b_i+{\sum }_{w=0}^k\left({\sum }_{j\equiv w-i(\mathrm{mod}k+1)}j\right)a_i\\ \\ \approx \frac{k(k+1)}{2}\left({\sum }_{i=0}^k{a}_i+{\sum }_{i=0}^k{b}_i\right)=k(k+1)n.\end{array}$$ Therefore at least one $S_w$ is less than or equal to $kn$. $\square$