Maths Olympiad Prep

Library / /178 of 299

Combinatorics Difficulty 6.7 National Olympiad Prove it Iran

An n×nn \times n Latin square is given. We are allowed to do the following operation on an n×nn \times n table. We can choose a cell in the square and add the same integer to the number of all the cells in the union of the row and the column of the chosen cell. Prove that one can do a finite number of such operations to reach every Latin square. (Note that the square after some initial steps need not to be a Latin square, and we can do the operation on each cell more than once.)

Solution

Denote the number of cell (i,j)(i, j) in the square by aija_{ij}. For i,j,r,k{1,2,,n}i, j, r, k \in \{1, 2, \dots, n\}, with iji \neq j and rkr \neq k, we define the operation PijrkP_{ijrk} in this way: Add 11 to all the cells in the union of row and column of cell (i,j)(i, j), add 11 to all the cells in the union of row and column of cell (r,k)(r, k), add 1-1 to all the cells in the union of row and column of cell (i,k)(i, k), and finally add 1-1 to all the cells in the union of row and column of cell (r,j)(r, j).
After this operation, air,ajka_{ir}, a_{jk} will increase by 11, aik,arka_{ik}, a_{rk} will decrease by 11 and all the other cells remain the same.

For two squares AA and BB we define
d(A,B)=1i,jnaijbij. d(A, B) = \sum_{1 \le i, j \le n} |a_{ij} - b_{ij}|.
We want to use the above operation to replace the Latin square AA by some other square AA' such that d(A,B)<d(A,B)d(A', B) < d(A, B) if we can do this by repeating this operation we can transform AA to BB.
Because the sum of the numbers in each row and column in AA and BB are the same, there should be two integer numbers 1i,jn1 \le i, j \le n so that aij>bija_{ij} > b_{ij} and two integer numbers 1k,ln1 \le k, l \le n so that aik<bik,alj<blja_{ik} < b_{ik}, a_{lj} < b_{lj}. Now if we do the operation PiljkP_{iljk} on AA to obtain AA' then d(A,B)<d(A,B)d(A', B) < d(A, B) and the sum of numbers in each row and column of AA' does not change. So we can reach BB by repeating this process. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.