3. We have a $n \times n$ board. We color the unit square $(i,j)$ black if $i=j$, red if $i<j$ and green if $i>j$. Let $a_{i,j}$ be the color of the unit square $(i,j)$. In each move we switch two rows and write down the $n$-tuple $(a_{1,1},a_{2,2},\cdots,a_{n,n})$. How many $n$-tuples can we obtain by repeating this process? (note that the order of the numbers are important)
Problem
Source: 2023 Iran MO 2nd round
Tags: combinatorics
GuvercinciHoca
19.05.2023 10:07
$\frac{3^n+3-2n}{4}$. And the main idea is, all $n-$tuples need to have
the first color from the left, other than black, must be green and
the first color from the right, other than black, must be red
Eilia_K1385
29.05.2023 11:05
Non-black houses on the main diagonal are called colored houses. We claim that we can achieve a coloring of the main diameter with the allowed movement of the problem if and only if, in this coloring, the first colored house on the main diameter is red and the last colored house on the main diameter is green. To prove this claim, notice that the numbers of the lines form a permutation of natural numbers smaller than $n$ after the displacement operation, if we make each position of this place in the color of the house of the corresponding main diameter, we can see. that our problem is equivalent to the problem because given a permutation of natural numbers smaller than $n$ such as $a_{i}$, if $a_{i} \leq i$ the place $i$ is green, If $ a_{i} = i$ , we make this position black and if $ i \leq a_{i} $, we make this position red. Find the number of different colorings that can be made for n different permutations.