Consider a latin square of size $n$. We are allowed to choose a $1 \times 1$ square in the table, and add $1$ to any number on the same row and column as the chosen square (the original square will be counted aswell) , or we can add $-1$ to all of them instead. Can we with doing finitly many operation , reach any latin square of size $n?$
Problem
Source: Iranian Third Round 2020 Combinatorics exam Problem3
Tags: latin squares, combinatorics
20.11.2020 16:44
We will show that we can modify all the latin squares that they become equel.First apply all the $-1$ operation to all squares which were $1$ at first This will make all non-1 numbers decrease by 2.And numbers that were $1$ at first will become zero.Now simlarly in each step take all the minimum numbers and and apply $-1$ operation to them it is easy to see that in each step number of minimums will increase by $n$.It is easy to see that any latin square will reach to the same position using this operations so doing this operation reversed can change any latin square to any other.
21.11.2020 15:54
Here is another solution: Using the problems operation , we create another: Consider four squares such that their centers create a rectangle, parallel to the sides of the square. Now apply $-1$ to two of the diagonally opposite squares and $+1$ to the other two. This move we have created can be interpreted as taking a rectangle and adding $1$ to two of the diagonal opposites and subtracting $1$ from the other two We return to the problem: we show that any two latin squares can be directly turned into each other Now, take the $(n-1)$x$(n-1)$ square a the top left of our square. Picking any cell in that part and considering the square in the same row and the rightmost column, the square in the same column and the bottommost row and the bottom right square and applying our new operation such that we turn the square that we had picked, to the equivalent square in the other latin square. Now we have turned the top left $(n-1)$x$(n-1)$ into what we wanted. Now, because our move keeps the sum of each row and column the same, and the sum of rows and columns in the two latin squares are equal, the rest of the square automatically turns into our desired numbers! (Yay)
22.11.2020 21:26
Here is Another Solution: Lemma 1: For any 2 Rows and any Column we can add 1 to the First Row and minus 1 from Second Row(except the 2 intersections of the Selected Column with 2 Rows) and not changing the rest of the Square:(Like in the image below) Proof: The proof is simple just do the operation for the one of the intersections with adding 1 and with the other by subtracting 1. Lemma 2: For any 4 squares such that their centers create a rectangle, parallel to sides of The square , we can change the numbers written in the 2 squares with same row and adding and subtracting their difference to the other 2 squares:(Like in the image below) Proof: Select the 2 rows and one of the columns and do the operation of Lemma 1, $i-j$ times. Then select the 2 rows and the other column and do the operation of Lemma 1, $i-j$ times. Then you are done. Now the rest is easy. Change the numbers in the first row to shape the first row of the Latin square you want to shape using lemma 2 with changing only the last row. Then change the numbers in the second row to shape the second row of the Latin square you want to shape using lemma 2 with changing only the last row. And so on. In the end the upper $n*(n-1)$ square is exactly as the wanted Latin square. Then you can see that lemma 2 doesn't change the sum of each row and column. So it's easy to see that the numbers in the last row Must be equal to the numbers of the last row of The wanted Latin Square. And so we are done.
Attachments:


12.10.2021 14:26
Let' define both $ A,B $ are latin squares. We want to transform $A$ to $B$. For every position $ (x,y) $, if $ d=B[x,y]-A[x,y]<0 $ , then we add -1 for $d$ times on the x-th row and y-th column, and if $d>0$ then add +1 for $d$ times. We can easily prove correctness by calculation. And accroding to the result of my program, it's only one essentially different way to transform $A$ to $B$ . I think it's more interesting to prove this. But I don't know how to prove it.
23.03.2022 21:20
Well you can use induction I guess
23.03.2022 22:05
Shav wrote: Here is Another Solution: Lemma 1: For any 2 Rows and any Column we can add 1 to the First Row and minus 1 from Second Row(except the 2 intersections of the Selected Column with 2 Rows) and not changing the rest of the Square:(Like in the image below) Proof: The proof is simple just do the operation for the one of the intersections with adding 1 and with the other by subtracting 1. Lemma 2: For any 4 squares such that their centers create a rectangle, parallel to sides of The square , we can change the numbers written in the 2 squares with same row and adding and subtracting their difference to the other 2 squares:(Like in the image below) Proof: Select the 2 rows and one of the columns and do the operation of Lemma 1, $i-j$ times. Then select the 2 rows and the other column and do the operation of Lemma 1, $i-j$ times. Then you are done. Now the rest is easy. Change the numbers in the first row to shape the first row of the Latin square you want to shape using lemma 2 with changing only the last row. Then change the numbers in the second row to shape the second row of the Latin square you want to shape using lemma 2 with changing only the last row. And so on. In the end the upper $n*(n-1)$ square is exactly as the wanted Latin square. Then you can see that lemma 2 doesn't change the sum of each row and column. So it's easy to see that the numbers in the last row Must be equal to the numbers of the last row of The wanted Latin Square. And so we are done. nodgd wrote: Let' define both $ A,B $ are latin squares. We want to transform $A$ to $B$. For every position $ (x,y) $, if $ d=B[x,y]-A[x,y]<0 $ , then we add -1 for $d$ times on the x-th row and y-th column, and if $d>0$ then add +1 for $d$ times. We can easily prove correctness by calculation. And accroding to the result of my program, it's only one essentially different way to transform $A$ to $B$ . I think it's more interesting to prove this. But I don't know how to prove it. Congrats on 1st post.
23.06.2022 05:06
Mr.C wrote: Consider a latin square of size $n$. We are allowed to choose a $1 \times 1$ square in the table, and add $1$ to any number on the same row and column as the chosen square (the original square will be counted aswell) , or we can add $-1$ to all of them instead. Can we with doing finitly many operation , reach any latin square of size $n?$ I am not sure if I am missing something trivial. But it is direct that sum of all the numbers modulo $2n-1$ is constant. Hence we cannot reach all Latin square of size $n$ (unless $n=1$).
23.06.2022 15:22
guptaamitu1 wrote: Mr.C wrote: Consider a latin square of size $n$. We are allowed to choose a $1 \times 1$ square in the table, and add $1$ to any number on the same row and column as the chosen square (the original square will be counted aswell) , or we can add $-1$ to all of them instead. Can we with doing finitly many operation , reach any latin square of size $n?$ I am not sure if I am missing something trivial. But it is direct that sum of all the numbers modulo $2n-1$ is constant. Hence we cannot reach all Latin square of size $n$ (unless $n=1$). Latin Squares are special squares. And question asks that you can change any Latin square to any other latin square that has same numbers in this square with before one. You can find information about Latin Squares with Google search.