Let $n\ge2$ be a positive integer. The numbers $1,2,..., n^2$ are consecutively placed into squares of an $n\times n$, so the first row contains $1,2,...,n$ from left to right, the second row contains $n+1,n+2,...,2n$ from left to right, and so on. The magic square value of a grid is defined to be the number of rows, columns, and main diagonals whose elements have an average value of $\frac{n^2 + 1}{2}$. Show that the magic-square value of the grid stays constant under the following two operations: (1) a permutation of the rows; and (2) a permutation of the columns. (The operations can be used multiple times, and in any order.) Proposed by Ray Li
Problem
Source: ELMO Shortlist 2013: Problem C1, by Ray Li
Tags: analytic geometry, combinatorics unsolved, combinatorics
23.07.2013 12:28
Assign coordinates to the squares of the grid so that initially, $1$ occupies position $(1, 1)$, $n$ occupies position $(1, n)$, and $n^2$ occupies position $(n, n)$. Clearly any grid configuration that can be reached by the application of some number of operations is given uniquely by two permutations $\pi_r$ and $\pi_c$, where the entry originally at $(i, j)$ is now at position $(\pi_r(i), \pi_c(j))$. If row $i$ initially had average element $(n^2 + 1)/2$ the average element of row $\pi_r(i)$ is \[\sum_{k = 1}^{n}{\#(\pi_r(i), k)} = \sum_{k = 1}^{n}{\#(\pi_r(i), \pi_c(k))}\] which is the sum of the entries initially in row $i$ so row $\pi_r(i)$ has average element $(n^2 + 1)/2$ as well. Analogous reasoning gives the same conclusion for columns. It remains only to consider diagonals. It's easy to see that initially, both main diagonals have average element $(n^2 + 1)/2$. The sum of the entries on the main diagonals after the operations have been performed is \[\sum_{k = 1}^{n}{\#(\pi_r(k), \pi_c(k))} = \sum_{k = 1}^{n}{n[\pi_r(k) - 1]+ \pi_c(k)} = \frac{n^3 + n}{2}\] and \[\sum_{k = 1}^{n}{\#(\pi_r(k), \pi_c(n + 1 - k))} = \sum_{k = 1}^{n}{n[\pi_r(k) - 1]+ \pi_c(n + 1 - k)} = \frac{n^3 + n}{2}\] so that both main diagonals have average element $(n^2 + 1)/2$ as before.
08.11.2015 21:22
Assign coordinates same as hyperbolictangent. Then we see that we have a special property:$ # (i_{1},j_{1}) + # (i_{2}i,j_{2}) = # (i_{2},j_{1}) + #(i_{1},j_{2})$.This property is preserved at each step and it maintains a constant sum of the two main diagonals.Similar reasoning goes for columns.