A - Permutation Grid Editorial by evima
Consider the case \(n=5\) and the permutations \(R, C\) are both \(1,2,3,4,5\). Let ?
denote the square whose color is not yet determined.
?????
?????
?????
?????
?????
Since the \(5\)-th row should have five black squares, it must be entirely black. The same goes for the \(5\)-th column.
????#
????#
????#
????#
#####
Since the \(1\)-st row should have one black square, all remaining squares must be white. The same goes for the \(1\)-st column.
....#
.???#
.???#
.???#
#####
Since the \(4\)-th row should have four black squares, all remaining squares must be black. The same goes for the \(4\)-th column.
....#
.??##
.??##
.####
#####
Since the \(2\)-nd row should have two black squares, all remaining squares must be white. The same goes for the \(2\)-nd column.
....#
...##
..?##
.####
#####
Since the \(3\)-rd row should have three black squares, all remaining squares must be black. The same goes for the \(3\)-rd column.
....#
...##
..###
.####
#####
Therefore, the square at the \(r\)-th row from the top and \(c\)-th column from the left will be black if \(r+c\ge 6\) and white otherwise.
We can also prove that for a general \(n\), when the permutations \(R, C\) are both \(1,2,\dots,n\), the square at the \(r\)-th row from the top and \(c\)-th column from the left will be black if \(r+c\ge n+1\) and white otherwise. (We can prove it, for example, by induction by determining the outermost squares as we did above and reducing the case to the \(n-2\) case.)
Additionally, when we have the solution \(M\) for some \(R_1,\dots,R_n, C_1,\dots,C_n\), the solution for that case after swapping the \(a\)-th and \(b\)-th terms of \(R_1,\dots,R_n\) will be \(M\) after swapping the \(a\)-th and \(b\)-th rows. The same goes for columns.
Therefore, the square at the \(r\)-th row from the top and \(j\)-th column from the left will be black if \(R_r+C_c\ge n+1\) and white otherwise.
posted:
last update: