Cells of a $n*n$ square are filled with positive integers in the way that in the intersection of the $i-$th column and $j-$th row, the number $i+j$ is written. In every step, we can choose two non-intersecting equal rectangles with one dimension equal to $n$ and swap all the numbers inside these two rectangles with one another. ( without reflection or rotation ) Find the minimum number of moves one should do to reach the position where the intersection of the $i-$th column and $j-$row is written $2n+2-i-j$.
Problem
Source: Iranian 3rd-Round MO 2019 ; mid-term Combinatorics Exam P3
Tags: rectangle, combinatorics
bumjoooon
24.08.2019 00:36
Thank you for posting. Since I have difficulties in understanding the problem clearly, I'm posting a question to remove the vagueness. What does "two non-intersecting equal rectangles with one dimension equal to n". If I understand correctly, it seems like two non-intersecting $n \times k$ rectangles or two non-intersecting $k \times n$ rectangles. For example, two different rows are two different columns. If that's the right meaning, my guess is $2[n/2]$. Change $1$st row and $n$th row, $2$nd row and $(n-1)$ th row and goes on. Next, change $1$st column and $n$th column, $2$nd colum and $(n-1)$ th column and goes on. Then $2[n/2]$ is enough for the desired situation.
matinyousefi
09.04.2020 06:29
@above you got the problem statement right. Shamefully this is just the 2D version of Bulgaria 2001.
r_ef
25.08.2020 11:21
........
Why-
22.09.2020 14:55
matinyousefi wrote: @above you got the problem statement right. Shamefully this is just the 2D version of Bulgaria 2001. But I dont't think they are the same It does't need consecutive in this problem
Why-
23.09.2020 09:47
We can consider the of number of adjacent reverse pair which is $n-1$ at first and every step can decrease at most $2$ adjacent reverse pair Then extension to 2D So the answer is$\boxed{2[\frac{n}{2}]}$
nbdaaa
26.02.2022 04:31
Consider the main diagonal (the one from the top left to the right bottom) of the square, which is filled $2,4,6,8, \ldots, 2n$ from the top to the bottom in that order. Note that in every single step, our progress doesn't change the numbers on $n$ cells, but change there orders. Also the last configuration we have the reverse order $2n,2(n-1), \ldots , 4, 2$. Let $(a,b)$ be a "good" pair iff $a,b$ are consecutive, $a$ is above $b$ and $a<b$. Then easily prove that each step the numbers of good pairs change at most $2$. But since in the last configuration there are $0$ good pairs, in the start point we have $n-1$ good pairs, then we need at least $2 \left\lfloor {\frac{n}{2}} \right\rfloor $ steps The construction is easy now! Choose consecutively the $k$ column and the $n+1-k$ column for $k=0,1,2,... $ (Take the $2$ symmetric column wrt to the horizontal symmetrical axis )