Problem

Source: ELMO Shortlist 2013: Problem C4, by Evan Chen

Tags: inequalities, algorithm, combinatorics unsolved, combinatorics



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 such that the entries in each column are decreasing? Proposed by Evan Chen