Let n≥2 be a positive integer. The numbers 1,2,...,n2 are consecutively placed into squares of an n×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 n2+12. 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 n2 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 πr and πc, where the entry originally at (i,j) is now at position (πr(i),πc(j)). If row i initially had average element (n2+1)/2 the average element of row πr(i) is n∑k=1#(πr(i),k)=n∑k=1#(πr(i),πc(k)) which is the sum of the entries initially in row i so row πr(i) has average element (n2+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 (n2+1)/2. The sum of the entries on the main diagonals after the operations have been performed is n∑k=1#(πr(k),πc(k))=n∑k=1n[πr(k)−1]+πc(k)=n3+n2 and n∑k=1#(πr(k),πc(n+1−k))=n∑k=1n[πr(k)−1]+πc(n+1−k)=n3+n2 so that both main diagonals have average element (n2+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.