You have an n × n grid of empty squares. You place a cross in all the squares, one at a time. When you place a cross in an empty square, you receive i+j points if there were i crosses in the same row and j crosses in the same column before you placed the new cross. Which are the possible total scores you can get?
I agree completely with Steven Lord.
To put it a little differently, all we are counting is the total number of "handshakes", if every cell shakes hands with every other cell in their row and column. There are n^2 cells, and and each shakes hands with 2(n-1) other cells, but we need to divide by 2 to avoid double-counting. So, n^2 * 2(n-1) / 2 = (n-1)n^2
Solution (spoiler)
