v_Enhance wrote: Let $n$ be a positive integer. The numbers $\{1, 2, ..., n^2\}$ are placed in an $n \times n$ grid, each exactly once. The grid is said to be Muirhead-able if the sum of the entries in each column is the same, but for every $1 \le i,k \le n-1$, the sum of the first $k$ entries in column $i$ is at least the sum of the first $k$ entries in column $i+1$. For which $n$ can one construct a Muirhead-able array? Proposed by Evan Chen It is always possible. Case 1 : $n$ is even. Fill out the numbers in increasing order left to right, top to bottom. Then reverse the order in all the odd-numbered rows. Case 2 : $n=2k+1$. Take the set of the first $3n$ numbers : $\{1,2,\ldots, 3n\}$. We will fill the first $3$ rows so that it satisfies the murihead condition for the sub $3 \times n$ matrix. In the first row fill in $n,n-1,\ldots,1$. Then fill the second row : $(3n+1)/2,(3n-1)/2,\ldots,n+1,2n,2n-1,\ldots,(3n+3)/2$. Fill the last row : $2n+1,2n+3,\ldots,3n,2n+2,2n+4,\ldots,3n-1$. This satisfies all columns sum to a same number but does not satisfy the secon condition. We need to rearrange : Fill the first row : $3n-1,3n-3,\ldots,2n+4,2n+2,(3n+1)/2,(3n-1)/2,\ldots,1$. Fill the last row : $1,2,\ldots,(n-1)/2,2n+1,2n+3,\ldots,,3n$. Fill the second row with whatever is left in the column. This satisfies the second condition since the first row is in decreasing order while the last row is in increasing order (hence the sum of the first two rows are in decreasing order ). Now fill the remaining rows with the remaining numbers in increasing order left to right, top to bottom, then reverse all the even-numbered rows (numbered at least $4$).

Actually, $n=3$ is not possible.

v_Enhance wrote: Actually, $n=3$ is not possible. 3 2 1 8 6 5 4 7 9 What's wrong with the above example?

Oops, I left out the condition that the entries had to be decreasing from top to bottom. (That was the intention of the name Muirhead appearing, it's just asking whether the first $n^2$ integers can be partitioned into sets which majorize each other.)

It is always possible if $n \neq 3$. The case $n$ even is easy, just fill left-right top-bottom in decreasing order then reverse all even-numbered rows. Assume $n$ is odd and $> 3$. Take out the middle $3n$ numbers and these will be used to fill in the middle $3$ rows later. Now we fill in each column from left to right. In the following procedure , we always avoid the middle $3$ cells in each column. Put $n = 2k +3$. Procedure : Take the top $k$ numbers and the bottom $k$ numbers and put them in the first column in decreasing order. Then take the top $k$ numbers and the bottom $k$ numbers from the remaining numbers and put in to the next column in decreasing order, and so on. Now we are left with the middle $3n$ numbers which we denote by : $a+1,a+2,\ldots,a+3n$. We need to use these numbers to fill in the middle $3$ rows. Fill them as follow. First row: $a+3n, a+3n-1,\ldots,a+2n+1$. Second row: $a+n+1, a+n+3,\ldots,a+2n,a+n+2,a+n+4,\ldots,a+2n-1$. Third row : $a+(n+1)/2,a+(n-1)/2,\ldots,a+1,a+n,a+n-1,\ldots,a+(n+3)/2$. Then all column has the same sum. Now we need to check the Murihead condition. For $K <= k+1$, it is obvious because the rows are in decreasing order up to this point. For $K > k +3$ it is also obvious if we look at the cumulative sum of each column from the other direction. (bottom to top ), as the rows are in increasing order. If $K = k+2$, this still holds because the maximum positive difference between an element and is left neighbor in this row is $2$, where as the accumulative sum (till row $k+1$) of each column is at least $2 +$ that of the next column to its right. If $K = k+3$. We look at the cumulative sum in the reverse direction. Up to this point, the cumulative sum of each column greater than that of the next column to its left. And on the row $k+3$, the biggest positive difference between one cell and its right neighbor is $1$, hence the cumulative sums in the reverse direction are still in non-decreasing order till row $k+3$. Using the above algorithm generate the following examples for $n=5$ and $n=7$. $n=5$: $$\begin{array} {ccccc} 25 & 24 & 23 & 22 & 21 \\ 20 & 19 & 18 & 17 & 16 \\ 11 & 13 & 15 & 12 & 14 \\ 8 & 7 & 6 & 10 & 9 \\ 1 & 2 & 3 & 4 & 5 \end{array}$$ $n=7$: $$\[ \begin{array} {ccccccc} 49 & 47 & 45 & 43 & 41 & 39 & 37 \\ 48 & 46 & 44 & 42 & 40 & 38 & 36 \\ 35 & 34 & 33 & 32 & 31 & 30 & 29 \\ 22 & 24 & 26 & 28 & 23 & 25 & 27 \\ 18 & 17 & 16 & 15 & 21 & 20 & 19 \\ 2 & 4 & 6 & 8 & 10 & 12 & 14 \\ 1 & 3 & 5 & 7 & 9 & 11 & 13 \end{array}$$